Skip to content

03. Sliding-Window#

Theory#

Description#

The Sliding Window is a popular algorithmic technique used to efficiently solve problems involving sequences (arrays or lists) or strings. It is commonly applied in problems where a contiguous block of elements in an array or a string needs to be examined, especially when the window size is either fixed or dynamic.

1. Fixed Size Sliding Window#

In a Fixed Size Sliding Window, the window size is predetermined and does not change during the traversal of the sequence. The window moves step-by-step across the sequence, adjusting its position by adding the next element into the window and removing the element that is no longer in the window's range.

Key Idea#

  • The window size remains constant throughout the process.
  • The window moves from the beginning of the sequence to the end, sliding one element at a time.
  • At each step, the next element is added, and the element that is no longer within the window is removed.

Example#

Maximum Sum Subarray of Size k
Given an array of integers and a number k, find the maximum sum of a subarray of size k.
Input

Array: [2, 1, 5, 1, 3, 2], k = 3
Process
1. Start with the first window of size k. The window is [2, 1, 5] with sum 8.
2. Slide the window one element to the right: remove 2, add 1. The window is now [1, 5, 1] with sum 7.
3. Slide the window one more time: remove 1, add 3. The window is now [5, 1, 3] with sum 9.
4. Slide the window again: remove 5, add 2. The window is now [1, 3, 2] with sum 6. 5. The maximum sum of any subarray of size 3 is 9.

Time Complexity
O(n), because you only need to traverse the array once and perform constant-time operations for each slide (removing one element and adding another).

2. Dynamic Size Sliding Window#

In a Dynamic Size Sliding Window, the size of the window can change based on some condition. The window grows or shrinks dynamically as you traverse the sequence, making it ideal for problems where the window needs to adjust based on constraints or conditions.

Key Idea#

  • The window expands or contracts depending on certain conditions.
  • The size of the window is not fixed and can change during traversal.
  • You may expand the window when you meet a certain condition or contract it when a constraint is violated.

Example#

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Input

String: "abcabcbb"
Process
1. Start with an empty set and begin with the first character 'a'. The window is now "a".
2. Move to the next character 'b'. The window is now "ab".
3. Move to the next character 'c'. The window is now "abc".
4. Move to the next character 'a'. Since 'a' is a duplicate, shrink the window from the left by removing 'a'. The window is now "bc".
5. Continue this process. The longest substring without repeating characters in this case is "abc", and its length is 3.

Time Complexity
O(n), because each character is added and removed from the window at most once.

Key Differences Between Fixed and Dynamic Sliding Windows#

  1. Window Size:

    • Fixed Size: The window size is constant throughout the problem.
    • Dynamic Size: The window size can change dynamically as per the problem’s requirements.

  2. Problem Types:

    • Fixed Size: Problems often involve fixed-size subarrays or subsegments.
    • Dynamic Size: Problems often involve adjusting the window to satisfy certain constraints or conditions.

  3. Movement of Window:

    • Fixed Size: The window moves one step at a time, adding a new element and removing the old one.
    • Dynamic Size: The window can both grow and shrink, depending on whether the window satisfies certain conditions.

  4. Applications:

    • Fixed Size: Often used for problems involving sums, averages, or statistics on fixed-length subarrays.
    • Dynamic Size: Often used for problems involving string patterns, constraints like sum or distinct elements, or longest subsequences.

Summary#

  • Fixed Size Sliding Window is used when you need to consider subarrays of a fixed size as you traverse the array or string.
  • Dynamic Size Sliding Window is used when the size of the window is flexible and changes depending on some condition, often involving optimization or constraint satisfaction.

Both techniques provide an efficient way to solve problems in linear time, as they avoid recomputing sums or other calculations from scratch every time the window moves. Instead, they update values incrementally as the window slides, making them highly effective for problems involving sequences.

Templates#

Fixed-Size Window Template#

Use when the subarray/substring length is always k.

def fixed_window(nums, k):
    window_sum = sum(nums[:k])          # build first window
    best = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # slide: add right, drop left
        best = max(best, window_sum)

    return best

Pattern: right expands one step; once right - left + 1 > k, drop nums[left] and move left.

