- Published on
Leetcode Pattern 1 Sliding Window
- Authors
- Name
- Yinhuan Yuan
Introduction
The Sliding Window method helps optimize the solution by avoiding unnecessary recomputation, making it particularly useful for problems that require finding a subset of elements within a certain range or condition. In this blog post, we’ll explore what the Sliding Window algorithm is, how it works, and discuss some leetcode questions to illustrate its utility.
The Sliding Window algorithm maintain a range or window of elements in a data structure like an array or string. This range "slides" over the elements to examine each subset that satisfies certain conditions. The key idea is to keep track of a subset of elements in a way that allows efficient computation, often in linear time.
The algorithm typically involves two pointers or indices that represent the boundaries of the current window. These pointers move through the data structure, adjusting the window size and position as needed.
The Sliding Window technique can be broadly divided into two types: fixed-size sliding window, Minimum sliding window and Maximum sliding window.
- Fixed-Size Sliding Window
In this approach, the window size remains constant. As the window slides from the beginning of the array to the end, each subset of elements is considered. This is useful for problems like finding the maximum sum of a subarray of fixed length.
We can solve it by calculate the first k elements firstly. Then, we drop the most left element and add a new element to the window and update the results. The time complexity is O(N).
Pseudo code:
// Pseudo code
// initialize state: [0, k - 1] with nums.slice(0, k)
// iterate i from k to n - 1.
// drop nums[i - k] and add nums[i]
// update state
- Minimum sliding window
In this approach, our goal is to find the minimum length of a window that satisfies a specific condition. We add elements to the window one by one. When adding an element causes the condition to be met, we start removing elements from the beginning of the window until the condition is no longer met. At that point, we have a valid window [left - 1, right]. We calculate its length as right - (left - 1) + 1 and compare it with the current minimum length. If this window is shorter, we update the final result.
function minimumCardPickup(cards: number[]): number {
const meetCondition = (state): boolean => ......;
const n = cards.length;
let state = ....
let ans = Infinity;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
// .......
if (meetCondition(state)) {
while (meetCondition(state)) {
// Update state by removing left element
// .......
left += 1;
}
// [left - 1, right] is the subarray meeting the condition.
ans = Math.min(ans, right - (left - 1) + 1);
}
}
return ans === Infinity ? -1 : ans;
};
- Maximum sliding window
In this approach, our goal is to find the maximum length of a window that satisfies a specific condition. We add elements one by one to the window. If adding an element causes the condition to fail, we remove elements from the beginning of the window. Once we find a valid window [left, right], we calculate its length as right - left + 1 and compare it with the current maximum length. If this window is longer, we update the final result.
function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
const n = s.length;
let ans = -1;
let state = .......
const meetCondition = (state): boolean => ........;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
// .......
while (!meetCondition(freq, k)) {
// Update state by removing left element
// ........
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
- 1. Fixed Sliding Window Problems
- 2. Minimum sliding window Problems
- 3. Maximum sliding window Problems
- 340. Longest Substring with At Most K Distinct Characters[Medium]
- 713. Subarray Product Less Than K[Medium]
- 904. Fruit Into Baskets[Medium]
- 159. Longest Substring with At Most Two Distinct Characters[Medium]
- 3. Longest Substring Without Repeating Characters[Medium]
- 424. Longest Repeating Character Replacement[Medium]
- 485. Max Consecutive Ones[Easy]
- 487. Max Consecutive Ones II[Medium]
- 1004. Max Consecutive Ones III[Medium]
1. Fixed Sliding Window Problems
643. Maximum Average Subarray I[Easy]
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.
Solution: We maintain the sum of the elements within a window of length k as our state. As the window slides, we remove the first element and add a new element to the window. After each slide, we compare the current sum with the final result and update it if necessary.
// Choose the total of the window as the window's value
function findMaxAverage(nums: number[], k: number): number {
const n = nums.length;
// calculate [0, k - 1]
let total: number = nums.slice(0, k).reduce((acc, cur) => acc + cur, 0);
let ans = total;
// i from k to n - 1; drop nums[i - k ] and add nums[i] at each step.
for (let i = k; i < n; i++) {
total -= nums[i - k];
total += nums[i];
ans = Math.max(ans, total);
}
return ans / k;
};
1708. Largest Subarray Length K[Easy]
An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].
For example, consider 0-indexing:
[1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2. [1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2. A subarray is a contiguous subsequence of the array.
Given an integer array nums of distinct integers, return the largest subarray of nums of length k.
Solution: We use the starting index of the array as the state. As the window slides, we increment the starting index by 1. After each slide, we compare the current window with the final result and update it if necessary.
// Chose the left side as the window's state
function largestSubarray(nums: number[], k: number): number[] {
const n = nums.length;
const compare = (start1: number, start2: number): number => {
for (let i = 0; i < k; i++) {
if (nums[start1 + i] !== nums[start2 + i]) {
return nums[start1 + i] - nums[start2 + i];
}
}
return 0;
};
// [0, k - 1] for state
let start: number = 0;
let ans: number = start;
for (let i = k; i < n; i++) {
// drop nums[i - k] and add nums[i]
start += 1;
if (compare(ans, start) < 0) {
ans = start;
}
}
return nums.slice(ans, ans + k);
};
567. Permutation in String[Medium]
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
Solution: We use the letter frequency of the window as the state. As the window slides, we update the frequency by decrementing the count of the letter that was dropped and incrementing the count of the new letter added. After each slide, we compare the letter frequency of the window with the target letter frequency.
To track letter frequencies, we use an array of length 26, where each index represents the frequency of the corresponding letter from 'a' to 'z'.
// Chose the letter frequency as the window's value
// need helper functions: calculateFrequency and compareFrequencuy.
function checkInclusion(s1: string, s2: string): boolean {
if (s2.length < s1.length) {
return false;
}
const getIndex = (s: string, index: number) => s.charCodeAt(index) - 'a'.charCodeAt(0);
const calFreq = (s: string): number[] => {
const result: number[] = Array(26).fill(0);
[...s].forEach((_, index) => {
result[getIndex(s, index)] += 1;
});
return result;
};
const isFreqEqual = (freq1: number[], freq2: number[]) => {
return freq1.every((val, index) => val === freq2[index]);
};
const n = s2.length;
const k = s1.length;
// [0, k - 1]
const s1Freq = calFreq(s1);
const windowFreq = calFreq(s2.slice(0, k));
if (isFreqEqual(s1Freq, windowFreq)) {
return true;
}
// remove s2[i - k] and add s2[i]
for (let i = k; i < n; i++) {
windowFreq[getIndex(s2, i - k)] -= 1;
windowFreq[getIndex(s2, i)] += 1;
if (isFreqEqual(s1Freq, windowFreq)) {
return true;
}
}
return false;
};
438. Find All Anagrams in a String[Medium]
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Solution: Similar to 567. Permutation in String [Medium], the only difference is that we need to include the starting index of the substring.
function findAnagrams(s: string, p: string): number[] {
const getIndex = (s: string, index: number): number => s.charCodeAt(index) - 'a'.charCodeAt(0);
const getFreq = (s: string): number[] => {
const result: number[] = Array(26).fill(0);
[...s].forEach((_, index) => {
result[getIndex(s, index)] += 1;
});
return result;
};
const isFreqEqual = (freq1: number[], freq2: number[]) => freq1.every((val, index) => val === freq2[index]);
let ans: number[] = [];
const n = s.length;
const k = p.length;
// [0, k - 1]
const freqP = getFreq(p);
const freqS = getFreq(s.slice(0, k));
if (isFreqEqual(freqP, freqS)) {
ans.push(0);
}
// i from k to n
// remove i - k and add i
for (let i = k; i < n; i++) {
freqS[getIndex(s, i - k)] -= 1;
freqS[getIndex(s, i)] += 1;
// [i - k + 1, i]
if (isFreqEqual(freqP, freqS)) {
ans.push(i - k + 1);
}
}
return ans;
};
30. Substring with Concatenation of All Words[Hard]
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Solution: Similar to 438. Find All Anagrams in a String[Medium], the only difference is that we need to include the letter frequency and word frequency.
function findSubstring(s: string, words: string[]): number[] {
const n = s.length;
const wordLen = words[0].length;
const k = wordLen * words.length;
const calFreq = (words: string[]): Map<string, number> => {
const freq: Map<string, number> = new Map<string, number>();
for (const word of words) {
const val = freq.get(word) ?? 0;
freq.set(word, val + 1);
}
return freq;
};
const areFreqsEqual = (map1: Map<string, number>, map2: Map<string, number>): boolean => {
const keys1 = [...map1.keys()];
const keys2 = [...map2.keys()];
if (keys1.length !== keys2.length || !keys1.every(key => keys2.includes(key))) {
return false;
}
for (const key of keys1) {
if (map1.get(key) !== map2.get(key)) {
return false;
}
}
return true;
};
const buildWordsFreq = (start: number): Map<string, number> => {
let i = start;
const ans: Map<string, number> = new Map<string, number>();
while (i < start + k) {
const word = s.slice(i, i + wordLen);
const val = ans.get(word) ?? 0;
ans.set(word, val + 1);
i += wordLen;
}
return ans;
};
// Edge case
if (n < k) {
return [];
}
const wordsFreq = calFreq(words);
const lettersFreq = calFreq([...words.join("")]); // default words.join use ,
let sLettersFreq = calFreq([...s.slice(0, k)]);
let sWordsFreq = buildWordsFreq(0); // build words freq with [0, k - 1]
const result: number[] = [];
if (areFreqsEqual(lettersFreq, sLettersFreq) && areFreqsEqual(wordsFreq, sWordsFreq)) {
result.push(0);
}
for (let i = k; i < n; i++) {
// add i and drop i - k
sWordsFreq = buildWordsFreq(i - k + 1); // build words freq with [i - k + 1, i]
const val = sLettersFreq.get(s[i - k]);
if (val === 1) {
sLettersFreq.delete(s[i - k]);
} else {
sLettersFreq.set(s[i - k], val - 1);
}
sLettersFreq.set(s[i], (sLettersFreq.get(s[i]) ?? 0) + 1);
if (areFreqsEqual(lettersFreq, sLettersFreq) && areFreqsEqual(wordsFreq, sWordsFreq)) {
result.push(i - k + 1);
}
}
return result;
};
219. Contains Duplicate II[Easy]
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Solution: We use the frequency of numbers within the window as the state. As the window slides, we update the frequency by decreasing the count of the number that was removed and increasing the count of the newly added number. After each slide, we check the frequency within the window to see if there are any duplicate numbers.
// frequency.windows size: k + 1
function containsNearbyDuplicate(nums: number[], k: number): boolean {
const n = nums.length;
// [0, k]
const map: Map<number, number> = new Map();
for (let i = 0; i <= k; i++) {
if (i === n) break;
if (map.get(nums[i]) >= 1) return true;
map.set(nums[i], (map.get(nums[i]) ?? 0) + 1);
}
// i from k + 1 to n - 1 add nums[i] and drop nums[i - k - 1]
for (let i = k + 1; i < n; i++) {
const key = nums[i - k - 1];
const val = map.get(key) ?? 0;
if (val === 1) {
map.delete(key);
} else {
map.set(key, val - 1);
}
if (map.get(nums[i]) >= 1) return true;
map.set(nums[i], (map.get(nums[i]) ?? 0) + 1);
}
return false;
};
2. Minimum sliding window Problems
209. Minimum Size Subarray Sum[Medium]
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).
Solution: We use the sum of the window elements as the state and check if it exceeds the target.
function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
let total = 0;
let ans = Infinity;
const meetCondition = (total) => total >= target;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
total += nums[right];
if (meetCondition(total)) {
while (meetCondition(total)) {
// Update state by removing left element
total -= nums[left];
left += 1;
}
// [left - 1, right] is the subarray meeting the condition.
ans = Math.min(ans, right - (left - 1) + 1);
}
}
return ans === Infinity ? 0 : ans;
}
76. Minimum Window Substring[Hard]
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Solution: We represent the window state using the frequency of each letter. Since the letters can be both uppercase and lowercase, we use an array of length 52 to store these frequencies. The condition we check is that, for every letter in the target string, its frequency must be less than or equal to its frequency in the window.
function minWindow(s: string, t: string): string {
const aCharCode = 'a'.charCodeAt(0);
const zCharCode = 'z'.charCodeAt(0);
const upperACharCode = 'A'.charCodeAt(0);
const upperZCharCode = 'Z'.charCodeAt(0);
const getIndex = (charCode: number): number => {
if (charCode >= aCharCode && charCode <= zCharCode) {
return charCode - aCharCode;
}
if (charCode >= upperACharCode && charCode <= upperZCharCode) {
return charCode - upperACharCode + 26;
}
throw new Error(`Incorrect character: ${charCode}`);
};
const getCharsFreq = (s: string): number[] => {
const result: number[] = Array(52).fill(0);
[...s].forEach((char, index) => {
result[getIndex(char.charCodeAt(0))] += 1;
});
return result;
};
const isFreqIncluded = (freq: number[], containerFreq: number[]) => freq.every((val, index) => val <= containerFreq[index]);
const tFreq = getCharsFreq(t);
const sFreq: number[] = Array(52).fill(0);
const meetCondition = (tFreq: number[], sFreq: number[]): boolean => tFreq.every((val, index) => val <= sFreq[index]);
let ans = "";
const n = s.length;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
sFreq[getIndex(s.charCodeAt(right))] += 1;
if (meetCondition(tFreq, sFreq)) {
while (meetCondition(tFreq, sFreq)) {
// Update state by removing left element
sFreq[getIndex(s.charCodeAt(left))] -= 1;
left += 1;
}
// [left - 1, right] is the subarray meeting the condition.
if ((ans === "") || (ans.length > right - left + 1)) {
ans = s.slice(left - 1, right + 1);
}
}
}
return ans;
};
2260. Minimum Consecutive Cards to Pick Up[Medium]
You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.
Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.
Solution: We use a set called cardSet and a variable matchedCard to represent the window state. If a card is matched, matchedCard will hold a valid value; otherwise, it will be set to null. The condition we check is whether matchedCard is null.
function minimumCardPickup(cards: number[]): number {
const meetCondition = (matchedCard: number | undefined): boolean => matchedCard !== undefined;
const n = cards.length;
const cardSet: Set<number> = new Set([]);
let matchedCard: number | undefined = undefined;
let ans = Infinity;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
if (cardSet.has(cards[right])) {
matchedCard = cards[right];
} else {
cardSet.add(cards[right]);
}
if (meetCondition(matchedCard)) {
while (meetCondition(matchedCard)) {
// Update state by removing left element
if (cards[left] === matchedCard as number) {
matchedCard = undefined;
} else {
cardSet.delete(cards[left]);
}
left += 1;
}
// [left - 1, right] is the subarray meeting the condition.
ans = Math.min(ans, right - (left - 1) + 1);
}
}
return ans === Infinity ? -1 : ans;
};
3. Maximum sliding window Problems
340. Longest Substring with At Most K Distinct Characters[Medium]
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Solution: We can use the frequency of letters to represent the window state. The condition to check is whether the length of the letter frequency is less than or equal to ( k ).
function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
const n = s.length;
let ans = -1;
const freq: {[key: string] : number} = {};
const meetCondition = (freq: {[key: string] : number}, k: number) => Object.keys(freq).length <= k;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
freq[s[right]] = (freq[s[right]] ?? 0) + 1;
while (!meetCondition(freq, k)) {
// Update state by removing left element
freq[s[left]] -= 1;
if (freq[s[left]] === 0) {
delete freq[s[left]];
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
713. Subarray Product Less Than K[Medium]
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.
Solution: We can use the product of elements to represent the window state. The condition to check is whether the product is less than ( k ).
function numSubarrayProductLessThanK(nums: number[], k: number): number {
const n = nums.length;
if (k <= 1) return 0;
let prod = 1; // State
const meetCondition = (prod: number): boolean = prod < k;
let count = 0;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
prod *= nums[right];
while (!meetCondition(prod)) {
// Update state by removing left element
prod /= nums[left];
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
count += right - left + 1;
}
return count;
};
904. Fruit Into Baskets[Medium]
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets. Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick.
Solution: We can use the frequency of numbers to represent the window state. The condition to check is whether the length of the letter frequency is less than or equal to 2.
function totalFruit(fruits: number[]): number {
// Find the max length of a subarray whose values can only be two different values.
// Use a dictionary to track the sliding window status
const n = fruits.length;
const meetCondition = (freq: {[key: string] : number}) : boolean => Object.keys(freq).length <= 2;
let ans = -1;
const freq: {[key: string] : number} = {};
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
freq[fruits[right]] = (freq[fruits[right]] ?? 0) + 1;
while (!meetCondition(freq)) {
// Update state by removing left element
freq[fruits[left]] -= 1;
if (freq[fruits[left]] === 0) {
delete freq[fruits[left]];
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
159. Longest Substring with At Most Two Distinct Characters[Medium]
Given a string s, return the length of the longest substring that contains at most two distinct characters.
Solution: We can use the frequency of letters to represent the window state. The condition to check is whether the length of the letter frequency is less than or equal to 2.
function lengthOfLongestSubstringTwoDistinct(s: string): number {
const n = s.length;
const meetCondition = (freq: {[key: string]: number}) => Object.keys(freq).length <= 2;
let ans = -1;
const freq: {[key: string]: number} = {};
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
freq[s[right]] = (freq[s[right]] ?? 0) + 1;
while (!meetCondition(freq)) {
// Update state by removing left element
freq[s[left]] -= 1;
if (freq[s[left]] === 0) {
delete freq[s[left]];
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
3. Longest Substring Without Repeating Characters[Medium]
Given a string s, find the length of the longest substring without repeating characters.
Solution: We can use the frequency of letters to represent the window state. The condition to check is whether every value in the letter frequency is less than or equal to 1.
function lengthOfLongestSubstring(s: string): number {
const n = s.length;
if (n === 0) return 0;
const meetCondition = (freq: {[key: string]: number}): boolean => {
return [...Object.values(freq)].every(val => val <= 1);
};
let ans = -1;
const freq: {[key: string]: number} = {};
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
freq[s[right]] = (freq[s[right]] ?? 0) + 1;
while (!meetCondition(freq)) {
// Update state by removing left element
freq[s[left]] -= 1;
if (freq[s[left]] === 0) {
delete freq[s[left]];
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
424. Longest Repeating Character Replacement[Medium]
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Solution: We use the frequency of letters to represent the window state. To make a substring contain only identical letters, we would need to change all letters after removing the one with the highest frequency. The condition to check is whether the total number of letters minus the highest frequency is less than or equal to ( k ).
function characterReplacement(s: string, k: number): number {
// meet condition: Remove the largest freq and add the remaining together,
// the total should less or equal to k.
const n = s.length;
const meetCondition = (freq: {[key: string]: number}): boolean => {
if (Object.keys(freq).length === 0) return true;
const max = Math.max(...Object.values(freq));
const total = [...Object.values(freq)].reduce((acc, cur) => acc + cur, 0);
return total - max <= k;
};
let ans = -1;
const freq: {[key: string]: number} = {};
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
freq[s[right]] = (freq[s[right]] ?? 0) + 1;
while (!meetCondition(freq)) {
// Update state by removing left element
freq[s[left]] -= 1;
if (freq[s[left]] === 0) {
delete freq[s[left]];
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
485. Max Consecutive Ones[Easy]
Given a binary array nums, return the maximum number of consecutive 1's in the array.
Solution: We start by moving the end pointer to the first position containing a 1. Then, starting from end, we move the front pointer forward until it reaches a 0. The count of 1s is calculated as front - 1 - end + 1. We compare this count with the final result and update it if this result is larger. It is slight different from the classic solution.
function findMaxConsecutiveOnes(nums: number[]): number {
// while front < n
// end finds the first 1
// front starting from end and finds the first 0.
// size = front - end.
// end = front
let front = 0;
let end = 0;
const n = nums.length;
let ans = 0;
while (front < n) {
// end finds the first 1
while (end < n && nums[end] !== 1) {
end += 1;
}
if (nums[end] !== 1) {
break;
}
// front starting from end and finds the first 0.
front = end;
while (front < n && nums[front] === 1) {
front += 1;
}
ans = Math.max(ans, front - end);
end = front;
}
return ans;
};
487. Max Consecutive Ones II[Medium]
Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Solution: We use the count of 0 to represent the window state. The condition to check is whether the count is less than or equal to 1.
// Find the longest window which only contain 1 or 0 zero.
function findMaxConsecutiveOnes(nums: number[]): number {
let countZero = 0;
const meetCondition = (countZero) => countZero <= 1;
const n = nums.length;
let ans = 0;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
if (nums[right] === 0) {
countZero += 1;
}
while (!meetCondition(countZero)) {
// Update state by removing left element
if (nums[left] === 0) {
countZero -= 1;
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};
1004. Max Consecutive Ones III[Medium]
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Solution: We use the count of 0 to represent the window state. The condition to check is whether the count is less than or equal to ( k ).
function longestOnes(nums: number[], k: number): number {
let countZero = 0;
const meetCondition = (countZero) => countZero <= k;
const n = nums.length;
let ans = 0;
let left = 0;
for (let right = 0; right < n; right++) {
// Update state by adding right element
if (nums[right] === 0) {
countZero += 1;
}
while (!meetCondition(countZero)) {
// Update state by removing left element
if (nums[left] === 0) {
countZero -= 1;
}
left += 1;
}
// the number of new subarrays ending at right is (right - left + 1).
// [left, right], [left + 1, right], [left + 2, right]......[right, right]
// count += right - left + 1;
ans = Math.max(ans, right - left + 1);
}
return ans;
};