Course4all
Join us on telegram
Home/dsa/Sliding Window

Sliding Window

Master this topic with zero to advance depth.

Sliding Window Mental Models

The Sliding Window technique is a powerful optimization used to convert O(N2N^2) or O(N3N^3) nested loop problems into O(NN) linear time. It is primarily used for contiguous subarrays or substrings.

1. Fixed Size Window (Static)

The window size k is constant. We slide the window by adding one element from the right and removing one from the left.

Window Size K=3, nums = [1, 2, 3, 4, 5, 6] Step 1: [1, 2, 3], 4, 5, 6 (Sum: 6) Step 2: 1, [2, 3, 4], 5, 6 (Sum: 9) Step 3: 1, 2, [3, 4, 5], 6 (Sum: 12)

2. Variable Size Window (Dynamic)

The window size expands and shrinks based on a condition. We use two pointers: left and right.

Target Sum >= 7, nums = [2, 3, 1, 2, 4, 3] [2, 3, 1], 2, 4, 3 (Sum: 6 < 7, Expand Right) [2, 3, 1, 2], 4, 3 (Sum: 8 >= 7, Valid! Shrink Left) 2, [3, 1, 2], 4, 3 (Sum: 6 < 7, Expand Right)

3. Universal Sliding Window Template (Variable)

Most variable window problems follow this structure:

def sliding_window(nums): left = 0 state = initial_state() res = 0 for right in range(len(nums)): # 1. Expand: Update state with nums[right] update_state(state, nums[right]) # 2. Shrink: While condition is violated while condition_violated(state): remove_from_state(state, nums[left]) left += 1 # 3. Update Result: Window is now valid res = max(res, right - left + 1) return res

4. Common Patterns & Pitfalls

  • State Maintenance: Use a Sum variable for numeric problems, a HashMap for character frequency, or a Deque for window maximums.
  • Shrinking Condition: For "At Most K", shrink when count > K. For "Exactly K", calculate atMost(K) - atMost(K-1).
  • Integer Overflow: When summing large arrays, ensure the Sum variable is a 64-bit integer (e.g., long in Java/C++).
  • Empty String/Array: Always handle edge cases where n < k or the input is empty.

Maximum Sum Subarray of Size K

Given an array of integers nums and a positive integer k, find the maximum sum of any contiguous subarray of size k.

Visual Representation

nums = [2, 1, 5, 1, 3, 2], k = 3 Step 1: [2, 1, 5], 1, 3, 2 (Sum = 8) Step 2: 2, [1, 5, 1], 3, 2 (Sum = 7) Step 3: 2, 1, [5, 1, 3], 2 (Sum = 9) -> MAX Step 4: 2, 1, 5, [1, 3, 2] (Sum = 6)
Easy

Examples

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9

Subarray [5, 1, 3] has the maximum sum of 9.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

The most basic way to solve this is to check every possible contiguous subarray of size k and calculate its sum. We keep track of the maximum sum found so far.

Thought Process

  1. Iterate through every possible starting index i from 0 to n - k.
  2. For each i, start another loop to sum up the next k elements.
  3. Update maxSum if the current subarray sum is larger.

Pattern Identification

This is a Naive Search pattern. We are re-calculating the sum for overlapping parts of subarrays, which is the main bottleneck.

⏱ O(N * K)💾 O(1)

Detailed Dry Run

Outer Loop (i)Inner Loop (j)Current SumMax SumAction
00, 1, 22+1+5 = 88Init Max
11, 2, 31+5+1 = 78No Change
22, 3, 45+1+3 = 99Update Max
33, 4, 51+3+2 = 69No Change
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int maxSum = 0;
        int n = nums.length;
        // Iterate through all possible starting points
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            // Sum k elements starting from i
            for (int j = i; j < i + k; j++) {
                currentSum += nums[j];
            }
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println("Max Sum: " + findMaxSum(nums, k)); // Expected: 9
    }
}
Approach 2

Level II: Prefix Sums (O(N) Space)

Intuition

We can precompute a prefix sum array where prefix[i] stores the sum of elements from 0 to i-1. The sum of any subarray nums[i...j] can then be calculated in O(1)O(1) as prefix[j+1] - prefix[i].

Thought Process

  1. Create an array prefix of size n + 1.
  2. Fill prefix such that prefix[i+1] = prefix[i] + nums[i].
  3. Iterate from i = 0 to n - k and calculate sum = prefix[i+k] - prefix[i].
  4. Update maxSum accordingly.

Pattern: Space-Time Tradeoff

This approach reduces the calculation time to O(1)O(1) per subarray but uses O(N)O(N) extra space.

⏱ O(N) - One pass for prefix sum, another for maximums.💾 O(N) - To store the prefix sum array.
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        
        int maxSum = 0;
        for (int i = 0; i <= n - k; i++) {
            maxSum = Math.max(maxSum, prefix[i + k] - prefix[i]);
        }
        return maxSum;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We can observe that two consecutive subarrays of size k share k-1 elements. Instead of re-summing everything, we can 'slide' the window: add the next element (Right) and subtract the element that is no longer in the window (Left).

Pattern: Sliding Window (Fixed Size)

  • Expand: Add nums[right] to windowSum.
  • Shrink/Slide: When right >= k - 1, the window is full. Update the result, then subtract nums[left] and increment left to prepare for the next step.

Mandatory Variables

  • left: Pointer to the start of the window.
  • windowSum: Current sum of the k elements.
  • maxSum: Best sum found so far.
⏱ O(N)💾 O(1)

Detailed Dry Run

StepRightLeftwindowSummaxSumAction
10020Expand
21030Expand
32088Window Full, Update Max
43178Slide (Sub 2, Add 1)
54299Slide (Sub 1, Add 3), Update Max
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int left = 0, windowSum = 0, maxSum = 0;
        for (int right = 0; right < nums.length; right++) {
            // 1. Expand
            windowSum += nums[right];
            
            // 2. Window is full (size k)
            if (right >= k - 1) {
                // 3. Update Result
                maxSum = Math.max(maxSum, windowSum);
                
                // 4. Shrink/Slide
                windowSum -= nums[left];
                left++;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println("Max Sum: " + findMaxSum(nums, k)); // 9
    }
}

Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Visual Representation

target = 7, nums = [2, 3, 1, 2, 4, 3] [2, 3, 1, 2], 4, 3 (Sum: 8 >= 7, Len: 4) 2, [3, 1, 2, 4], 3 (Sum: 10 >= 7, Len: 4) 2, 3, 1, [2, 4, 3] (Sum: 9 >= 7, Len: 3) -> MINIMAL
Medium

Examples

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

The subarray [4,3] has the minimal length under the problem constraint.

Approach 1

Level I: Brute Force (O(N^2))

Intuition

Check all possible subarrays and find the one with sum >= target and minimum length.

Thought Process

  1. Use two nested loops to define every subarray nums[i...j].
  2. Calculate the sum of each subarray.
  3. If sum >= target, update minLen = min(minLen, j - i + 1).

Pattern: Subarray Enumeration

⏱ O(N^2)💾 O(1)
java
public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, minLen = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
Approach 2

Level III: Optimal (Variable Sliding Window)

Intuition

Categorization

This is the classic Variable Size Window problem. We expand the window until the sum meets the target, then shrink from the left to find the smallest valid window.

Thought Process

  1. Maintain a windowSum and a left pointer.
  2. Iterate right from 0 to n-1 (Expand).
  3. Add nums[right] to windowSum.
  4. While windowSum >= target:
    • Update minLen with right - left + 1.
    • Subtract nums[left] from windowSum and increment left (Shrink).

Mandatory Variables

  • left: Pointer to the start of the window.
  • windowSum: Current sum of the window content.
  • minLen: Smallest valid window length found.
⏱ O(N) - Each element is visited at most twice.💾 O(1)

Detailed Dry Run

StepLRwindowSumminLenAction
1002infExpand
2015infExpand
3026infExpand
40384Sum >= 7! Update minLen, Shrink L
51364Sum < 7. Expand R
java
public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Visual Representation

s = "abcabcbb" L R | | a b c a b c b b [---] Set: {a, b, c}, Len: 3 L R | | a b c a b c b b [---] Set: {b, c, a}, Len: 3
Medium

Examples

Input: s = "abcabcbb"
Output: 3

The answer is "abc", with the length of 3.

Approach 1

Level I: Brute Force

Intuition

Check every possible substring and verify if it contains unique characters. A string of length NN has O(N2)O(N^2) substrings. Checking each takes O(N)O(N), leading to O(N3)O(N^3). We can optimize the check using a Set to O(N2)O(N^2).

Thought Process

  1. Use two nested loops to define every potential substring s[i...j].
  2. For each substring, use a third loop or a Set to check for duplicates.
  3. If no duplicates, update the maxLength.
⏱ O(N^2)💾 O(min(N, M)) where M is alphabet size.

Detailed Dry Run

