Sponsored
Sponsored
This approach involves using a sliding window distinguished by two pointers. The window expands by moving the right pointer and checks whether the number of zeros within the window exceeds the allowed count 'k'. If it does, we move the left pointer to shrink the window until the condition is satisfied. We aim to find the maximum window size that can be achieved following this condition.
Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice.
Space Complexity: O(1), as no additional space is used aside from variables.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int longestOnes(vector<int>& nums, int k) {
6 int left = 0, max_len = 0, zeros_count = 0;
7 for (int right = 0; right < nums.size(); ++right) {
8 if (nums[right] == 0) {
9 zeros_count++;
10 }
11 while (zeros_count > k) {
12 if (nums[left] == 0) {
13 zeros_count--;
14 }
15 left++;
16 }
17 max_len = max(max_len, right - left + 1);
18 }
19 return max_len;
20}This C++ code similarly uses a left and right pointer methodology while maintaining zero count. The max length of the ones subarray is captured by moving the right pointer to expand and left to constrict the window based on zero count.