Variable-Size Window Template#

Use when the window grows/shrinks based on a constraint (distinct count, sum, character frequency, etc.).

def variable_window(s):
    left = 0
    state = {}          # freq map, set, or running sum
    best = 0

    for right in range(len(s)):
        # expand: include s[right] in state
        state[s[right]] = state.get(s[right], 0) + 1

        while window_invalid(state):    # shrink until valid again
            state[s[left]] -= 1
            if state[s[left]] == 0:
                del state[s[left]]
            left += 1

        best = max(best, right - left + 1)   # or update answer while valid

    return best

Pattern: expand right greedily; while the window breaks the rule, shrink from left. Each index enters and leaves at most once → O(n).

Problems at a glance#

LC Problem
643 1. Maximum Average Subarray I ↗
1876 2. Substrings of Size Three with Distinct Characters ↗
1297 3. Maximum Number of Occurrences of a Substring ↗
2090 4. K Radius Subarray Averages ↗
1695 5. Maximum Erasure Value ↗
1343 6. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold ↗
567 7. Permutation in String ↗
1423 8. Maximum Points You Can Obtain from Cards ↗
239 9. Sliding Window Maximum ↗
480 10. Sliding Window Median ↗
992 11. Subarrays with K Different Integers ↗
76 12. Minimum Window Substring ↗
438 13. Find All Anagrams in a String ↗
2461 14. Maximum Sum of Distinct Subarrays With Length K ↗
30 15. Substring with Concatenation of All Words ↗

Problems#

1. Maximum Average Subarray I (Leetcode:643)#

Problem Statement

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.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:

        max_sum = curr_sum = sum(nums[:k])

        for i in range(k, len(nums)):
            curr_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, curr_sum)

        return max_sum / k
Explanation:

  1. Build the first window: Sum the first k elements — this is both curr_sum and initial max_sum.
  2. Slide the window: For each new index i, add nums[i] and subtract nums[i - k] (the element leaving the window).
  3. Track maximum: Update max_sum at every slide.
  4. Return average: Divide by k at the end (avoids floating-point drift from repeated division).

Time: O(n)  |  Space: O(1)

1
2
3
4
5
6
7
8
9
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_sum = sum(nums[:k])

        for i in range(1, len(nums) - k + 1):
            window_sum = sum(nums[i:i + k])
            max_sum = max(max_sum, window_sum)

        return max_sum / k
Explanation:

  1. Enumerate every window: For each start index i, recompute the sum of nums[i:i + k] from scratch.
  2. Track maximum: Keep the largest window sum seen.
  3. Return average: Divide the best sum by k.

Time: O(n × k)  |  Space: O(1) — correct but recomputes each window; Approach 1 is preferred.

2. Substrings of Size Three with Distinct Characters (Leetcode:1876)#

Problem Statement

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

1 <= s.length <= 100
s​​​​​​ consists of lowercase English letters.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        if len(s) < 3:
            return 0

        count = 0
        seen = set(s[:3])
        if len(seen) == 3:
            count += 1

        for i in range(3, len(s)):
            seen.add(s[i])
            seen.discard(s[i - 3])
            if len(seen) == 3:
                count += 1

        return count
Explanation:

  1. Fixed window of size 3: Build the first window s[0:3] in a set.
  2. Check distinctness: A good substring has exactly 3 unique characters → len(seen) == 3.
  3. Slide: Add s[i], remove s[i - 3], recount when the window moves.
  4. Increment answer each time the window is good.

Time: O(n)  |  Space: O(1) — alphabet size is bounded (26 letters)

1
2
3
4
5
6
7
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s) - 2):
            if s[i] != s[i + 1] and s[i] != s[i + 2] and s[i + 1] != s[i + 2]:
                count += 1
        return count
Explanation:

  1. Window size is always 3, so no sliding state is needed — just check each triplet.
  2. Distinctness test: All three pairwise comparisons must differ.
  3. No extra space — simplest solution for this small fixed window.

Time: O(n)  |  Space: O(1)

1
2
3
4
5
6
7
8
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0

        for x, y, z in zip(s, s[1:], s[2:]):
            if x != y and y != z and x != z:
                count += 1
        return count