ijSubstringUnique?Max Len
00"a"Yes1
01"ab"Yes2
02"abc"Yes3
03"abca"No3
13"bca"Yes3
java
import java.util.*;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isUnique(s, i, j)) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

    private static boolean isUnique(String s, int start, int end) {
        Set<Character> chars = new HashSet<>();
        for (int k = start; k <= end; k++) {
            if (chars.contains(s.charAt(k))) return false;
            chars.add(s.charAt(k));
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum length k. For a fixed k, we check if there exists any substring of length k with no repeating characters using a fixed-size sliding window. If a valid substring of length k exists, then any length smaller than k is also possible, so we search in [k, right]. Otherwise, we search in [left, k-1].

Thought Process

  1. Search range for maximum length is [1, n].
  2. In each step of binary search (length mid):
    • Use a sliding window of size mid to check for uniqueness.
    • If unique substring found, ans = mid, low = mid + 1.
    • Else, high = mid - 1.

Pattern: Search on Answer Space

⏱ O(N log N) - Binary search takes $\log N$ steps, each check takes $O(N)$.💾 O(min(N, M)) for the character set during the check.
java
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) return 0;
        int low = 1, high = s.length(), ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (hasUnique(s, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean hasUnique(String s, int k) {
        java.util.Map<Character, Integer> window = new java.util.HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (i >= k) {
                char out = s.charAt(i - k);
                window.put(out, window.get(out) - 1);
                if (window.get(out) == 0) window.remove(out);
            }
            if (window.size() == k) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Variable Size Window problem because the length of the unique substring changes as we encounter duplicates.

Thought Process

Instead of checking all substrings, we maintain a sliding window [left, right]. As we expand right, we add the character to a Set. If s[right] is already in the Set, we have a violation. We must shrink the window from the left until the duplicate is gone.

Mandatory Variables

  • left: Marks the start of the current unique substring.
  • charSet: Stores characters in the current window for O(1)O(1) duplicate checking.
  • maxLength: Tracks the largest window size found.
⏱ O(N)💾 O(min(N, M)) where M is the character set size.

Detailed Dry Run

StepLRCharActionSet ContentMax Len
100'a'Add 'a'{a}1
201'b'Add 'b'{a, b}2
302'c'Add 'c'{a, b, c}3
403'a'Dupe 'a'! Shrink L{b, c, a}3
514'b'Dupe 'b'! Shrink L{c, a, b}3
java
import java.util.*;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            // Shrink if duplicate found
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            // Expand
            set.add(s.charAt(right));
            // Update Result
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the window shrink condition. It must be a while loop to remove all characters until the duplicate is gone. Also, remember to add the current character after the shrink loop.

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

Visual Representation

s1 = "ab", s2 = "eidbaooo" Target Count: {a:1, b:1} [e, i] d b a o o o Count: {e:1, i:1} (Mismatch) e [i, d] b a o o o Count: {i:1, d:1} (Mismatch) e i [d, b] a o o o Count: {d:1, b:1} (Mismatch) e i d [b, a] o o o Count: {b:1, a:1} (Matches!)
Medium

Examples

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

s2 contains one permutation of s1 ("ba").

Approach 1

Level I: Brute Force

Intuition

To check if s2 contains a permutation of s1, we can generate all substrings of s2 that have the same length as s1, and then check if that substring is a permutation of s1 (by sorting both and comparing).

Thought Process

  1. Iterate through all substrings of s2 with length equal to s1.length().
  2. For each substring, sort its characters and also sort the characters of s1.
  3. If the sorted strings match, then a permutation exists.
⏱ O(N * M log M) where N is length of s2 and M is length of s1.💾 O(M)

Detailed Dry Run

Window in s2Sorted WindowSorted s1 (ab)Match?
"ei""ei""ab"No
"id""di""ab"No
"db""bd""ab"No
"ba""ab""ab"YES
java
import java.util.*;

public class Main {
    public static boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;

        char[] s1Chars = s1.toCharArray();
        Arrays.sort(s1Chars);
        String sortedS1 = new String(s1Chars);

        for (int i = 0; i <= n2 - n1; i++) {
            String sub = s2.substring(i, i + n1);
            char[] subChars = sub.toCharArray();
            Arrays.sort(subChars);
            if (new String(subChars).equals(sortedS1)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
        System.out.println(checkInclusion("ab", "eidboaoo")); // false
    }
}
Approach 2

Level II: Frequency Counter (O(N * 26))

Intuition

Instead of sorting, we can compare character frequency maps. This is still a 'sliding' concept but we re-build or re-check the entire map of size 26 for each window. Since the alphabet size is constant (26), this is technically O(N * 26).

Thought Process

  1. Count frequencies of characters in s1.
  2. Iterate through s2 and for every window of size s1.length(), build a new frequency map.
  3. Compare the window's map with s1's map.

Pattern: Frequency Hashing

⏱ O(N * 26) where N is length of s2.💾 O(26) for the frequency array.
java
public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;
        int[] s1Count = new int[26];
        for (char c : s1.toCharArray()) s1Count[c - 'a']++;

        for (int i = 0; i <= n2 - n1; i++) {
            int[] s2Count = new int[26];
            for (int j = i; j < i + n1; j++) s2Count[s2.charAt(j) - 'a']++;
            if (java.util.Arrays.equals(s1Count, s2Count)) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Fixed Size Window problem because any permutation of s1 must have exactly the same length as s1.

Thought Process

Instead of sorting every substring, we use character frequency counts. A permutation of s1 will have the exact same character frequency count as s1. We maintain a window of size s1.length() in s2 and update the counts as we slide.

Mandatory Variables

  • left: Marks the start of the window.
  • s1Counts: Frequency map of characters in s1.
  • windowCounts: Frequency map of characters in the current s2 window.
⏱ O(N) where N is length of s2.💾 O(1) - alphabet size (26).

Detailed Dry Run

Windows2 FragmentCounts Match?Action
[0, 1]"ei"NoExpand R, Shrink L
[1, 2]"id"NoExpand R, Shrink L
[2, 3]"db"NoExpand R, Shrink L
[3, 4]"ba"YES!Return True
java
import java.util.*;

public class Main {
    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        
        int[] s1Counts = new int[26];
        int[] windowCounts = new int[26];
        
        // Fill counts for s1 and initial window of s2
        for (int i = 0; i < s1.length(); i++) {
            s1Counts[s1.charAt(i) - 'a']++;
            windowCounts[s2.charAt(i) - 'a']++;
        }

        // Comparison helper
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (Arrays.equals(s1Counts, windowCounts)) return true;
            
            // Slide window: remove left, add right
            windowCounts[s2.charAt(i) - 'a']--;
            windowCounts[s2.charAt(i + s1.length()) - 'a']++;
        }
        
        return Arrays.equals(s1Counts, windowCounts);
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
    }
}

⚠️ Common Pitfalls & Tips

Be careful to check the final window after the loop ends, as the last comparison might not happen inside the loop depending on how you structure it.

Minimum Window Substring

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

Visual Representation

s = "ADOBECODEBANC", t = "ABC" Window Expand (Found all ABC): [ADOBEC]ODEBANC (Len: 6) Window Shrink (Still have ABC): A [DOBEC]ODEBANC (Len: 5) -> [DOBEC] (Wait, missing A!) Final Optimal Window: ADOBECODE [BANC] (Len: 4)
Hard

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Approach 1

Level I: Brute Force

Intuition

Check every possible substring of s and verify if it contains all characters of t in the required frequencies. Keep track of the minimum length substring that satisfies this.

Thought Process

  1. Iterate through all possible start and end indices to define every substring.
  2. For each substring, count its character frequencies.
  3. Compare these frequencies with the target frequency map of t.
  4. If the substring is valid, update the minWindow result.
⏱ O(N^2 * M) where N is length of s and M is length of t.💾 O(N + M)

Detailed Dry Run

SubstringValid?Min LengthMin Window
"ADOBE"No (missing C)inf""
"ADOBEC"YES!6"ADOBEC"
"BANC"YES!4"BANC"
java
import java.util.*;

public class Main {
    public static String minWindow(String s, String t) {
        String result = "";
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (isValid(sub, t)) {
                    if (sub.length() < minLen) {
                        minLen = sub.length();
                        result = sub;
                    }
                }
            }
        }
        return result;
    }

    private static boolean isValid(String sub, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        Map<Character, Integer> subMap = new HashMap<>();
        for (char c : sub.toCharArray()) subMap.put(c, subMap.getOrDefault(c, 0) + 1);
        for (char c : tMap.keySet()) {
            if (subMap.getOrDefault(c, 0) < tMap.get(c)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
    }
}
Approach 2

Level II: Binary Search on Window Size

Intuition

The shortest valid window length must be between len(t) and len(s). We can binary search for this length k. For each k, we use a fixed-size sliding window of length k to check if any valid substring exists. If it does, we try smaller lengths; otherwise, we try larger ones.

⏱ O(N log N) where N is the length of s.💾 O(K) where K is the number of unique characters.

Detailed Dry Run

Input: s = "ADOBECODEBANC", t = "ABC"

  1. Binary Search range: [3, 13].
  2. Try k = 8: Substring ADOBECOD is valid. Search [3, 7].
  3. Try k = 5: Substring EBANC is valid. Search [3, 4].
  4. Try k = 4: Substring BANC is valid. Search [3, 3].
  5. Try k = 3: No window of size 3 is valid.
  6. Result: k = 4, return BANC.
java
import java.util.*;

public class Solution {
    public String minWindow(String s, String t) {
        int left = t.length(), right = s.length();
        String result = "";
        Map<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) target.put(c, target.getOrDefault(c, 0) + 1);

        while (left <= right) {
            int mid = left + (right - left) / 2;
            String current = check(s, t, mid, target);
            if (!current.isEmpty()) {
                result = current;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private String check(String s, String t, int k, Map<Character, Integer> target) {
        Map<Character, Integer> window = new HashMap<>();
        int formed = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (target.containsKey(c) && window.get(c).equals(target.get(c))) formed++;
            if (i >= k) {
                char out = s.charAt(i - k);
                if (target.containsKey(out) && window.get(out).equals(target.get(out))) formed--;
                window.put(out, window.get(out) - 1);
            }
            if (formed == target.size()) return s.substring(i - k + 1, i + 1);
        }
        return "";
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Variable Size Window problem. We need to find the smallest range [L, R] that satisfies the requirement.

Thought Process

  1. Use a map targetCounts to store required characters in t.
  2. Expand right until the window contains all characters in t. We use a have counter vs a need counter for O(1)O(1) validity check.
  3. Once valid, shrink left as much as possible while maintaining validity to find the smallest window.
  4. Update the minWindow result whenever a smaller valid window is found.

Mandatory Variables

  • left, right: Window pointers.
  • targetMap: Frequencies of characters in t.
  • windowMap: Frequencies of characters in the current window.
  • have, need: Variables to track progress toward the target frequency.
⏱ O(N + M) where N is length of s and M is length of t.💾 O(M) for frequency maps.

Detailed Dry Run

s = "ADOBEC", t = "ABC"

StepLRCharWindow MapHave/NeedAction
100'A'{A:1}1/3Expand
2-404'E'{A:1, B:1}2/3Expand
505'C'{A:1, B:1, C:1}3/3VALID!
615'D'{B:1, C:1}2/3Shrink (Invalidated)
java
import java.util.*;

public class Main {
    public static String minWindow(String s, String t) {
        if (t.isEmpty()) return "";
        Map<Character, Integer> countT = new HashMap<>(), window = new HashMap<>();
        for (char c : t.toCharArray()) countT.put(c, countT.getOrDefault(c, 0) + 1);

        int have = 0, need = countT.size();
        int[] res = {-1, -1}; int resLen = Integer.MAX_VALUE;
        int L = 0;

        for (int R = 0; R < s.length(); R++) {
            char c = s.charAt(R);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (countT.containsKey(c) && window.get(c).equals(countT.get(c))) have++;

            while (have == need) {
                if ((R - L + 1) < resLen) {
                    resLen = R - L + 1;
                    res[0] = L; res[1] = R;
                }
                char leftChar = s.charAt(L);
                window.put(leftChar, window.get(leftChar) - 1);
                if (countT.containsKey(leftChar) && window.get(leftChar) < countT.get(leftChar)) have--;
                L++;
            }
        }
        return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with character counts if t has duplicates. Using a have/need counter for unique characters is more robust than a total character count.

Max Consecutive Ones III

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.

Visual Representation

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 L R | | 1 1 1 0 0 0 1 1 1 1 0 [-----] (Zeros: 1 <= 2, Expand R) L R | | 1 1 1 0 0 0 1 1 1 1 0 [-------] (Zeros: 2 <= 2, Expand R) L R | | 1 1 1 0 0 0 1 1 1 1 0 [---------] (Zeros: 3 > 2! Shrink L)
Medium

Examples

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Approach 1

Level I: Brute Force

Intuition

Check every possible subarray and count the number of zeros in it. If the zero count is less than or equal to k, the subarray is valid. Keep track of the maximum length of such valid subarrays.

Thought Process

  1. Use two nested loops to define all possible subarrays [i, j].
  2. In the inner loop, count zeros.
  3. If zeros <= k, update maxLen = max(maxLen, j - i + 1).
  4. If zeros > k, break the inner loop (optimization).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijnums[j]ZerosMax LenAction
00101Update
03014Update
04025Update
05035Break (Zeros > k)
java
public class Main {
    public static int longestOnes(int[] nums, int k) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            int zeros = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 0) zeros++;
                if (zeros <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        int k = 2;
        System.out.println(longestOnes(nums, k)); // 6
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum possible length L of a valid subarray. For a fixed length L, we can check if there exists any subarray of length L with at most k zeros using a fixed-size sliding window in O(N)O(N) time.

Thought Process

  1. Search range for length is [0, n].
  2. For a fixed mid length:
    • Slide a window of size mid across the array.
    • Count zeros in the window.
    • If any window has zeros <= k, then mid is possible.
  3. If possible, search higher; else search lower.

Pattern: Search on Answer Space

⏱ O(N log N) - Binary search takes $\log N$ steps, and each check takes $O(N)$.💾 O(1)
java
public class Solution {
    public int longestOnes(int[] nums, int k) {
        int low = 0, high = nums.length, res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, k, mid)) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    private boolean check(int[] nums, int k, int len) {
        int zeros = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) zeros++;
            if (i >= len) {
                if (nums[i - len] == 0) zeros--;
            }
            if (i >= len - 1 && zeros <= k) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Instead of checking every subarray, we use a window [left, right]. We expand the window by moving right. If the number of zeros in the window exceeds k, we must shrink the window from the left until the zero count is back to k.

Pattern: Variable Size Sliding Window

  • Expand: windowSum += (nums[right] == 0 ? 1 : 0)
  • Constraint: zeros > k
  • Shrink: while (zeros > k) { if (nums[left] == 0) zeros--; left++; }
⏱ O(N)💾 O(1)

Detailed Dry Run

RNumZerosActionMax Len
301Expand4
402Expand5
503Shrink L (until zeros=2)5
1002Expand6
java
public class Main {
    public static int longestOnes(int[] nums, int k) {
        int left = 0, res = 0, zeros = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeros++;
            while (zeros > k) {
                if (nums[left] == 0) zeros--;
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        int k = 2;
        System.out.println(longestOnes(nums, k)); // 6
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the while loop condition. It should be zeros > k. Also, ensure you update maxLen after the shrink loop is done to ensure the window is valid.

Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees. Each tree has a type. You have TWO baskets, each holding ONE type. Find the maximum fruits you can collect in a contiguous range.

Visual Representation

fruits = [1, 2, 1, 2, 3] L R | | 1, 2, 1, 2, 3 Types: {1, 2}, Count: 4 [---------] L R | | 1, 2, 1, 2, 3 Types: {2, 3}, Count: 2 [-]
Medium

Examples

Input: fruits = [1,2,1]
Output: 3
Approach 1

Level I: Brute Force

Intuition

Check every possible contiguous range of trees and count how many fruits and types are in that range. If the number of types is ≤ 2, the range is valid. Track the maximum fruits collected.

Thought Process

  1. Use two nested loops to define all possible ranges [i, j].
  2. In the inner loop, add each fruit to a set to count types.
  3. If types ≤ 2, update maxFruits = max(maxFruits, j - i + 1).
  4. If types > 2, break the inner loop.
⏱ O(N^2)💾 O(1) - The set size is at most 3 before breaking.

Detailed Dry Run

ijfruits[j]TypesFruitsMax
001{1}11
012{1, 2}22
021{1, 2}33
032{1, 2}44
043{1, 2, 3}54 (Break)
java
import java.util.*;

public class Main {
    public static int totalFruit(int[] fruits) {
        int maxFruits = 0;
        for (int i = 0; i < fruits.length; i++) {
            Set<Integer> types = new HashSet<>();
            for (int j = i; j < fruits.length; j++) {
                types.add(fruits[j]);
                if (types.size() <= 2) {
                    maxFruits = Math.max(maxFruits, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        int[] fruits = {1, 2, 1, 2, 3};
        System.out.println(totalFruit(fruits)); // 4
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum number of fruits L we can collect. For a fixed length L, we check if any contiguous subarray of length L contains at most 2 distinct fruit types using a fixed-size sliding window.

Thought Process

  1. Search range is [1, n].
  2. For a fixed mid length:
    • Slide a window of size mid.
    • Maintain a frequency map of fruit types in the window.
    • If map.size() <= 2 at any point, the length mid is possible.
  3. Adjust the search range based on possibility.

Pattern: BS on Answer + Sliding Window Check

⏱ O(N log N)💾 O(1) - The map size in the check is at most 3.
java
public class Solution {
    public int totalFruit(int[] fruits) {
        int low = 1, high = fruits.length, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canCollect(fruits, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean canCollect(int[] fruits, int len) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < fruits.length; i++) {
            counts.put(fruits[i], counts.getOrDefault(fruits[i], 0) + 1);
            if (i >= len) {
                int out = fruits[i - len];
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            if (i >= len - 1 && counts.size() <= 2) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We need to find the longest subarray that contains exactly or at most two distinct elements. We use a frequency map to track the fruits in our window. When the number of types (map size) exceeds 2, we shrink the window from the left.

Pattern: Variable Size Sliding Window (K Distinct Elements)

  • Expand: count[fruits[right]]++
  • Constraint: count.size() > 2
  • Shrink: while (count.size() > 2) { count[fruits[left]]--; if (count[fruits[left]] == 0) count.remove(fruits[left]); left++; }
⏱ O(N)💾 O(1) - Hash Map size is at most 3.

Detailed Dry Run

RFruitMapMap SizeActionResult
01{1:1}1Expand1
12{1:1, 2:1}2Expand2
21{1:2, 2:1}2Expand3
32{1:2, 2:2}2Expand4
43{1:2, 2:2, 3:1}3Shrink L (remove 1s)4
java
import java.util.*;

public class Main {
    public static int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.length; right++) {
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);
            
            while (count.size() > 2) {
                count.put(fruits[left], count.get(fruits[left]) - 1);
                if (count.get(fruits[left]) == 0) {
                    count.remove(fruits[left]);
                }
                left++;
            }
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        int[] fruits = {1, 2, 1, 2, 3};
        System.out.println(totalFruit(fruits)); // 4
    }
}

⚠️ Common Pitfalls & Tips

Be careful with shrinking: ensure you decrement the count and remove the key from the map ONLY when the count reaches zero. Forgetting to remove the key will result in an incorrect count.size().

Longest Repeating Character Replacement

You are given a string s and an integer k. You can change at most k characters to any other uppercase English character. Return the length of the longest substring containing the same letter.

Visual Representation

s = "AABABBA", k = 1 [A A B A] B B A (Len: 4, MaxFreq char 'A': 3) Window Size 4 - MaxFreq 3 = 1 (Matches k=1, VALID) [A A B A B] B A (Len: 5, MaxFreq char 'A': 3) Window Size 5 - MaxFreq 3 = 2 (Exceeds k=1, INVALID)
Medium

Examples

Input: s = "ABAB", k = 2
Output: 4

Replace the two 'A's with two 'B's or vice-versa.

Approach 1

Level I: Brute Force

Intuition

For every possible substring, check if we can make all characters in that substring the same by replacing at most k characters. To do this for a substring, we find the frequency of the most common character and check if (length - maxFreq) <= k.

Thought Process

  1. Use two nested loops to iterate through all substrings [i, j].
  2. For each substring, count character frequencies.
  3. Find the character with the maximum frequency (maxFreq).
  4. If (substringLength - maxFreq) <= k, the substring is valid.
  5. Update maxLen accordingly.
⏱ O(26 * N^2)💾 O(1) - alphabet size map (26)

Detailed Dry Run

SubstringFreq MapMax FreqLen - MaxFreqkValid?
"AAB"{A:2, B:1}23-2 = 11YES
"AABA"{A:3, B:1}34-3 = 11YES
"AABAB"{A:3, B:2}35-3 = 21NO
java
public class Main {
    public static int characterReplacement(String s, int k) {
        int maxLen = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                maxFreq = Math.max(maxFreq, ++count[s.charAt(j) - 'A']);
                if ((j - i + 1) - maxFreq <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(characterReplacement("AABABBA", 1)); // 4
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N * 26))

Intuition

We can binary search for the maximum possible length L of a valid substring. For a fixed length L, we use a sliding window of size L to check if at least one window satisfies (L - maxFreq) <= k. Finding maxFreq in a window takes O(26).

Thought Process

  1. Search range for L is [0, n].
  2. For each mid length step in binary search:
    • Slide a window of size mid across the string.
    • Count characters and find the most frequent character.
    • If mid - maxFreq <= k, then length mid is possible.
  3. Adjust the search range accordingly.

Pattern: Search on Answer Space

⏱ O(26 * N log N) - Binary search takes $\log N$ steps, each check takes $O(26 \times N)$.💾 O(1) - alphabet size map (26)
java
public class Solution {
    public int characterReplacement(String s, int k) {
        int low = 1, high = s.length(), res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, k, mid)) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    private boolean check(String s, int k, int len) {
        int[] counts = new int[26];
        int maxFreq = 0;
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'A']++;
            if (i >= len) counts[s.charAt(i - len) - 'A']--;
            
            if (i >= len - 1) {
                maxFreq = 0;
                for (int count : counts) maxFreq = Math.max(maxFreq, count);
                if (len - maxFreq <= k) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Instead of re-calculating everything, we use a sliding window [left, right]. We maintain the frequency of the most common character within the current window. The window is valid as long as (WindowLength - MaxFrequency) <= k. This works because WindowLength - MaxFrequency represents the minimum number of characters we need to replace to make all characters in the window the same.

Pattern: Variable Size Sliding Window

  • Expand: Increment frequency of s[right] and update maxFreq.
  • Constraint: (right - left + 1) - maxFreq > k
  • Shrink: Increment left and decrement its frequency. Note: maxFreq doesn't strictly need to be decreased, as only a larger maxFreq can increase our result.
⏱ O(N)💾 O(1) - alphabet size (26).

Detailed Dry Run

RCharFreq MapMax FreqValid?Action
0A{A:1}1YesExpand
1A{A:2}2YesExpand
2B{A:2, B:1}2YesExpand
3A{A:3, B:1}3YesExpand
4B{A:3, B:2}3NoShrink L
java
public class Main {
    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxFreq = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
            
            // Window invalid? Shrink it
            if (right - left + 1 - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(characterReplacement("AABABBA", 1)); // 4
    }
}

⚠️ Common Pitfalls & Tips

You don't need to decrement maxFreq when shrinking the window. While this seems counter-intuitive, think about it: we only care about the largest maxFreq we've ever seen because that's the only way to get a larger maxLen.

Find All Anagrams in a String

Given strings s and p, return an array of all the start indices of p's anagrams in s.

Visual Representation

s = "cbaebabacd", p = "abc" [c b a] e b a b a c d (Window: {a:1, b:1, c:1}, Matches! Index 0) c [b a e] b a b a c d (Window: {a:1, b:1, e:1}, Mismatch) ... c b a e b a b [a c d] (Wait, missing b! Mismatch)
Medium

Examples

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Approach 1

Level I: Brute Force

Intuition

For every possible substring of s that has the same length as p, check if it's an anagram of p. To check for anagrams, we can sort both strings or compare their character frequency maps.

Thought Process

  1. Iterate through s with a loop from 0 to n - m (where m is p.length()).
  2. Extract the substring of length m.
  3. Compare the substring with p using a frequency map or sorting.
  4. If they match, add the starting index to the result list.
⏱ O(N * M)💾 O(1) - alphabet size (26)

Detailed Dry Run

Start IndexSubstringIs Anagram of "abc"?Result
0"cba"YES[0]
1"bae"NO[0]
6"abc"YES[0, 6]
java
import java.util.*;

public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return result;
        
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            int[] sCount = new int[26];
            for (int j = i; j < i + m; j++) {
                sCount[s.charAt(j) - 'a']++;
            }
            if (Arrays.equals(pCount, sCount)) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc")); // [0, 6]
    }
}
Approach 2

Level II: Optimized Brute Force (O(N * 26))

Intuition

Instead of re-comparing the whole substring or sorting, we can compare the frequency counts of characters. Since the alphabet is small (26), comparing two maps of size 26 is O(26)O(26), which is effectively constant time.

Thought Process

  1. Count character frequencies for p.
  2. Iterate through s and for every window of size m, build the frequency map for that window.
  3. Compare the map with pCount using Arrays.equals (Java) or == (Python/Go).

Pattern: Constant-Time Map Comparison

⏱ O(N * 26) where N is the length of `s`.💾 O(26) for storing frequency counts.
java
public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return res;
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            int[] sCount = new int[26];
            for (int j = i; j < i + m; j++) sCount[s.charAt(j) - 'a']++;
            if (java.util.Arrays.equals(pCount, sCount)) res.add(i);
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Since an anagram must have exactly the same length as p, we use a Fixed Size Sliding Window of length m. We maintain frequency counts for both p and the current s window. Instead of re-calculating the frequency map for every window, we 'slide' it: add the incoming character and remove the outgoing one.

Pattern: Fixed Size Sliding Window

  • Init: Fill frequency maps for p and the first m characters of s.
  • Slide: For i from m to n-1:
    1. Add s[i] to sCount.
    2. Remove s[i - m] from sCount.
    3. Compare maps.
⏱ O(N)💾 O(1) - alphabet size (26).

Detailed Dry Run

| Window | Start Index | Added | Removed | Match? | | :--- | :--- | :--- | :--- | :--- | :--- | | [0, 2] | 0 | - | - | YES | | [1, 3] | 1 | 'e' | 'c' | NO | | [6, 8] | 6 | 'c' | 'b' | YES |

java
import java.util.*;

public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;
        
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(pCount, sCount)) res.add(0);

        for (int i = p.length(); i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++; // Add right
            sCount[s.charAt(i - p.length()) - 'a']--; // Remove left
            
            if (Arrays.equals(pCount, sCount)) {
                res.add(i - p.length() + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc")); // [0, 6]
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the sliding logic: ensure you add the NEW character and remove the OLD character at the same step to keep the window size constant. Also, check the very first window before the loop starts.

Sliding Window Maximum

Given an array nums and a window size k, return the maximum in each sliding window.

Visual Representation

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Window: [1, 3, -1] Max: 3 Window: [3, -1, -3] Max: 3 Window: [-1, -3, 5] Max: 5 Monotonic Deque (indices): Step 1 (1): [0] Step 2 (3): [1] (discarded 0 since 3 > 1) Step 3 (-1): [1, 2] Step 4 (-3): [1, 2, 3] Step 5 (5): [4] (discarded 1, 2, 3 since 5 is larger)
Hard

Examples

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

Level I: Brute Force

Intuition

For every possible sliding window of size k, iterate through all its elements to find the maximum value.

Thought Process

  1. There are n - k + 1 windows in an array of size n.
  2. For each window starting at index i, loop from i to i + k - 1 to find the max.
  3. Store the result in an array.
⏱ O(N * K)💾 O(1) excluding the result array.

Detailed Dry Run

WindowElementsMaxResult
[0, 2][1, 3, -1]3[3]
[1, 3][3, -1, -3]3[3, 3]
[2, 4][-1, -3, 5]5[3, 3, 5]
java
import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return new int[0];
        int[] res = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int max = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] > max) max = nums[j];
            }
            res[i] = max;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums, 3))); // [3, 3, 5, 5, 6, 7]
    }
}
Approach 2

Level II: Heaps / Priority Queue (O(N log N))

Intuition

To find the maximum in a window efficiently, we can use a Max-Heap (Priority Queue). The heap stores pairs of (value, index). For each window, we add the current element to the heap and then remove elements from the top of the heap if their indices are outside the current window.

Thought Process

  1. Use a Max-Heap to store [nums[i], i].
  2. In each step, add the current element to the heap.
  3. Peek at the top of the heap. If the index is less than i - k + 1, it's outside the window; remove it (pop).
  4. The top of the heap is the maximum for the current window.

Pattern: Sliding Window + Heap Optimization

⏱ O(N log N) - In the worst case, we push all $N$ elements into the heap.💾 O(N) - To store elements in the heap.
java
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            if (i >= k - 1) {
                while (pq.peek()[1] <= i - k) pq.poll();
                res[i - k + 1] = pq.peek()[0];
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Monotonic Deque)

Intuition

Thought Process

We need a way to find the maximum in the current window in O(1)O(1). A Monotonic Deque stores indices of elements in strictly decreasing order of their values (nums[dq.front()] is always max).

Logic Steps

  1. Clean Deque (Old indices): If the index at the front is outside the current window [i-k+1, i], remove it.
  2. Maintain Monotonicity: Before adding nums[i], remove all indices from the back whose values are ≤nums[i]\le nums[i]. They can never be the maximum in any future window containing nums[i].
  3. Add Result: Once the window reaches size k, the value at nums[dq.front()] is the maximum for the current window.
⏱ O(N) - Each index is pushed and popped at most once.💾 O(K) for the deque.

Detailed Dry Run

iValActionDeque (Indices)Result
13Pop 0 (1 < 3)[1]-
2-1Push 2[1, 2][3]
3-3Push 3[1, 2, 3][3, 3]
45Pop all (all < 5)[4][3, 3, 5]
java
import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 1. Remove indices outside current window
            if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
            // 2. Maintain monotonic decreasing property
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            // 3. Add current
            dq.offerLast(i);
            // 4. Record max
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums, 3)));
    }
}

⚠️ Common Pitfalls & Tips

Storing values instead of indices in the deque makes it hard to check if the maximum element has slid out of the window. Always store indices.

Minimum Window Subsequence

Given strings s1 and s2, find the minimum contiguous substring of s1 such that s2 is a subsequence of that part.

Visual Representation

s1 = "abcdebdde", s2 = "bde" Forward (Find b...d...e): a b c d e b d d e ^ ^ ^ (Found at index 4, end=5) Backward (Optimize Start from index 4): a b c d e ^ ^ (Start=1, b is at idx 1) Result: "bcde" (Len 4)
Hard

Examples

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Approach 1

Level I: Brute Force

Intuition

For every possible starting point in s1, scan forward to see if s2 can be formed as a subsequence. If it can, record the length and update the minimum window found so far.

Thought Process

  1. Iterate through all indices i in s1 as potential starts.
  2. From i, use another pointer k to scan s1, and j to scan s2.
  3. If s1[k] == s2[j], increment j.
  4. If j == s2.length(), we found a window [i, k]. Its length is k - i + 1.
  5. Track the minimum such length and the starting position.
⏱ O(N^2)💾 O(1)

Detailed Dry Run

Starts1 Scans2 MatchedWindowMin
1 (b)bcdeb, d, e (All)[1, 4]4
5 (b)bddeb, d, e (All)[5, 8]4
java
public class Main {
    public static String minWindow(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        String res = "";
        int minLen = n + 1;

        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) == s2.charAt(0)) {
                int s1Idx = i, s2Idx = 0;
                while (s1Idx < n && s2Idx < m) {
                    if (s1.charAt(s1Idx) == s2.charAt(s2Idx)) s2Idx++;
                    s1Idx++;
                }
                if (s2Idx == m) {
                    if (s1Idx - i < minLen) {
                        minLen = s1Idx - i;
                        res = s1.substring(i, s1Idx);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(minWindow("abcdebdde", "bde")); // "bcde"
    }
}
Approach 2

Level II: Dynamic Programming (O(N * M))

Intuition

We can use a 2D DP table dp[i][j] that stores the starting index of the shortest substring in s1[0...i] such that s2[0...j] is a subsequence. If no such substring exists, we store -1.

Thought Process

  1. dp[i][0] is i if s1[i] == s2[0], else dp[i-1][0].
  2. For j > 0, if s1[i] == s2[j], then dp[i][j] = dp[i-1][j-1] (we extend the subsequence start index from the previous match).
  3. Otherwise, dp[i][j] = dp[i-1][j] (we inherit the latest start index).

Pattern: Subsequence Search with DP

⏱ O(N * M)💾 O(N * M) - Can be optimized to $O(N)$.
java
public class Solution {
    public String minWindow(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) Arrays.fill(dp[i], -1);
        
        int start = -1, minLen = n + 1;
        for (int i = 1; i <= n; i++) {
            if (s1.charAt(i-1) == s2.charAt(0)) dp[i][1] = i - 1;
            else dp[i][1] = dp[i-1][1];
            
            for (int j = 2; j <= m; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = dp[i-1][j];
            }
            
            if (dp[i][m] != -1) {
                if (i - dp[i][m] < minLen) {
                    minLen = i - dp[i][m];
                    start = dp[i][m];
                }
            }
        }
        return start == -1 ? "" : s1.substring(start, start + minLen);
    }
}
Approach 3

Level III: Optimal (Sliding Window + Dual Scan)

Intuition

Thought Process

Unlike 'Minimum Window Substring' (set of chars), this requires subsequence (specific order). We scan forward to find any window containing the subsequence. Once found, we scan backward from the current end to find the best starting point for that specific window.

Patterns

  1. Forward Pass: Expand to find a valid window ending at i.
  2. Backward Pass: From i, scan back to find the latest valid start j. This handles cases like S=abbbcde, T=abcde more accurately by skipping redundant bs at the beginning of the window.
⏱ O(N * M)💾 O(1)

Detailed Dry Run

ijActionResult
10'b' matchedi=2, j=1
42'e' matchedWindow Found!
Backward-Scan back from i=4Start=1
Min-Check "bcde"MinLen=4
java
public class Main {
    public static String minWindow(String s1, String s2) {
        int i = 0, j = 0, start = -1, minL = s1.length() + 1;
        while (i < s1.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                if (++j == s2.length()) {
                    int end = i + 1;
                    j--; // Back to last matched index of s2
                    while (j >= 0) {
                        if (s1.charAt(i) == s2.charAt(j)) j--;
                        i--;
                    }
                    i++; j++; // i is now start, j is 0
                    if (end - i < minL) {
                        minL = end - i;
                        start = i;
                    }
                }
            }
            i++;
        }
        return start == -1 ? "" : s1.substring(start, start + minL);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("abcdebdde", "bde")); // "bcde"
    }
}

⚠️ Common Pitfalls & Tips

The backward scan is crucial for finding the optimal start. Without it, you might find a valid window but not the minimum one starting from a later occurrence of the first character.

Maximum Points You Can Obtain from Cards

You can take exactly k cards from either the beginning or the end of the row to maximize your point total.

Visual Representation

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3 Take cards from ends (Total: 7, k: 3): (1, 2) ... (1) Total: 4 (1) ... (6, 1) Total: 8 ... ... (5, 6, 1) Total: 12 (MAX) Trick: Minimize the sum of the remaining (n-k) cards! Remaining window size = 7 - 3 = 4
Medium

Examples

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Approach 1

Level I: Brute Force

Intuition

Try all possible combinations of taking i cards from the left and k - i cards from the right (where 0 <= i <= k). For each combination, calculate the sum and track the maximum.

Thought Process

  1. Let i be the number of cards from the left end.
  2. Then k - i cards must be taken from the right end.
  3. Iterate i from 0 to k.
  4. Calculate Sum = (Sum of first i) + (Sum of last k - i).
  5. Tracking the maximum sum.
⏱ O(K^2) or O(K) with prefix sums💾 O(1)

Detailed Dry Run

Cards from LeftCards from RightTotal Sum
03 (5, 6, 1)12
1 (1)2 (6, 1)8
2 (1, 2)1 (1)4
3 (1, 2, 3)06
java
public class Main {
    public static int maxScore(int[] cardPoints, int k) {
        int maxScore = 0;
        int n = cardPoints.length;
        for (int i = 0; i <= k; i++) {
            int currentScore = 0;
            // Left i cards
            for (int j = 0; j < i; j++) currentScore += cardPoints[j];
            // Right k-i cards
            for (int j = 0; j < k - i; j++) currentScore += cardPoints[n - 1 - j];
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1, 2, 3, 4, 5, 6, 1}, 3)); // 12
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Selecting k cards from the ends is equivalent to leaving n - k contiguous cards in the middle. To maximize the end cards, we must minimize the sum of the middle cards. This turns it into a fixed-size sliding window problem on the inner subarray.

Patterns

  1. Inverse Goal: Instead of picking ends, find the minimum middle.
  2. Fixed Window: The middle part always has size n - k.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowSumMin SumAction
[1, 2, 3, 4]1010Initial
[2, 3, 4, 5]1410Slide
[3, 4, 5, 6]1810Slide
[4, 5, 6, 1]1610Slide
java
public class Main {
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, total = 0, windowSum = 0;
        for (int p : cardPoints) total += p;
        if (k == n) return total;
        int windowSize = n - k;
        for (int i = 0; i < windowSize; i++) windowSum += cardPoints[i];
        int minWindowSum = windowSum;
        for (int i = windowSize; i < n; i++) {
            windowSum += cardPoints[i] - cardPoints[i - windowSize];
            minWindowSum = Math.min(minWindowSum, windowSum);
        }
        return total - minWindowSum;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1, 2, 3, 4, 5, 6, 1}, 3));
    }
}

⚠️ Common Pitfalls & Tips

While you can use recursion with memoization, the sliding window approach is much faster and uses O(1) extra space. The 'inverse' trick is the most important leap.

Longest Subarray of 1's After Deleting One Element

Given a binary array nums, you must delete exactly one element. Return the maximum number of consecutive 1's remaining.

Visual Representation

nums = [1, 1, 0, 1] [1, 1, 0, 1] ^ Delete this 0 Remaining: [1, 1, 1] -> Len 3 Sliding Window Rule: Window must contain at most ONE zero. Final Result = WindowSize - 1
Medium

Examples

Input: nums = [1,1,0,1]
Output: 3
Approach 1

Level I: Brute Force

Intuition

Iterate through every element in the array. For each element, assume it is the one being deleted, and then find the longest contiguous block of 1's that can be formed using the remaining elements.

Thought Process

  1. Iterate through each index i from 0 to n-1.
  2. Simulate deleting nums[i].
  3. After 'deletion', find the longest sequence of 1's in the remaining array.
  4. Track the maximum length found across all possible deletions.
⏱ O(N^2)💾 O(N) to store the modified array, or O(1) if logic is careful.

Detailed Dry Run

Deleting IndexResulting ArrayMax 1sResult
0[1, 0, 1]11
1[1, 0, 1]11
2[1, 1, 1]33
3[1, 1, 0]23
java
public class Main {
    public static int longestSubarray(int[] nums) {
        int maxLen = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentLen = 0, bestInThisCase = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (nums[j] == 1) {
                    currentLen++;
                    bestInThisCase = Math.max(bestInThisCase, currentLen);
                } else {
                    currentLen = 0;
                }
            }
            maxLen = Math.max(maxLen, bestInThisCase);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 0, 1};
        System.out.println(longestSubarray(nums)); // 3
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is equivalent to 'Max Consecutive Ones III' with k = 1. We find the longest window with at most one zero. Since we must delete one element, the result is always WindowSize - 1.

Patterns

  1. Variable Window: Expand as long as zeros ≤1\le 1.
  2. Constraint: If zeros > 1, shrink from left.
⏱ O(N)💾 O(1)

Detailed Dry Run

RNumZerosWindow SizeResult
01010
11021
20132
31143 (MAX)
java
public class Main {
    public static int longestSubarray(int[] nums) {
        int left = 0, zeros = 0, maxLen = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeros++;
            while (zeros > 1) {
                if (nums[left] == 0) zeros--;
                left++;
            }
            // The window length is (right - left + 1)
            // We MUST delete one element, so result is (windowLen - 1)
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestSubarray(new int[]{1, 1, 0, 1})); // 3
    }
}

⚠️ Common Pitfalls & Tips

If the array consists only of 1's, the result should be N - 1, not N. Don't forget that one deletion is MANDATORY.

Minimum Operations to Reduce X to Zero

Subtract values from either the left or right to reduce x exactly to 0. Return the minimum operations.

Visual Representation

nums = [1, 1, 4, 2, 3], x = 5 [1, 1] ... [3] (Total: 5, Ops: 3) [1] ... [2, 3] (Total: 6, Ops: 3) X ... ... [2, 3] (Total: 5, Ops: 2) -> BEST Goal: Maximize middle subarray with sum (TotalSum - x) Middle Target = 11 - 5 = 6 Max Middle = [1, 1, 4] (Len 3) Ops = 5 - 3 = 2
Medium

Examples

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible numbers of elements taken from the left end (i elements). For each i, find out how many elements from the right end are needed to reach exactly x. Track the minimum total operations.

Thought Process

  1. Let i be the number of elements from the left (0 <= i <= nums.length).
  2. Calculate the sum of these i elements. If sum > x, we can't take this many from left.
  3. If sum <= x, we need to find x - sum from the right end.
  4. Use another loop (or map) to find how many elements from right are needed.
  5. Total operations = i + count_from_right.
⏱ O(N^2) or O(N) with Hash Map💾 O(N) for maps, or O(1) for loops.

Detailed Dry Run

Left OpsLeft SumTarget RightRight OpsTotal
0052 (2, 3)2
1 (1)140 (None)-
2 (1, 1)231 (3)3
java
import java.util.*;

public class Main {
    public static int minOperations(int[] nums, int x) {
        int n = nums.length;
        int minOps = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            int leftSum = 0;
            for (int k = 0; k < i; k++) leftSum += nums[k];
            if (leftSum > x) break;
            if (leftSum == x) {
                minOps = Math.min(minOps, i);
            } else {
                int rightSum = 0;
                for (int j = 0; j < n - i; j++) {
                    rightSum += nums[n - 1 - j];
                    if (leftSum + rightSum == x) {
                        minOps = Math.min(minOps, i + j + 1);
                        break;
                    }
                    if (leftSum + rightSum > x) break;
                }
            }
        }
        return minOps == Integer.MAX_VALUE ? -1 : minOps;
    }

    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5)); // 2
    }
}
Approach 2

