703381. Length of longest subarray
Length of Longest Subarray
Slug: length-of-longest-subarray0440
Difficulty: Easy
Id: 703381
Topic Tags: two-pointer-algorithm, Arrays, Data Structures, Algorithms
Company Tags: None
Summary
Given an array of integers where all elements are either 0 or 1, find the length of the longest subarray with at most one 1.
This problem involves using a two-pointer algorithm to solve this problem efficiently. The key concept is to maintain two pointers that traverse the array and update the maximum length found so far.
Detailed Explanation
The given array can be thought of as alternating between 0s and 1s, with at most one 1 in every subarray of interest. To find the longest such subarray, we use a sliding window approach with two pointers, left and right, both initially pointing to the start of the array.
Here's the step-by-step breakdown:
- Initialize
max_lengthto 0, which will store the maximum length found so far. - Iterate through the array using the two-pointer approach:
- If the current element is 0, increment both
leftandrightpointers. - If the current element is 1, increment only the
rightpointer.
- If the current element is 0, increment both
- For each iteration, check if there's more than one 1 in the current subarray (i.e., if
right - left > 1). If so, updatelefttoleft + 1to reset the sliding window. - Update
max_lengthwhenever a longer subarray is found. - Return
max_lengthas the length of the longest subarray with at most one 1.
The time complexity for this algorithm is O(n), where n is the length of the input array, since we only need to traverse the array once. The space complexity is O(1) since we only use a constant amount of space to store left, right, and max_length.
Optimized Solutions
Java
int longestSubarray(int[] arr) {
int max_length = 0;
int left = 0, right = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
left++;
right = i + 1;
} else {
right++;
if (right - left > 1) {
left = right - 1;
}
}
max_length = Math.max(max_length, right - left);
}
return max_length;
}