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.
1public class 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 Console.WriteLine(sol.LongestSubarray(nums));
19 }
20}The C# solution also leverages two pointers to ensure that the subarray being considered never has more than one zero at any point. When it exceeds, it adjusts the window by moving the left pointer.
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.