Level III: Optimal (Sliding Window on Inverse Target)

Intuition

Thought Process

Finding minimum operations from the ends is the same as finding the maximum length contiguous subarray in the middle whose sum is totalSum - x. This simplifies the problem into a standard variable-size sliding window.

Patterns

  1. Inverse Target: Target sum for window = Sum(nums) - x.
  2. Result Mapping: Min operations from ends = TotalLength - MaxWindowLength.
⏱ O(N)💾 O(1)

Detailed Dry Run

Current SumTargetMax LenOps
16--
26--
6 (Found!)635-3=2
863-
java
public class Main {
    public static int minOperations(int[] nums, int x) {
        long totalSum = 0;
        for (int n : nums) totalSum += n;
        long target = totalSum - x;
        if (target < 0) return -1;
        if (target == 0) return nums.length;

        int left = 0, maxLen = -1;
        long currentSum = 0;
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            while (currentSum > target && left <= right) {
                currentSum -= nums[left++];
            }
            if (currentSum == target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        return maxLen == -1 ? -1 : nums.length - maxLen;
    }

    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5)); // 2
    }
}

⚠️ Common Pitfalls & Tips

Edge cases: x is larger than total sum (target < 0), or x is exactly the total sum (target = 0). Use long for sums to avoid overflow if arrays are very large.