Explanation:

  1. zip(s, s[1:], s[2:]) yields every length-3 substring as (x, y, z) without manual indexing.
  2. Same distinctness check as Approach 2 — equivalent logic, more Pythonic syntax.

Time: O(n)  |  Space: O(1)

3. Maximum Number of Occurrences of a Substring (Leetcode:1297)#

Problem Statement

Given a string s, return the maximum number of occurrences of any substring under the following rules:

  • The number of unique characters in the substring must be less than or equal to maxLetters.
  • The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Constraints:

1 <= s.length <= 105
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.

Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = {}
        for i in range(len(s) - minSize + 1):
            substr = s[i:i + minSize]
            if len(set(substr)) <= maxLetters:
                freq[substr] = freq.get(substr, 0) + 1

        return max(freq.values(), default=0)
Explanation:

  1. Key insight: If a longer valid substring exists, its length-minSize prefix occurs at least as often — so only check windows of size minSize.
  2. Slide fixed windows of length minSize across s.
  3. Filter by unique letters: Count only substrings with <= maxLetters distinct characters.
  4. Return max frequency from the hash map.

Time: O(n × minSize)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = {}
        distinct = 0
        counts = {}

        for i in range(minSize):
            counts[s[i]] = counts.get(s[i], 0) + 1
        distinct = len(counts)

        if distinct <= maxLetters:
            freq[s[:minSize]] = 1

        for i in range(minSize, len(s)):
            counts[s[i]] = counts.get(s[i], 0) + 1
            if counts[s[i]] == 1:
                distinct += 1

            out_char = s[i - minSize]
            counts[out_char] -= 1
            if counts[out_char] == 0:
                distinct -= 1
                del counts[out_char]

            if distinct <= maxLetters:
                substr = s[i - minSize + 1:i + 1]
                freq[substr] = freq.get(substr, 0) + 1

        return max(freq.values(), default=0)
Explanation:

  1. Maintain a running frequency map instead of rebuilding set(substr) each slide.
  2. Track distinct — increment when a char count goes 0→1, decrement when 1→0.
  3. Slide in O(1) per step by adding the right char and removing the left char.
  4. Same minSize-only insight as Approach 1; avoids repeated set construction.

Time: O(n × minSize) for substring key storage  |  Space: O(n)

4. K Radius Subarray Averages (Leetcode:2090)#

Problem Statement

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.

Example 2:

Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
avg[0] = 100000 / 1 = 100000.

Example 3:

Input: nums = [8], k = 100000
Output: [-1]
Explanation:
- avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

