Tasks

Sliding Window

April 2023

Index	Name	Number	Difficulty	Link
1	Maximum Sum Subarray of Size K	643	Easy	https://leetcode.com/problems/maximum-average-subarray-i/
2	Longest Substring Without Repeating Characters	3	Medium	https://leetcode.com/problems/longest-substring-without-repeating-characters/
3	Minimum Size Subarray Sum	209	Medium	https://leetcode.com/problems/minimum-size-subarray-sum/
4	Fruit Into Baskets	904	Medium	https://leetcode.com/problems/fruit-into-baskets/
5	Permutation in String	567	Medium	https://leetcode.com/problems/permutation-in-string/
6	Maximum Points You Can Obtain from Cards	1423	Medium	https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/
7	Minimum Window Substring	76	Hard	https://leetcode.com/problems/minimum-window-substring/
8	Longest Repeating Character Replacement	424	Medium	https://leetcode.com/problems/longest-repeating-character-replacement/
9	Sliding Window Maximum	239	Hard	https://leetcode.com/problems/sliding-window-maximum/
10	Find All Anagrams in a String	438	Medium	https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

// 643. Maximum Average Subarray I

// Time: O(n) | Space: O(1)
var findMaxAverage = function(nums, k) {
    let max = -Infinity;
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (i < k - 1) {
            continue;
        }
        if (i > k - 1) {
            sum -= nums[i - k];
        }
        max = Math.max(max, (sum / k));
    }
    return max;
};

/*
Sliding Window
------------------------
1. Iterate over moving window.
2. Check average for nums in window.
3. Update max after every window move.
4. Return result.
------------------------
Time: O(n) | Space: O(1)
*/

// 3. Longest Substring Without Repeating Characters

// Time: O(n) | Space: O(n)
var lengthOfLongestSubstring = function(s) {
    if (s.length === 0) {
        return 0;
    }
    let res = 0;
    let left = 0;
    let set = new Set();
    
    for (let i = 0; i < s.length; i++) {
        while (set.has(s[i])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[i]);
        res = Math.max(res, set.size)
    }
    
    return res;
};

/*
Sliding Window
--------------------------------
1. Create a set.
2. Iterate over string.
3. While [i] char is already in set -> remove set[left] and left++.
4. Add s[i] to the set.
5. Update max result.
6. Return result.
--------------------------------
Time: O(n) | Space: O(n)
*/

// 209. Minimum Size Subarray Sum

// Time: O(n) | Space: O(1)
var minSubArrayLen = function(target, nums) {
    let sum = 0;
    let start = 0;
    let min = Infinity;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        while (sum >= target) {
            min = Math.min(min, i - start + 1);
            sum -= nums[start];
            start++;
        }
    }
    return min === Infinity ? 0 : min;
};

/*
Sliding Window
-----------------------
1. Iterate over. 
2. Count sum from the [start] to [i].
3. While sum >= target -> move [start] and reduce count.
4. Check min possible combination length.
5. Return min as a result.
-----------------------
Time: O(n) | Space: O(1)
*/

// 904. Fruit Into Baskets

// Time: O(n) | Space: O(1)
var totalFruit = function(fruits) {
    let left = 0;
    let max = 0;
    let char;
    const map = new Map();
    for (let i = 0; i < fruits.length; i++) {
        char = fruits[i];
        map.set(char, map.get(char) + 1 || 1);
        while (map.size > 2) {
            char = fruits[left];
            map.set(char, map.get(char) - 1);
            if (map.get(char) === 0) {
                map.delete(char);
            }
            left++;
        }
        max = Math.max(max, i + 1 - left);
    }
    return max;
}

/*
Sliding Window
-----------------------
1. Iterate over fruits.
2. Increase counter for 2 types in map.
3. While map has more then 2 types -> reduce [left] type counter.
4. Check max after the while loop.
5. Return max.
-----------------------
Time: O(n) | Space: O(1)
*/

// 567. Permutation in String