Grumpy Bookstore Owner

A bookstore owner can be grumpy at certain minutes. You can use a 'secret technique' to keep them calm for minutes consecutive minutes. Maximize satisfied customers.

Visual Representation

customers = [1, 0, 1, 2, 1, 1, 7, 5] grumpy = [0, 1, 0, 1, 0, 1, 0, 1] minutes = 3 Base satisfaction (owner not grumpy): 1 + 1 + 1 + 7 = 10 Potential extra (using technique on window of size 3): Win [1, 2, 1] (mins 1-3) -> Extra: 0*c[1] + 1*c[2] + 0*c[3] = 2 Win [7, 5] (mins 6-7) -> ... finding max extra ...
Medium

Examples

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Approach 1

Level I: Brute Force

Intuition

Iterate through every possible starting minute i for the 'X-minute technique'. For each i, calculate the total satisfied customers by summing: (base satisfied customers) + (additional customers satisfied while the technique is active at i).

Thought Process

  1. Calculate BaseSatisfied: Sum of customers[j] where grumpy[j] == 0 for all j.
  2. Iterate through each possible start i from 0 to n - minutes.
  3. For each i, calculate Additional: Sum of customers[j] where grumpy[j] == 1 and i <= j < i + minutes.
  4. Max Score = BaseSatisfied + max(Additional).
