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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int longestSubarray(vector<int>& nums) {
8 int maxLen = 0, left = 0, right = 0, zeroCount = 0;
9 for (right = 0; right < nums.size(); right++) {
10 if (nums[right] == 0) zeroCount++;
11 while (zeroCount > 1) {
12 if (nums[left] == 0) zeroCount--;
13 left++;
14 }
15 maxLen = max(maxLen, right - left);
16 }
17 return maxLen;
18 }
19};
20
21// Usage
22// Solution().longestSubarray({0,1,1,1,0,1,1,0,1});This C++ implementation uses the two-pointer method to spread out the window, counting zeros, and only keeping one zero in the window at any time. It calculates maximum length by monitoring the window size excluding edges where more than one zero is present.
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.
public int LongestSubarray(int[] nums) {
int n = nums.Length;
int[] prefix = new int[n];
int[] suffix = new int[n];
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 = Math.Max(maxLen, prefix[i] + ((i + 1 < n) ? suffix[i + 1] : 0));
}
return maxLen == n ? maxLen - 1 : maxLen;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {0,1,1,1,0,1,1,0,1};
Console.WriteLine(sol.LongestSubarray(nums));
}
}This C# strategy uses prefix-suffix arrays to simplify and manage length calculation through a clever handling of subarray boundaries. It handles each element strategically to balance cumulative considerations.