Sponsored
Sponsored
This approach uses a sliding window technique with variables to keep track of the count of consecutive 1's before and after a zero. The main idea is to iterate through the array, and whenever you encounter more than one zero, calculate the length of 1's that can be formed by deleting the previous zero, update maximum length as needed, and reset counts.
Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), as no additional space is used proportional to input size.
1class Solution {
2 public int longestSubarray(int[] nums) {
3 int maxLen = 0, left = 0, zeroCount = 0;
4 for (int right = 0; right < nums.length; right++) {
5 if (nums[right] == 0) zeroCount++;
6 while (zeroCount > 1) {
7 if (nums[left] == 0) zeroCount--;
8 left++;
9 }
10 maxLen = Math.max(maxLen, right - left);
11 }
12 return maxLen;
13 }
14
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] nums = {0,1,1,1,0,1,1,0,1};
18 System.out.println(sol.longestSubarray(nums));
19 }
20}The Java solution is similar to the C++ solution with a two-pointer approach. It uses a loop to move the right pointer and adjusts the left pointer whenever more than one zero is found to keep the subarray valid.
This approach utilizes prefix sums to keep a cumulative count of 1's encountered and calculates lengths avoiding excessive recalculations. Two arrays store the prefix sum of 1's up to the current element and from the current element to the end, respectively. A single pass is then made to compute the maximum length by checking possible deletions at each zero.
Time Complexity: O(n), each element is processed three independent times.
Space Complexity: O(n), proportional to input due to prefix and suffix arrays.
using namespace std;
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> prefix(n, 0), suffix(n, 0);
prefix[0] = nums[0];
for (int i = 1; i < n; i++) {
prefix[i] = (nums[i] == 1) ? prefix[i - 1] + 1 : 0;
}
suffix[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix[i] = (nums[i] == 1) ? suffix[i + 1] + 1 : 0;
}
int maxLen = 0;
for (int i = 0; i < n; i++) {
maxLen = max(maxLen, prefix[i] + ((i + 1 < n) ? suffix[i + 1] : 0));
}
return maxLen == n ? maxLen - 1 : maxLen;
}
};
// Usage
// Solution().longestSubarray({0,1,1,1,0,1,1,0,1});This C++ solution builds prefix and suffix arrays to efficiently iterate over potential zero indices and calculate maximum subarray lengths by once iterating through combining overlapping regions pre and post any zero.