⏱ O(N * minutes)💾 O(1)

Detailed Dry Run

StartBaseAdditionalTotal
0101+1+012
3102+1+114
5101+5+016 (MAX)
java
public class Main {
    public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length;
        int base = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }

        int maxAdditional = 0;
        for (int i = 0; i <= n - minutes; i++) {
            int currentAdditional = 0;
            for (int j = i; j < i + minutes; j++) {
                if (grumpy[j] == 1) currentAdditional += customers[j];
            }
            maxAdditional = Math.max(maxAdditional, currentAdditional);
        }
        return base + maxAdditional;
    }

    public static void main(String[] args) {
        int[] cust = {1,0,1,2,1,1,7,5};
        int[] grump = {0,1,0,1,0,1,0,1};
        System.out.println(maxSatisfied(cust, grump, 3)); // 16
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We want to choose a window of size minutes where we 'cancel' the owner's grumpiness to maximize additional customers. This is a classic fixed-size sliding window over the potential 'bonuses'.

Patterns

  1. Fixed Window: The technique duration is fixed at minutes.
  2. Additive Bonus: Base satisfied customers are always there; we only focus on maximizing the 'recovered' customers in a window.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowRecoveredMax Recovered
[1,0,1]00
[0,1,2]33
[1,2,1]33
[1,1,7]88 (MAX)
java
public class Main {
    public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int satisfied = 0, extra = 0, maxExtra = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) satisfied += customers[i];
            if (grumpy[i] == 1) extra += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) extra -= customers[i - minutes];
            maxExtra = Math.max(maxExtra, extra);
        }
        return satisfied + maxExtra;
    }

    public static void main(String[] args) {
        System.out.println(maxSatisfied(new int[]{1,0,1,2,1,1,7,5}, new int[]{0,1,0,1,0,1,0,1}, 3));
    }
}