// Time: O(n) | Space: O(n)
var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) {
        return false;
    }
    let s1Map = new Map();
    let left = 0;
    let char;

    for (let i = 0; i < s1.length; i++) {
        char = s1[i];
        s1Map.set(char, s1Map.get(char) + 1 || 1);
    }
    
    let count = s1Map.size;
    
    for (let i = 0; i < s2.length; i++) {
       char = s2[i];
        if (s1Map.has(char)) {
            s1Map.set(char, s1Map.get(char) - 1);
        }
        if (s1Map.get(char) === 0) {
            count--;
        }
        while (count === 0) {
            if (i + 1 - left === s1.length) {
                return true;
            }
            char = s2[left];
            if (s1Map.has(char)) {
                s1Map.set(char, s1Map.get(char) + 1);
            }
            if (s1Map.get(char) === 1) {
                count++;
            }
            left++;
        }
    }
    
    return false;
};

/*
Sliding Window + Hash Map
-------------------------------
1. Create s1 chars frequency map.
2. Set count as frequency map size.
3. Iterate over s2 and reduce frwquency in s1 map.
4. Once char frequency === 0 -> reduce count.
5. while count === 0 
5.1. if i + 1 - left === s1.length -> return true (result found).
5.2. All left char to the frequency (if map has this char).
5.3. if char frequency === 1 -> count++.
5.4. Move left pointer.
6. Return false if result not found.
-------------------------------
Time: O(n) | Space: O(n)
*/

// 1423. Maximum Points You Can Obtain from Cards

// Time: O(n) | Space: O(1)
var maxScore = function(cardPoints, k) {
    let start = k - 1;
    let end = cardPoints.length - k;
    let windowVal = 0;
    let max = 0;
    for (let i = start; i >= 0; i--) {
        max += cardPoints[i];
    }
    windowVal = max;
    for (let i = cardPoints.length - 1; i >= end; i--) {
        windowVal += cardPoints[i] - cardPoints[start];
        max = Math.max(max, windowVal);
        start--;
    }
    return max;
};

/*
Sliding Window
----------------------
1. Set start as k-1;
2. Set end as points.length - k;
3. Iterate from start to 0. Count first max.
4. Iterate from length-1 to end. Decrease windowVal by [start] and increase by [i]  
5. Check max for every window step.
6. Return max;
----------------------
Time: O(n) | Space: O(1)
*/

// 76. Minimum Window Substring

// Time: O(n + m) | Space: O(m)
var minWindow = function(s, t) {
    const frequency = t.split('').reduce((acc, char) => {
        acc[char] = ++acc[char] || 1;
        return acc;
    }, {});
    let left = 0;
    let right = 0;
    let count = t.length;
    let minWindowLength = Infinity;
    let minWindowStartIndex = 0;
    let char;
    while (right < s.length) {
        char = s[right];
        if (char in frequency) {
            if (frequency[char] > 0) {
                count--;
            }
            frequency[char]--;
        }
        right++;
        while (count === 0) {
            if ((right - left) < minWindowLength) {
                minWindowLength = right - left;
                minWindowStartIndex = left;
            }
            char  = s[left];
            if (char in frequency) {
                frequency[char]++;
                if (frequency[char] > 0) {
                    count++;
                }
            }
            left++;
        }
    }
    if (minWindowLength === Infinity) {
        return '';
    }
    return s.substring(minWindowStartIndex, minWindowStartIndex + minWindowLength);
};