n == nums.length 1 <= n <= 10^5 0 <= nums[i], k <= 10^5

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:

        window_size = 2 * k + 1
        n = len(nums)

        if n < window_size:
            return [-1] * n

        curr_sum = sum(nums[:window_size])
        avgs = [-1] * k
        avgs.append(curr_sum // window_size)

        for i in range(k + 1, n - k):
            curr_sum += nums[i + k] - nums[i - k - 1]
            avgs.append(curr_sum // window_size)

        for _ in range(k):
            avgs.append(-1)

        return avgs
Explanation:

  1. Fixed window size 2k + 1 — centered at index i, covers [i-k, i+k].
  2. Edge indices (first/last k positions) cannot fit the full window → -1.
  3. Build first valid average at center index k, then slide: add nums[i+k], drop nums[i-k-1].
  4. Integer division truncates toward zero as required.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:

        if k == 0:
            return nums

        window_size = 2 * k + 1
        n = len(nums)
        avgs = [-1] * n

        if n < window_size:
            return avgs

        window_sum = sum(nums[:window_size])
        avgs[k] = window_sum // window_size

        for i in range(window_size, n):
            window_sum += nums[i] - nums[i - window_size]
            avgs[i - k] = window_sum // window_size

        return avgs
Explanation:

  1. Initialize avgs with -1 — only overwrite valid center indices.
  2. Slide using right index i: window ending at i corresponds to center i - k.
  3. k == 0 edge case: each element is its own average.
  4. Cleaner index mapping — window [i - window_size + 1, i] centers at i - k.

Time: O(n)  |  Space: O(n)

5. Maximum Erasure Value (Leetcode:1695)#

Problem Statement

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()
        left = 0
        curr_sum = 0
        best = 0

        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                curr_sum -= nums[left]
                left += 1

            seen.add(nums[right])
            curr_sum += nums[right]
            best = max(best, curr_sum)

        return best
Explanation:

  1. Variable window — expand right; shrink left while a duplicate exists.
  2. Set tracks uniqueness — if nums[right] is already in the window, remove from the left until it is gone.
  3. Track running sum and maximize over all valid windows.
  4. Each element is added/removed at most once → O(n).

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        last_seen = {}
        left = 0
        curr_sum = 0
        best = 0

        for right, num in enumerate(nums):
            if num in last_seen and last_seen[num] >= left:
                while left <= last_seen[num]:
                    curr_sum -= nums[left]
                    left += 1

            last_seen[num] = right
            curr_sum += num
            best = max(best, curr_sum)

        return best
Explanation:

  1. last_seen maps each value to its most recent index.
  2. On duplicate inside window: jump left past the previous occurrence, subtracting elements along the way.
  3. No set needed — index bookkeeping alone maintains uniqueness.
  4. Each index moves forward at most once → O(n) time and O(n) space.

Time: O(n)  |  Space: O(n)

6. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Leetcode:1343)#

Problem Statement

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        window_sum = sum(arr[:k])
        count = 1 if window_sum >= k * threshold else 0

        for i in range(k, len(arr)):
            window_sum += arr[i] - arr[i - k]
            if window_sum >= k * threshold:
                count += 1

        return count
Explanation:

  1. Avoid floating point: Compare window_sum >= k * threshold instead of window_sum / k >= threshold.
  2. Build first window of size k, check if its average meets the threshold.
  3. Slide by adding arr[i] and dropping arr[i - k], increment count when valid.

Time: O(n)  |  Space: O(1)

1
2
3
4
5
6
7
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        count = 0
        for i in range(len(arr) - k + 1):
            if sum(arr[i:i + k]) / k >= threshold:
                count += 1
        return count
Explanation:

  1. Enumerate every subarray of length k and compute its average directly.
  2. Correct but recomputes sums each time — O(n × k).

Time: O(n × k)  |  Space: O(1)

7. Permutation in String (Leetcode:567)#

Problem Statement

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.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        k = len(s1)
        need = [0] * 26
        window = [0] * 26

        for c in s1:
            need[ord(c) - ord('a')] += 1

        for i in range(len(s2)):
            window[ord(s2[i]) - ord('a')] += 1

            if i >= k:
                window[ord(s2[i - k]) - ord('a')] -= 1

            if window == need:
                return True

        return False
Explanation:

  1. Fixed window of size len(s1) slides across s2.
  2. need stores character counts of s1; window tracks the current window's counts.
  3. When window == need, the current substring is a permutation of s1.
  4. Slide by incrementing the incoming char and decrementing the outgoing char.

Time: O(n)  |  Space: O(1) — 26-letter alphabet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        k = len(s1)
        need = Counter(s1)
        window = Counter(s2[:k - 1])
        matches = 0
        required = len(need)

        for i in range(k - 1, len(s2)):
            right = s2[i]
            window[right] += 1
            if window[right] == need.get(right, 0):
                matches += 1
            elif window[right] == need.get(right, 0) + 1:
                matches -= 1

            if i >= k:
                left = s2[i - k]
                window[left] -= 1
                if window[left] == need.get(left, 0):
                    matches += 1
                elif window[left] == need.get(left, 0) - 1:
                    matches -= 1

            if matches == required:
                return True

        return False
Explanation:

  1. Track how many characters have matching counts instead of comparing full arrays each step.
  2. matches == required means every character frequency in the window equals s1.
  3. Avoids O(26) array comparison per slide — useful when alphabet is large.

Time: O(n)  |  Space: O(1)

8. Maximum Points You Can Obtain from Cards (Leetcode:1423)#

Problem Statement

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        window_size = n - k
        total = sum(cardPoints)

        if window_size == 0:
            return total

        window_sum = sum(cardPoints[:window_size])
        min_sum = window_sum

        for i in range(window_size, n):
            window_sum += cardPoints[i] - cardPoints[i - window_size]
            min_sum = min(min_sum, window_sum)

        return total - min_sum
Explanation:

  1. Reframe the problem: Taking k cards from the ends = leaving a contiguous middle subarray of length n - k.
  2. Maximize end picks = minimize the sum of the untouched middle segment.
  3. Fixed window of size n - k slides across the array; track the minimum window sum.
  4. Answer = total - min_middle_sum.

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        prefix = [0]
        for x in cardPoints:
            prefix.append(prefix[-1] + x)

        best = 0
        for left_take in range(k + 1):
            right_take = k - left_take
            score = prefix[left_take] + (prefix[-1] - prefix[len(cardPoints) - right_take])
            best = max(best, score)

        return best
Explanation:

  1. Build prefix sums so any segment sum is O(1).
  2. Try all splits: take left_take from the front and right_take = k - left_take from the back.
  3. No sliding window, but the same O(n) insight — enumerate the k + 1 ways to partition picks.

Time: O(n)  |  Space: O(n)

9. Sliding Window Maximum (Leetcode:239)#

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window.
Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position Max
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # indices; front = max of current window
        result = []

        for i, num in enumerate(nums):
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            dq.append(i)

            if dq[0] <= i - k:
                dq.popleft()

            if i >= k - 1:
                result.append(nums[dq[0]])

        return result
Explanation:

  1. Deque stores indices in decreasing value order — front is always the window maximum.
  2. Before adding i: pop from the back while values are <= nums[i] (they can never become max).
  3. Remove expired index from the front when it leaves the window (i - k).
  4. Record max once the first full window forms at index k - 1.

Time: O(n)  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = []
        result = []

        for i, num in enumerate(nums):
            heappush(heap, (-num, i))

            if i >= k - 1:
                while heap[0][1] <= i - k:
                    heappop(heap)
                result.append(-heap[0][0])

        return result
Explanation:

  1. Store (-value, index) in a min-heap — largest value sits at the top.
  2. Lazy deletion: Before reading the max, pop entries whose index is outside the window.
  3. Simpler to write than a deque, but heap can hold stale entries → amortized O(n log n).

Time: O(n log n)  |  Space: O(n)

10. Sliding Window Median (Leetcode:480)#

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

For examples, if arr = [2,3,4], the median is 3.
For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:

Window position Median
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Constraints:

1 <= k <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        small = []  # max-heap (negated) — lower half
        large = []  # min-heap — upper half
        result = []

        def rebalance():
            if len(small) > len(large) + 1:
                heappush(large, -heappop(small))
            elif len(large) > len(small):
                heappush(small, -heappop(large))

        def add(num):
            heappush(small, -num)
            heappush(large, -heappop(small))
            rebalance()

        def remove(num):
            if num <= -small[0]:
                small.remove(-num)
                heapify(small)
            else:
                large.remove(num)
                heapify(large)
            rebalance()

        for i, num in enumerate(nums):
            add(num)
            if i >= k:
                remove(nums[i - k])
            if i >= k - 1:
                if k % 2:
                    result.append(float(-small[0]))
                else:
                    result.append((-small[0] + large[0]) / 2.0)

        return result
Explanation:

  1. Two heaps maintain the lower and upper halves of the window — median is O(1) to read.
  2. add pushes to small, balances one element to large, then rebalances sizes.
  3. remove deletes the outgoing element (lazy heapify after list removal).
  4. Odd k: median = top of small; even k: average of both tops.

Time: O(n log k)  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from sortedcontainers import SortedList

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        window = SortedList(nums[:k])
        result = []

        for i in range(k, len(nums) + 1):
            if k % 2:
                result.append(float(window[k // 2]))
            else:
                result.append((window[k // 2 - 1] + window[k // 2]) / 2.0)

            if i < len(nums):
                window.remove(nums[i - k])
                window.add(nums[i])

        return result
Explanation:

  1. SortedList keeps the window sorted — insert/remove in O(log k).
  2. Median by index: window[k // 2] for odd windows; average two middle elements for even.
  3. Cleaner code than dual heaps; requires the sortedcontainers library.

Time: O(n log k)  |  Space: O(k)

11. Subarrays with K Different Integers (Leetcode:992)#

Problem Statement

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

1 <= nums.length <= 2 * 10^4
1 <= nums[i], k <= nums.length

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def at_most(k):
            count = {}
            left = 0
            result = 0

            for right, num in enumerate(nums):
                count[num] = count.get(num, 0) + 1

                while len(count) > k:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        del count[nums[left]]
                    left += 1

                result += right - left + 1

            return result

        return at_most(k) - at_most(k - 1)
Explanation:

  1. Exactly K distinct = at most K minus at most K−1 — classic sliding-window decomposition.
  2. at_most(k) counts every subarray with <= k distinct integers by adding right - left + 1 valid windows ending at right.
  3. Shrink from left when distinct count exceeds k.
  4. Each index enters/leaves the window once → O(n) per call.

Time: O(n)  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        count = {}
        left = 0
        result = 0

        for right, num in enumerate(nums):
            count[num] = count.get(num, 0) + 1

            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1

            if len(count) == k:
                temp = left
                while temp < right and count[nums[temp]] > 1:
                    count[nums[temp]] -= 1
                    temp += 1
                result += temp - left + 1

        return result
Explanation:

  1. When the window has exactly k distinct elements, shrink from the left while duplicates allow — each duplicate prefix gives another valid subarray ending at right.
  2. More intricate than the atMost trick but avoids two passes.
  3. Still O(n) because temp only moves forward across the whole run.

Time: O(n)  |  Space: O(k)

12. Minimum Window Substring (Leetcode:76)#

Problem Statement

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.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        need = Counter(t)
        window = {}
        have, required = 0, len(need)
        left = 0
        best_len = float('inf')
        best_start = 0

        for right, char in enumerate(s):
            window[char] = window.get(char, 0) + 1

            if char in need and window[char] == need[char]:
                have += 1

            while have == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_start = left

                left_char = s[left]
                window[left_char] -= 1
                if left_char in need and window[left_char] < need[left_char]:
                    have -= 1
                left += 1

        return "" if best_len == float('inf') else s[best_start:best_start + best_len]
Explanation:

  1. need = required char counts from t; have tracks how many distinct chars meet their quota.
  2. Expand right: increment window counts; when a char hits its exact need, increment have.
  3. While have == required: window is valid — record minimum, then shrink from left until invalid.
  4. Variable window finds the smallest valid substring in O(m + n).

Time: O(m + n)  |  Space: O(1) — bounded alphabet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        filtered = [(i, c) for i, c in enumerate(s) if c in need]
        if not filtered:
            return ""

        required = len(need)
        have = 0
        counts = {}
        left = 0
        best_len = float('inf')
        best = (0, 0)

        for right in range(len(filtered)):
            char = filtered[right][1]
            counts[char] = counts.get(char, 0) + 1
            if counts[char] == need[char]:
                have += 1

            while have == required:
                start, end = filtered[left][0], filtered[right][0]
                if end - start + 1 < best_len:
                    best_len = end - start + 1
                    best = (start, end + 1)

                left_char = filtered[left][1]
                counts[left_char] -= 1
                if counts[left_char] < need[left_char]:
                    have -= 1
                left += 1

        return s[best[0]:best[1]] if best_len != float('inf') else ""
Explanation:

  1. Pre-filter s to only chars in t — skips irrelevant characters between matches.
  2. Run the same expand/shrink logic on the filtered list, mapping back to original indices.
  3. Useful when t is small and s is large with many irrelevant chars.

Time: O(m + n)  |  Space: O(m)

13. Find All Anagrams in a String (Leetcode:438)#

Problem Statement

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.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2: Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        k = len(p)
        need = [0] * 26
        window = [0] * 26
        result = []

        for c in p:
            need[ord(c) - ord('a')] += 1

        for i in range(len(s)):
            window[ord(s[i]) - ord('a')] += 1

            if i >= k:
                window[ord(s[i - k]) - ord('a')] -= 1

            if i >= k - 1 and window == need:
                result.append(i - k + 1)

        return result
Explanation:

  1. Fixed window of size len(p) slides across s.
  2. Compare 26-element frequency arrays — an exact match means the window is an anagram of p.
  3. Record the start index i - k + 1 whenever counts match.

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        k = len(p)
        need = Counter(p)
        window = Counter()
        matches = 0
        required = len(need)
        result = []

        for i in range(len(s)):
            right = s[i]
            window[right] += 1
            if window[right] == need.get(right, 0):
                matches += 1
            elif window[right] == need.get(right, 0) + 1:
                matches -= 1

            if i >= k:
                left = s[i - k]
                window[left] -= 1
                if window[left] == need.get(left, 0):
                    matches += 1
                elif window[left] == need.get(left, 0) - 1:
                    matches -= 1

            if i >= k - 1 and matches == required:
                result.append(i - k + 1)

        return result
Explanation:

  1. Same fixed-window slide, but track matches (how many chars have correct frequency) instead of full array compare.
  2. matches == required signals an anagram — O(1) check per slide.
  3. Same pattern as Permutation in String (LC 567), collecting all start indices instead of early return.

Time: O(n)  |  Space: O(1)

14. Maximum Sum of Distinct Subarrays With Length K (Leetcode:2461)#

Problem Statement

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

  • The length of the subarray is k, and
  • All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        counts = {}
        window_sum = 0
        best = 0

        for i, num in enumerate(nums):
            counts[num] = counts.get(num, 0) + 1
            window_sum += num

            if i >= k:
                out = nums[i - k]
                counts[out] -= 1
                if counts[out] == 0:
                    del counts[out]
                window_sum -= out

            if i >= k - 1 and len(counts) == k:
                best = max(best, window_sum)

        return best
Explanation:

  1. Fixed window of size k slides across nums.
  2. Distinct check: len(counts) == k means no duplicates in the window.
  3. Track window sum incrementally; update best only when the distinctness constraint holds.
  4. Return 0 if no valid window exists (best stays 0).

Time: O(n)  |  Space: O(k)

1
2
3
4
5
6
7
8
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        best = 0
        for i in range(len(nums) - k + 1):
            window = nums[i:i + k]
            if len(set(window)) == k:
                best = max(best, sum(window))
        return best
Explanation:

  1. Enumerate every length-k subarray and check distinctness with a set.
  2. Correct but recomputes sum and set each window — O(n × k).

Time: O(n × k)  |  Space: O(k)

15. Substring with Concatenation of All Words (Leetcode:30)#

Problem Statement

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.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation:
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not words or not s:
            return []

        word_len = len(words[0])
        total_len = word_len * len(words)
        need = Counter(words)
        result = []

        for offset in range(word_len):
            left = offset
            counts = Counter()
            used = 0

            for right in range(offset, len(s) - word_len + 1, word_len):
                word = s[right:right + word_len]

                if word not in need:
                    counts.clear()
                    used = 0
                    left = right + word_len
                    continue

                counts[word] += 1
                used += 1

                while counts[word] > need[word]:
                    left_word = s[left:left + word_len]
                    counts[left_word] -= 1
                    used -= 1
                    left += word_len

                if used == len(words):
                    result.append(left)

        return result
Explanation:

  1. Window moves in word-sized chunks (not char-by-char) — each step adds one word of length word_len.
  2. Try word_len offsets to cover all alignments (words may start at any position mod word_len).
  3. Shrink when a word is over-counted — slide left forward by one word.
  4. used == len(words) means the window contains exactly the right multiset of words.

Time: O(n × word_len)  |  Space: O(num_words)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not words or not s:
            return []

        word_len = len(words[0])
        total_len = word_len * len(words)
        need = Counter(words)
        result = []

        for i in range(len(s) - total_len + 1):
            seen = Counter()
            for j in range(0, total_len, word_len):
                word = s[i + j:i + j + word_len]
                if word not in need:
                    break
                seen[word] += 1
                if seen[word] > need[word]:
                    break
            else:
                if seen == need:
                    result.append(i)

        return result
Explanation:

  1. Fixed window of total_len characters — split into len(words) chunks and compare word counts.
  2. Break early if any chunk is unknown or over-counted.
  3. Simpler to read; re-scans each window from scratch — O(n × total_len).

Time: O(n × total_len)  |  Space: O(num_words)