⚠️ Common Pitfalls & Tips

Ensure you only add/remove customers[i] based on grumpy[i] == 1. The base customers grumpy[i] == 0 should not be affected by the sliding window logic after they are counted initially.

Maximum Number of Vowels in a Substring of Given Length

Find the maximum number of vowels in any substring of length k.

Visual Representation

s = "abciiidef", k = 3 Window [abc] -> Vowels: 1 (a) Window [bci] -> Vowels: 1 (i) Window [cii] -> Vowels: 2 (i, i) Window [iii] -> Vowels: 3 (i, i, i) -> MAX
Medium

Examples

Input: s = "abciiidef", k = 3
Output: 3
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible strings of length k. For each substring, count the number of vowels manually by iterating through characters.

Thought Process

  1. Iterate i from 0 to n - k.
  2. Extract substring s[i : i+k].
  3. Count vowels in the substring.
  4. Track the maximum count observed.
⏱ O(N * K)💾 O(1) (excluding substring storage if any)

Detailed Dry Run

SubstringVowelsMax
abca (1)1
bcii (1)1
ciii, i (2)2
iiii, i, i (3)3
java
public class Main {
    public static int maxVowels(String s, int k) {
        int maxV = 0;
        String vowels = "aeiou";
        for (int i = 0; i <= s.length() - k; i++) {
            int currentV = 0;
            for (int j = i; j < i + k; j++) {
                if (vowels.indexOf(s.charAt(j)) != -1) currentV++;
            }
            maxV = Math.max(maxV, currentV);
        }
        return maxV;
    }

    public static void main(String[] args) {
        System.out.println(maxVowels("abciiidef", 3)); // 3
    }
}
Approach 2

Level II: Prefix Sums for Vowels (O(N) Space)

Intuition

We can precompute an array vowelCount where vowelCount[i] stores the number of vowels from index 0 to i-1. The number of vowels in any substring s[i...i+k-1] can be calculated as vowelCount[i+k] - vowelCount[i].

Thought Process

  1. Initialize an array prefix of size n + 1.
  2. Iterate through the string; if s[i] is a vowel, prefix[i+1] = prefix[i] + 1, otherwise prefix[i+1] = prefix[i].
  3. Iterate i from 0 to n - k and track max(prefix[i+k] - prefix[i]).

Pattern: Multi-pass Optimization

⏱ O(N) - One pass to build prefix array, one to find max.💾 O(N) - To store the prefix sum array.
java
public class Main {
    public static int maxVowels(String s, int k) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        String vowels = "aeiou";
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (vowels.indexOf(s.charAt(i)) != -1 ? 1 : 0);
        }
        int maxV = 0;
        for (int i = 0; i <= n - k; i++) {
            maxV = Math.max(maxV, prefix[i + k] - prefix[i]);
        }
        return maxV;
    }
}
Approach 3

Level III: Optimal (Fixed Sliding Window)

Intuition

Thought Process

This is a classic fixed-size sliding window problem. We maintain a count of vowels. When a new character enters the window, we increment if it's a vowel. When a character leaves, we decrement if it was a vowel.

Patterns

  1. Fixed size k: Window is always exactly k wide.
  2. O(1) Update: Only the entering and leaving characters change the state.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowVowel CountMax Count
[abc]11
[bci]11
[cii]22
[iii]33
java
public class Main {
    public static int maxVowels(String s, int k) {
        int maxV = 0, curV = 0;
        String vowels = "aeiou";
        for (int i = 0; i < s.length(); i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) curV++;
            if (i >= k) {
                if (vowels.indexOf(s.charAt(i - k)) != -1) curV--;
            }
            maxV = Math.max(maxV, curV);
        }
        return maxV;
    }

    public static void main(String[] args) {
        System.out.println(maxVowels("abciiidef", 3));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with string indexing. The check for leaving elements should happen once the index i is >= k.

Subarray Product Less Than K

Count the number of contiguous subarrays where the product of all elements is strictly less than k.

Visual Representation

nums = [10, 5, 2, 6], k = 100 [10] -> Prod: 10 (<100) Count +1 [10, 5] -> Prod: 50 (<100) Count +2 (new: [5], [10,5]) [10, 5, 2] -> Prod: 100 (>=100) -> Shrink left [5, 2] -> Prod: 10 (<100) Count +2 (new: [2], [5,2]) Rule: Subarrays ending at 'right' = right - left + 1
Medium

Examples

Input: nums = [10,5,2,6], k = 100
Output: 8
Approach 1

Level I: Brute Force

Intuition

Iterate through every possible starting point i and ending point j. For each pair, calculate the product of elements in nums[i...j]. If the product is less than k, increment the count.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Calculate prod = prod * nums[j].
  4. If prod < k, count++.
  5. If prod >= k, break inner loop (since elements are positive, product will only increase).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijProdResult
00 (10)10Count 1
01 (5)50Count 2
02 (2)100STOP
11 (5)5Count 3
java
public class Main {
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long prod = 1;
            for (int j = i; j < nums.length; j++) {
                prod *= nums[j];
                if (prod < k) count++;
                else break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100)); // 8
    }
}
Approach 2

Level II: Log-Sum Prefix Sums + Binary Search (O(N log N))

Intuition

We can transform the product comparison into a sum comparison using logarithms: ∏xi<K  ⟺  ∑log⁡(xi)<log⁡(K)\prod x_i < K \iff \sum \log(x_i) < \log(K). Since all elements are positive, the prefix sums of log⁡(xi)\log(x_i) are monotonically increasing, allowing us to use Binary Search for each starting point.

Thought Process

  1. Precompute an array prefixLogs where prefixLogs[i] is the sum of log(nums[0...i-1]).
  2. For each starting index i, we need to find the largest j such that prefixLogs[j+1] - prefixLogs[i] < log(K) - epsilon (to handle floating point precision).
  3. The number of such j's for a fixed i is j - i + 1.

Pattern: Logarithmic Transformation

⏱ O(N log N) - For each of the $N$ starting points, we perform a binary search.💾 O(N) to store the prefix logs.
java
public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int n = nums.length;
        double[] prefixLogs = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixLogs[i + 1] = prefixLogs[i] + Math.log(nums[i]);
        }

        double logK = Math.log(k);
        int count = 0;
        for (int i = 0; i < n; i++) {
            int low = i + 1, high = n, ans = i;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (prefixLogs[mid] - prefixLogs[i] < logK - 1e-9) {
                    ans = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            count += (ans - i);
        }
        return count;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Standard variable-size sliding window. The key observation is that if a window [left, right] has a product < k, then ALL subarrays ending at right and starting between left and right also have products < k. There are right - left + 1 such subarrays.

Patterns

  1. Window-based Counting: Add Right - Left + 1 to result.
  2. Product Control: Divide by nums[left] when product ≥k\ge k.
⏱ O(N)💾 O(1)

Detailed Dry Run

RightNumProductLeftCount AddTotal
01010011
1550023
22100->10125
3660138
java
public class Main {
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, res = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k && left <= right) prod /= nums[left++];
            res += right - left + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100));
    }
}

⚠️ Common Pitfalls & Tips