/*
Two Pointers | Sliding Window
------------------------
1. Create frequency map.
2. Left and right pointers to zero.
3. Count to t.length.
4. minWindowLength to Infinity and minWindowStartIndex to 0 for the result.
5. Iterate from right to s.length.
6. If s[right] in frequency -> we need to check this char.
6.1. If frequency[s[right]] > 0 -> we should count it as a part of the window
6.1.1. count-- -> reduce count -> we are closer to window to be found.
6.2. frequency[s[right]]-- -> minus one char to be checked in the string.
6.3. right++ -> go to the next char in the string.
6.4. while (count === 0) -> we found the window and now we are searching for the min solution.
6.4.1. if (right - left < minWindowLength) -> current solution is closer to the searched result.
6.4.1.1 save current window length and start index.
6.4.2. if s[left] in frequency -> this char might affect count.
6.4.2.1. frequency[s[left]]++ -> keep frequency actual to be able to move left pointer.
6.4.2.2. if (frequency[s[left]] > 0) -> increase count. The window is broken and we will return to our right pointer.
6.4.3. left++ -> move right pointer after all checks.
7. If minWindowLength is still Infinity -> no results found -> return empty line.
8. If not Infinity -> return substring from minWindowStartIndex to index + window length. 
------------------------
Time: O(n + m) -> n for [s] iteration and m for [t] frequency map creation.
Space: O(m) -> to initialize frequency map.
*/

// 424. Longest Repeating Character Replacement

// Time: O(n) | Space: O(1)
var characterReplacement = function(s, k) {
    let left = 0;
    let result = 0;
    let frequencyMap = new Map();
    let maxFrequency = 0;
    let windowSize = 0;
    let char;
    
    for (let i = 0; i < s.length; i++) {
        char = s[i];
        frequencyMap.set(char, frequencyMap.get(char) + 1 || 1);
        maxFrequency = Math.max(maxFrequency, frequencyMap.get(char));
        windowSize = i + 1 - left;
        while (windowSize - maxFrequency > k) {
            char = s[left];
            frequencyMap.set(char, frequencyMap.get(char) - 1);
            left++;
            windowSize = i + 1 - left;
        }
        result = Math.max(result, windowSize);
    }
    return result;
};

/*
Sliding Window
------------------------
1. Iterate over s.
2. Increacy current char frequency in the map.
3. Use max frequency length to move window.
4. If windowSize - maxFrequency > k
4.1. Reduce the left char frequency.
4.2. Move left.
4.3. Reset windowSize.
5. Check max between current result and windowSize.
6. Return result.
------------------------
Time: O(n) | Space: O(1)
*/

// 239. Sliding Window Maximum

// Time: O(n) | Space: O(k)
var maxSlidingWindow = function(nums, k) {
  if (!nums.length) return [];
  if (k === 1) return nums;

  const output = [];
  const dq = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove out of the current window element index.
    while (dq.length && dq[0] <= i - k) {
      dq.shift();
    }
    // Maintaining the deque in decreasing order of elements.
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
      dq.pop();
    }
    // Add current index to the queue.
    dq.push(i);
    if (i >= k - 1) {
      // Push current window max value to the result.
      output.push(nums[dq[0]]);
    }
  }

  return output;
};

/*
Sliding Window
-------------------------
1. Use queue.
2. Keep in queue only elements indexes values of which are bigger than current val.
-------------------------
Time: O(n) | Space: O(k)
*/

https://leetcode.com/problems/sliding-window-maximum/solutions/2273663/javascript-sliding-window-applying-pattern-to-this-problem/comments/1556277

// 438. Find All Anagrams in a String

// Time: O(n) | Space: O(k)
var findAnagrams = function(s, p) {
    const initMap = p.split('').reduce((res, char) => {
        res[char] = ++res[char] || 1;
        return res;
    }, {});
    let map = { ...initMap };
    let count = p.length;
    const output = [];
    let left = 0;
    let right = 0;
    let char;
    
    while (right < s.length) {
        char = s[right];
        if (char in map) {
            if (map[char] > 0) {
                count--;
            }
            map[char]--;
            if (count === 0) {
                output.push(left);
            }
            if (right + 1 - left >= p.length) {
                char = s[left];
                if (map[char] >= 0) {
                    count++;
                }
                map[char]++;
                left++;
            }
        } else {
            left = right + 1;
            count = p.length;
            map = { ...initMap };
        }
        right++;
    }
    
    return output;
};

/*
Sliding Window
------------------------
1. Create p frequency map.
2. Iterate over s.
3. While char matches -> decrease count.
4. If count === 0 -> save left pointer.
5. If char does not match -> reset left, count, frequency.
6. Return result.
------------------------
Time: O(n) | Space: O(k)
*/