Edge case k <= 1 is critical because the product of any subarray of positive integers is at least 1, which wouldn't be strictly less than 1.

Longest Turbulent Subarray

Find the maximum size of a 'turbulent' subarray where the comparison sign flips between adjacent pairs (e.g., a > b < c > d).

Visual Representation

arr = [9, 4, 2, 10, 7, 8, 8, 1, 9] [9 > 4] (Turbulent? Yes, Len 2) [9 > 4 < 2] (Turbulent? No, 4 > 2 is same sign as 9 > 4) [2 < 10 > 7 < 8] (Turbulent? Yes, Len 4) [8 == 8] (Reset window)
Medium

Examples

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible starting points i. For each i, expand the subarray as long as it remains turbulent. Track the maximum length.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j starts from i.
  3. Check if arr[j...j+1] satisfies the turbulent condition based on arr[j-1...j].
  4. If it breaks, record length and start next i.
  5. Maximize the findings.
⏱ O(N^2)💾 O(1)

Detailed Dry Run

iTurbulent SubarrayLength
0[9, 4]2
1[4, 2]2
2[2, 10, 7, 8]4
6[8, 8]1
java
public class Main {
    public static int maxTurbulenceSize(int[] arr) {
        int n = arr.length, maxLen = 1;
        for (int i = 0; i < n; i++) {
            int cur = 1;
            for (int j = i + 1; j < n; j++) {
                if (j == i + 1) {
                    if (arr[j] != arr[j-1]) cur++;
                    else break;
                } else {
                    if ((arr[j-1] > arr[j-2] && arr[j] < arr[j-1]) ||
                        (arr[j-1] < arr[j-2] && arr[j] > arr[j-1])) cur++;
                    else break;
                }
            }
            maxLen = Math.max(maxLen, cur);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(maxTurbulenceSize(new int[]{9,4,2,10,7,8,8,1,9})); // 5
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We essentially track the 'alternating sign' property. If the comparison between arr[i-1] and arr[i] matches the alternating expectation, we expand. If they are equal, we reset. If they have the same sign as the previous pair, we slide the start to the previous element.

Patterns

  1. Comparison Matching: Use Integer.compare or sign functions.
  2. Dynamic Anchor: Move anchor point based on where turbulence breaks.
⏱ O(N)💾 O(1)

Detailed Dry Run

iComparisonanchorres
19 > 4 (1)02
24 > 2 (1)12
32 < 10 (-1)22
410 > 7 (1)23
57 < 8 (-1)24
java
public class Main {
    public static int maxTurbulenceSize(int[] arr) {
        int n = arr.length, res = 1, anchor = 0;
        for (int i = 1; i < n; i++) {
            int c = Integer.compare(arr[i-1], arr[i]);
            if (c == 0) anchor = i;
            else if (i == n-1 || c * Integer.compare(arr[i], arr[i+1]) != -1) {
                res = Math.max(res, i - anchor + 1);
                anchor = i;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(maxTurbulenceSize(new int[]{9,4,2,10,7,8,8,1,9})); // 5
    }
}

⚠️ Common Pitfalls & Tips

Equal elements (e.g., 8, 8) break the turbulence immediately and reset the anchor to the current index.

Replace the Substring for Balanced String

Find the minimum length of a substring that can be replaced to make all characters ('Q', 'W', 'E', 'R') appear exactly n/4 times.

Visual Representation

s = "QQWE", n = 4, target = 1 Counts: Q:2, W:1, E:1, R:0 Over-limit: Q (2 > 1) Goal: Find smallest window that contains the 'excess' characters. Window [Q] (at index 0): Remaining Counts outside window: Q:1, W:1, E:1, R:0 All remaining counts <= target? YES! (1, 1, 1, 0 <= 1) Min Length = 1
Medium

Examples

Input: s = "QQWE"
Output: 1
Approach 1

Level I: Brute Force

Intuition

Iterate through every possible substring that could be replaced. For each substring, calculate the character frequencies of the remaining part of the string. If all counts (Q, W, E, R) in the remaining part are ≤n/4\le n/4, then the substring can be replaced to make the string balanced. Find the minimum length of such a substring.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Count characters in s[0...i-1] and s[j+1...n-1].
  4. If all counts ≤n/4\le n/4, minLen = min(minLen, j - i + 1).
  5. Handle the special case where the string is already balanced (length 0).
⏱ O(N^3) (can be O(N^2) if count updated incrementally)💾 O(1)

Detailed Dry Run

Substring [i, j]Remaining CountsValid?
GlobalQ:2, W:1, E:1, R:0NO
[0, 0] (Q)Q:1, W:1, E:1, R:0YES! (Len 1)
[1, 1] (Q)Q:1, W:1, E:1, R:0YES! (Len 1)
java
public class Main {
    public static int balancedString(String s) {
        int n = s.length(), m = n / 4;
        int[] total = new int[128];
        for (char c : s.toCharArray()) total[c]++;
        if (total['Q'] <= m && total['W'] <= m && total['E'] <= m && total['R'] <= m) return 0;

        int minLen = n;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int[] count = new int[128];
                for (int k = 0; k < i; k++) count[s.charAt(k)]++;
                for (int k = j + 1; k < n; k++) count[s.charAt(k)]++;
                if (count['Q'] <= m && count['W'] <= m && count['E'] <= m && count['R'] <= m) {
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }
        return minLen;
    }

    public static void main(String[] args) {
        System.out.println(balancedString("QQWE")); // 1
    }
}
Approach 2

Level II: Binary Search on Window Size (O(N log N))

Intuition

We can binary search for the minimum length L of the substring to replace. For a fixed length L, we check if any substring of size L can be replaced to make the entire string balanced. A string is balanced if all counts of 'Q', 'W', 'E', 'R' are exactly n/4n/4. Replacing a substring means the counts of remaining characters must be ≤n/4\le n/4.

Thought Process

  1. Target count for each character is n/4.
  2. In binary search, for a fixed mid length:
    • Slide a window of size mid across the string.
    • Count character frequencies outside the window.
    • If all counts outside ≤n/4\le n/4, then length mid is possible.
  3. Adjust the search range for the minimum possible mid.

Pattern: Search on Answer Space

⏱ O(N log N)💾 O(1) - alphabet size (4)
java
public class Solution {
    public int balancedString(String s) {
        int n = s.length(), target = n / 4;
        int low = 0, high = n, ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, target, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(String s, int target, int len) {
        int[] count = new int[256];
        for (char c : s.toCharArray()) count[c]++;
        
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]--;
            if (i >= len) count[s.charAt(i - len)]++;
            
            if (i >= len - 1) {
                if (count['Q'] <= target && count['W'] <= target && 
                    count['E'] <= target && count['R'] <= target) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

A string is balanced if all counts are ≤n/4\le n/4. To make a string balanced by replacing a substring, the characters outside that substring must all have counts ≤n/4\le n/4. We search for the smallest window such that all characters remaining outside it satisfy this condition.

Patterns

  1. Window Complement: Check characters NOT in the window.
  2. Smallest Valid Window: Shrink from left while condition is met.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowCount QCount WCount ECount RValid?
Global2110NO
[Q]1110YES
[QQ]0110YES
java
public class Main {
    public static int balancedString(String s) {
        int[] count = new int[128];
        int n = s.length(), res = n, i = 0, k = n / 4;
        for (int j = 0; j < n; j++) count[s.charAt(j)]++;
        if (count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) return 0;
        for (int j = 0; j < n; j++) {
            count[s.charAt(j)]--;
            while (i < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
                res = Math.min(res, j - i + 1);
                count[s.charAt(i++)]++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(balancedString("QQWE"));
    }
}

⚠️ Common Pitfalls & Tips

The goal is finding the smallest window that contains ALL excesses. If the string is already balanced, the answer is 0.

Get Equal Substrings Within Budget

Find the maximum length of a substring that can be transformed from s to t without exceeding maxCost.

Visual Representation

s = "abcd", t = "bcdf", maxCost = 3 Costs: |a-b|=1, |b-c|=1, |c-d|=1, |d-f|=2 Window [abc] -> [bcd]: Cost = 1+1+1 = 3 (<= 3) Len 3 Window [bcd] -> [cdf]: Cost = 1+1+2 = 4 (> 3) X
Medium

Examples

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible substrings s[i...j]. For each substring, calculate the transformation cost by summing the absolute differences between s[k] and t[k] for all k in the range. If the cost ≤maxCost\le maxCost, track the length.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Calculate currentCost = sum(abs(s[k] - t[k])) for k from i to j.
  4. If currentCost <= maxCost, maxLen = max(maxLen, j - i + 1).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijSubstringsCostMax Len
00'a'->'b'11
01'ab'->'bc'1+1=22
02'abc'->'bcd'1+1+1=33
03'abcd'->'bcdf'3+2=53
java
public class Main {
    public static int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), maxLen = 0;
        for (int i = 0; i < n; i++) {
            int currentCost = 0;
            for (int j = i; j < n; j++) {
                currentCost += Math.abs(s.charAt(j) - t.charAt(j));
                if (currentCost <= maxCost) maxLen = Math.max(maxLen, j - i + 1);
                else break;
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(equalSubstring("abcd", "bcdf", 3)); // 3
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum possible length L of a valid substring. For a fixed length L, we use a sliding window of size L to check if at least one window satisfies the maxCost constraint.

Thought Process

  1. Search range for L is [0, n].
  2. In each step of binary search (length mid):
    • Slide a window of size mid across the strings.
    • Calculate the total cost of the window.
    • If totalCost <= maxCost for any window, then mid is possible.
  3. Adjust the search range accordingly.

Pattern: Search on Answer Space

⏱ O(N log N)💾 O(1)
java
public class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), low = 0, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, t, maxCost, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(String s, String t, int maxCost, int len) {
        int currentCost = 0;
        for (int i = 0; i < s.length(); i++) {
            currentCost += Math.abs(s.charAt(i) - t.charAt(i));
            if (i >= len) currentCost -= Math.abs(s.charAt(i - len) - t.charAt(i - len));
            
            if (i >= len - 1 && currentCost <= maxCost) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is a standard variable-size sliding window problem on the array of transformation costs. We expand the window as long as the total cost is within the budget, and shrink from the left when it exceeds.

Patterns

  1. Rolling Cost Sum: Add cost of element at Right.
  2. Constraint Boundary: Move Left as long as Sum > Budget.
  3. Max Length Utility: Result is max(Result, Right - Left + 1).
⏱ O(N)💾 O(1)

Detailed Dry Run

RightCostTotal CostLeftMax Len
01101
11202
21303
325 -> 413
java
public class Main {
    public static int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), i = 0, j, res = 0, currentCost = 0;
        for (j = 0; j < n; j++) {
            currentCost += Math.abs(s.charAt(j) - t.charAt(j));
            while (currentCost > maxCost) {
                currentCost -= Math.abs(s.charAt(i) - t.charAt(i));
                i++;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(equalSubstring("abcd", "bcdf", 3));
    }
}

⚠️ Common Pitfalls & Tips

Be mindful of binary characters vs ASCII values. Use abs(ord(s[i]) - ord(t[i])) in Python or Math.abs(s.charCodeAt(i) - t.charCodeAt(i)) in JS.

Subarrays with K Different Integers

Count the number of 'good' subarrays where the number of different integers is exactly k.

Visual Representation

nums = [1, 2, 1, 2, 3], k = 2 Exactly(K) = AtMost(K) - AtMost(K-1) AtMost(2) Subarrays: [1], [2], [1,2], [1,2,1], [2,1,2] ... AtMost(1) Subarrays: [1], [2], [1], [2], [3] Exactly(2) = 12 - 5 = 7
Hard

Examples

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible substrings nums[i...j]. For each substring, count the number of unique integers. If the count is exactly k, increment the total result.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Maintain a set of unique elements encountered so far in nums[i...j].
  4. If set.size() == k, res++.
  5. If set.size() > k, break inner loop (since distinct elements only increase).
⏱ O(N^2)💾 O(K)

Detailed Dry Run

ijSubarrayDistinctResult
00[1]10
01[1, 2]21
02[1, 2, 1]22
04[1, 2, 1, 2, 3]3STOP
java
import java.util.*;
public class Main {
    public static int subarraysWithKDistinct(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> distinct = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                distinct.add(nums[j]);
                if (distinct.size() == k) count++;
                else if (distinct.size() > k) break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subarraysWithKDistinct(new int[]{1,2,1,2,3}, 2)); // 7
    }
}
Approach 2

Level II: Sliding Window with 3 Pointers (O(N))

Intuition

We can use three pointers to find the number of subarrays with exactly k distinct integers directly. We maintain two 'left' pointers: left1 (minimum index to satisfy k distinct) and left2 (minimum index to satisfy k-1 distinct). The number of valid subarrays ending at right is left2 - left1.

Thought Process

  1. Maintain count1 (frequencies for left1) and count2 (frequencies for left2).
  2. As we expand right, update both maps.
  3. Move left1 as far as possible such that the window [left1, right] has k distinct elements.
  4. Move left2 as far as possible such that the window [left2, right] has k-1 distinct elements.
  5. For each right, any start index in the range [left1, left2) produces a valid subarray.

Pattern: Multi-pointer Sliding Window

⏱ O(N)💾 O(N) for frequency maps.
java
public class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        Window w1 = new Window(), w2 = new Window();
        int left1 = 0, left2 = 0, res = 0;
        for (int x : nums) {
            w1.add(x); w2.add(x);
            while (w1.distinct > k) w1.remove(nums[left1++]);
            while (w2.distinct >= k) w2.remove(nums[left2++]);
            res += left2 - left1;
        }
        return res;
    }
    
    class Window {
        Map<Integer, Integer> count = new HashMap<>();
        int distinct = 0;
        void add(int x) { if (count.getOrDefault(x, 0) == 0) distinct++; count.put(x, count.getOrDefault(x, 0) + 1); }
        void remove(int x) { count.put(x, count.get(x) - 1); if (count.get(x) == 0) distinct--; }
    }
}
Approach 3

Level III: Optimal (Sliding Window - Two Pass)

Intuition

Thought Process

Finding 'exactly K' is difficult with a single sliding window because shrinking doesn't always reduce the count of distinct elements. However, finding 'at most K' is a standard sliding window problem. Using the property Exactly(K) = AtMost(K) - AtMost(K-1) simplifies the problem significantly.

Patterns

  1. Complement Rule: Exactly(K) = AtMost(K) - AtMost(K-1).
  2. Frequency Map: Track counts of each number in the current window.
⏱ O(N)💾 O(K)

Detailed Dry Run

XAtMost(X)
212
15
Result12 - 5 = 7
java
import java.util.*;
public class Main {
    public static int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    private static int atMost(int[] nums, int k) {
        int left = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            if (count.getOrDefault(nums[right], 0) == 0) k--;
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
            while (k < 0) {
                count.put(nums[left], count.get(nums[left]) - 1);
                if (count.get(nums[left]) == 0) k++;
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(subarraysWithKDistinct(new int[]{1,2,1,2,3}, 2));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the count map logic. Incrementing AtMost(K) means counting ALL subarrays with ≤K\le K distinct elements.

Frequency of the Most Frequent Element

Maximize the frequency of an element by incrementing other elements by at most k overall.

Visual Representation

nums = [1, 2, 4], k = 5 Sort: [1, 2, 4] Window [1, 2, 4] ending at 4: Cost to make all 4: (4-1) + (4-2) + (4-4) = 3 + 2 + 0 = 5 Cost 5 <= k (5)? YES! Frequency = 3
Medium

Examples

Input: nums = [1,2,4], k = 5
Output: 3
Approach 1

Level I: Brute Force

Intuition

For each element x in the array, try to make a sequence of elements equal to x ending at x. Use a sliding window to find the maximum possible frequency for each starting position.

Thought Process

  1. Sort the array.
  2. Iterate i from 0 to n-1.
  3. Iterate j from i to n-1.
  4. Calculate cost = sum(nums[j] - nums[k]) for k in [i...j].
  5. If cost <= k, maxFreq = max(maxFreq, j - i + 1).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijWindowCostMax Freq
00[1]01
01[1, 2](2-1) = 12
02[1, 2, 4](4-1)+(4-2) = 53
java
import java.util.*;
public class Main {
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, maxFreq = 1;
        for (int i = 0; i < n; i++) {
            long cost = 0;
            for (int j = i + 1; j < n; j++) {
                cost += (long)(j - i) * (nums[j] - nums[j-1]);
                if (cost <= k) maxFreq = Math.max(maxFreq, j - i + 1);
                else break;
            }
        }
        return maxFreq;
    }

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5)); // 3
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

After sorting, we can binary search for the maximum frequency L. For a fixed L, we check if any subarray of length L exists such that the cost to make all elements equal to the largest element in that subarray is ≤k\le k.

Thought Process

  1. Sort the array.
  2. Search range for frequency L is [1, n].
  3. For each mid length:
    • Use a fixed-size sliding window of size mid.
    • Cost for window [i, i + mid - 1] is nums[i + mid - 1] * mid - windowSum.
    • If any window has cost <= k, mid is possible.
  4. Adjust the search range accordingly.

Pattern: BS on Answer + Rolling Sum

⏱ O(N log N) - Sorting takes $O(N \log N)$, and binary search check takes $O(N)$ for each of the $\log N$ steps.💾 O(1) - Ignored sorting space.
java
public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 1, high = nums.length, ans = 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, k, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int[] nums, int k, int len) {
        long currentSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            if (i >= len) currentSum -= nums[i - len];
            if (i >= len - 1) {
                long cost = (long)nums[i] * len - currentSum;
                if (cost <= k) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sorting + Sliding Window)

Intuition

Thought Process

After sorting, for any window [left, right], it's always optimal to make all elements equal to the largest element nums[right]. The total cost is nums[right] * windowSize - windowSum. We maintain the largest possible window that satisfies cost <= k.

Patterns

  1. Sort then Window: Sorting allows monotonic cost calculations.
  2. Sum-based Cost: cost = lastVal * len - sum.
⏱ O(N log N)💾 O(1)

Detailed Dry Run

RNumSumCost (4*Win - Sum)Max Freq
01101
1232*2 - 3 = 12
2474*3 - 7 = 53
java
import java.util.*;
public class Main {
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, res = 1;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while ((long)nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5));
    }
}

⚠️ Common Pitfalls & Tips

Integer overflow is a common issue here. nums[right] * (right - left + 1) can exceed 2^31 - 1, so use 64-bit integers (long in Java/C++, default in Python/JS) for intermediate calculations.

Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Visual Representation

s = "eceba", k = 2 [e] [e, c] [e, c, e] (Distinct: 2 <= 2, Valid!) [e, c, e, b] (Distinct: 3 > 2, INVALID!)
Medium

Examples

Input: s = "eceba", k = 2
Output: 3
Approach 1

Level I: Brute Force

Intuition

Check every possible substring and count unique characters. Update maximum length if the count is ≤k\le k.

⏱ O(N^2)💾 O(K)
java
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> distinct = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                distinct.add(s.charAt(j));
                if (distinct.size() <= k) maxLen = Math.max(maxLen, j - i + 1);
                else break;
            }
        }
        return maxLen;
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Standard variable-size sliding window. Maintain a frequency map of characters in the window. When map size exceeds k, shrink from the left.

Pattern: Variable Size Sliding Window (K Distinct)

⏱ O(N)💾 O(K)
java
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> counts = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            counts.put(c, counts.getOrDefault(c, 0) + 1);
            while (counts.size() > k) {
                char out = s.charAt(left++);
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Count Complete Subarrays in an Array

A subarray is complete if the number of distinct elements in it is equal to the number of distinct elements in the entire array.

Visual Representation

nums = [1, 3, 1, 2, 2], Total Distinct: 3 [1, 3, 1, 2] (Distinct: 3, VALID!) [3, 1, 2] (Distinct: 3, VALID!) [1, 2, 2] (Distinct: 2, INVALID)
Medium

Examples

Input: nums = [1,3,1,2,2]
Output: 4
Approach 1

Level I: Brute Force

Intuition

Find the total number of distinct elements in the array first. Then, check every subarray and count how many are complete.

⏱ O(N^2)💾 O(N)
java
public class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> total = new HashSet<>();
        for (int x : nums) total.add(x);
        int k = total.size(), res = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> current = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                current.add(nums[j]);
                if (current.size() == k) res++;
            }
        }
        return res;
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is equivalent to finding subarrays with at least k distinct elements. We can use the 'at least' pattern or the 'total - (at most k-1)' pattern.

Calculation

Total Subarrays - Subarrays with at most (K-1) distinct elements.

⏱ O(N)💾 O(N)
java
public class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int k = set.size();
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    private int atMost(int[] nums, int k) {
        if (k == 0) return 0;
        Map<Integer, Integer> counts = new HashMap<>();
        int left = 0, res = 0;
        for (int right = 0; right < nums.length; right++) {
            counts.put(nums[right], counts.getOrDefault(nums[right], 0) + 1);
            while (counts.size() > k) {
                int out = nums[left++];
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            res += right - left + 1;
        }
        return res;
    }
}
← Previous TopicTwo Pointers
Next Topic →Linked List Patterns