SvenStack

🧩 Problem Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

1
2
3

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

💡 Brute Force (Too Slow)

Try all subarrays and calculate the sum:

• Time complexity: O(n²) to O(n³)
• ❌ Not acceptable for large inputs

💡 Optimal Approach: Kadane’s Algorithm

✨ Key Idea

At each position i, we decide:

• Either start a new subarray at i, or
• Extend the previous subarray to include nums[i]

This leads to the recurrence:

1
2

currentMax = max(nums[i], currentMax + nums[i])
globalMax = max(globalMax, currentMax)

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) – single pass
• Space Complexity: O(1) – no extra array needed

✍️ Summary

• Kadane’s Algorithm is a must-know for maximum subarray problems.
• It tracks both the current streak and global maximum.
• Often appears in interview problems and can be extended to 2D, circular arrays, etc.

If you understand this pattern, problems like “maximum profit”, “maximum product”, and “max subarray length” will feel much easier.

🧩 Problem Description

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.

If there is no such substring, return the empty string "".

Example:

1
2

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

💡 Brute Force? Not Efficient

Try all substrings of s and check if they contain all characters of t.

• Time: O(n³)
• ❌ Way too slow

💡 Optimal Approach: Sliding Window + Hash Map

🧠 Key Ideas

• Use a sliding window defined by two pointers: left and right
• Expand the window to the right until all required characters are included
• Then try to shrink the window from the left to find the minimum
• Track character counts using hash maps

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int valid = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() == need.get(c).intValue()) {
                    valid++;
                }
            }

            // Try to shrink the window
            while (valid == need.size()) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n + m)
  Where n is length of s, m is length of t
• Space Complexity: O(m)
  For the hash maps tracking counts

✍️ Summary

• A classic and foundational sliding window problem
• Mastering this helps with problems like:
  • lc-567 (Permutation in String)
  • lc-438 (Find All Anagrams)
  • lc-239 (Sliding Window Maximum)

Key challenge: tracking when the window becomes valid and shrinking it optimally.

🧩 Problem Description

You are given an array of integers nums, and there is a sliding window of size k that moves from the very left to the very right.

Return the maximum value in each window as it slides.

Example:

1
2

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

💡 Brute Force (Too Slow)

For each window, scan the k elements to find the max.

1
2
3
4
5
6
7
8

// O(n * k)
for (int i = 0; i <= nums.length - k; i++) {
    int max = Integer.MIN_VALUE;
    for (int j = i; j < i + k; j++) {
        max = Math.max(max, nums[j]);
    }
    result.add(max);
}

• ✅ Works
• ❌ Too slow when nums.length is large

💡 Optimal Approach: Monotonic Queue (Deque)

🧠 Key Idea

Use a deque (double-ended queue) to keep indices of elements in decreasing order:

• Front of deque always holds the index of the current maximum
• Before adding a new index, remove all indices whose values are less than the current number
• Remove indices that are out of the window

✅ Why a deque?

It helps us maintain a “candidate list” for the maximum of the current window — always in O(1) time per operation.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];

        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // store indices

        for (int i = 0; i < nums.length; i++) {
            // Remove indices out of the current window
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements (they’ll never be max)
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.offerLast(i); // Add current index

            // Start recording results after first window is filled
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each element is added and removed at most once from the deque
• Space Complexity: O(k)
  For the deque storing at most k elements

✍️ Summary

• The monotonic queue is a powerful technique for max/min in sliding windows
• Much more efficient than brute force (O(n) vs O(n × k))
• Common pattern in other problems like lc-862, lc-1438, and lc-1425

When dealing with “sliding window max/min”, always think of using a deque to maintain order.

🧩 Problem Description

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example:

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

💡 Brute Force (Too Slow)

Try every subarray and compute its sum.

1
2
3
4
5
6
7
8
9

// Time: O(n^2)
int count = 0;
for (int start = 0; start < nums.length; start++) {
    int sum = 0;
    for (int end = start; end < nums.length; end++) {
        sum += nums[end];
        if (sum == k) count++;
    }
}

• ❌ Time complexity: O(n²)
• Works only for small inputs

💡 Optimized Approach: Prefix Sum + HashMap

✨ Key Insight

If we know the prefix sum up to index i is sum, and we previously saw a prefix sum of sum - k,
then the subarray between those two indices sums to k.

✅ Steps

• Use a Map<Integer, Integer> to count how many times each prefix sum has occurred.
• At each step:
  • Add current number to running sum
  • Check if sum - k has appeared before → it means a subarray with sum = k ends here
  • Add sum to the map

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1); // Important: one way to get sum = 0 before starting

        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;

            if (prefixCount.containsKey(sum - k)) {
                count += prefixCount.get(sum - k);
            }

            prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
        }

        return count;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  One pass through the array
• Space Complexity: O(n)
  For the prefix sum map

✍️ Summary

• Prefix sum is a powerful technique for cumulative problems
• The hash map tracks all possible sums we’ve seen so far
• Key trick: initialize the map with {0:1} to handle cases where subarray starts at index 0

This is a high-frequency interview question and a foundation for other problems like Longest Subarray Sum, Count of Subarrays With Sum Divisible by K, etc.

🧩 Problem Description

Given two strings s and p, return all the start indices of p‘s anagrams in s.

You may return the answer in any order.

Example:

Input: s = “cbaebabacd”, p = “abc”
Output: [0, 6]

Explanation:

• The substring starting at index 0 is “cba”, an anagram of “abc”.
• The substring starting at index 6 is “bac”, another anagram.

💡 Brute Force (Not Efficient)

Generate every substring of s with length p.length() and check if it is an anagram.

• Time: O(n * k log k) if sorting is used
• ❌ Too slow for large inputs

💡 Optimized Approach: Sliding Window + Frequency Count

• Use two arrays of size 26 (for lowercase letters)
• One array stores frequency of characters in p
• The second tracks the sliding window in s
• Compare the arrays at each step (or use a match count to speed up)

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        if (s.length() < p.length()) return result;

        int[] pCount = new int[26];
        int[] sCount = new int[26];

        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            // Add new character to current window
            sCount[s.charAt(i) - 'a']++;

            // Remove character that's left the window
            if (i >= p.length()) {
                sCount[s.charAt(i - p.length()) - 'a']--;
            }

            // Compare frequency arrays
            if (Arrays.equals(pCount, sCount)) {
                result.add(i - p.length() + 1);
            }
        }

        return result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each character processed once, comparison takes O(26) = constant
• Space Complexity: O(1)
  Only fixed-size arrays used (no hashmap needed)

✍️ Summary

• This is a classic fixed-length sliding window problem
• Using character count arrays instead of sorting or hashing improves performance significantly
• Similar patterns appear in Minimum Window Substring, Permutation in String, etc.

Mastering this technique is key to solving many real-time window comparison problems efficiently.

🧩 Problem Description

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

Example:

1
2
3

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

💡 Brute Force (Too Slow)

Try all substrings and check if characters are unique.

• Time: O(n³)
• Space: O(k) for checking duplicates

✅ Correct but ❌ inefficient.

💡 Optimized Approach: Sliding Window + HashMap

We use a sliding window with two pointers:

• Expand right to include new characters
• If a duplicate is found, move left to skip past the previous occurrence
• Use a HashMap to store the last index of each character

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);

            if (map.containsKey(ch)) {
                // Move left pointer past the previous occurrence of ch
                left = Math.max(left, map.get(ch) + 1);
            }

            map.put(ch, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each character is visited at most twice.
• Space Complexity: O(k)
  Where k is the number of unique characters (e.g. 26 for lowercase letters, 128 for ASCII)

✍️ Summary

• Sliding window is ideal for “longest substring” problems.
• Key trick: update left pointer only when needed, and never move it backward.
• Using a HashMap allows constant-time character index tracking.

This is one of the most popular sliding window problems — understanding this unlocks many similar challenges like Longest Subarray with Sum ≤ k, or Minimum Window Substring.

🧩 Problem Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

1
2

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

💡 Brute Force (Too Slow)

For each index i, calculate:

• The max height to the left
• The max height to the right
• Water at i = min(leftMax, rightMax) - height[i]

But this takes O(n²) time.

💡 Optimized Approach 1: Precomputed Arrays (Prefix Max)

We use two arrays:

• leftMax[i]: max height to the left (including i)
• rightMax[i]: max height to the right (including i)

Then compute trapped water at each index.

🔢 Java Code (Prefix Max)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return total;
    }
}

⏱ Complexity

• Time: O(n)
• Space: O(n)

💡 Optimized Approach 2: Two Pointers (Space O(1))

We use two pointers (left, right) and two variables (leftMax, rightMax) to simulate the process:

• Always move the pointer with lower height
• Update leftMax or rightMax and calculate trapped water accordingly

🔢 Java Code (Two Pointers)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, total = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    total += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    total += rightMax - height[right];
                }
                right--;
            }
        }

        return total;
    }
}

⏱ Complexity

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

✍️ Summary

• This is a classic two-pointer technique problem with a space optimization.
• The intuition is that water is bounded by the shorter side.
• First solve using prefix arrays to build understanding, then optimize to two pointers.

🧩 Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.

Note: The solution must not contain duplicate triplets.

Example:

1
2

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

💡 Brute Force (Too Slow)

Try all triplets (i, j, k) and check if the sum is 0.

• Time complexity is O(n³)
• May also return duplicate triplets
• ❌ Not acceptable for large input sizes

💡 Optimal Approach (Two Pointers After Sorting)

1. Sort the array
2. Fix one element nums[i]
3. Use two pointers left and right to find pairs that sum to -nums[i]
4. Skip duplicates to ensure unique triplets

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  // Sort first
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicates for the first element
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicates for second and third elements
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return res;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n²)
  • Outer loop O(n), inner loop O(n)
• Space Complexity: O(1) (excluding the output list)

✍️ Summary

• A classic example of combining sorting + two pointers
• Always handle duplicates carefully when problems ask for “unique” results
• This technique is often reused in 4Sum, Two Sum II, etc.

Understanding this pattern gives you a powerful tool for many array + sum problems.

🧩 Problem Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that, together with the x-axis, form a container that holds the most water.

Return the maximum amount of water a container can store.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

💡 Naive Approach (Brute Force)

Try every pair (i, j) and calculate the area between them.

1
2
3
4
5
6
7
8

// Not efficient: O(n^2)
int max = 0;
for (int i = 0; i < height.length; i++) {
    for (int j = i + 1; j < height.length; j++) {
        int area = (j - i) * Math.min(height[i], height[j]);
        max = Math.max(max, area);
    }
}

• ❌ Too slow for large inputs
• ✅ Correct, but time complexity is O(n²)

💡 Optimal Approach (Two Pointers)

Use two pointers from both ends and move the shorter line inward:

• At each step, compute area between left and right
• Move the pointer with the shorter height
• Keep track of the max area seen so far

This gives us O(n) time.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int width = right - left;
            int area = h * width;
            maxArea = Math.max(maxArea, area);

            // Move the shorter line inward
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  One pass using two pointers.
• Space Complexity: O(1)
  No extra space used.

✍️ Summary

• Two-pointer technique works because width shrinks as we move, so we must maximize height wisely.
• Brute-force fails time constraint; optimal method relies on greedy shrinking of shorter side.
• One of the most elegant sliding-window-style problems.

This pattern is key for problems involving “max area”, “longest distance with constraint”, etc.

🧩 Problem Description

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

You must do this in-place without making a copy of the array.

Example:

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

💡 Naive Idea (Two-Pass Write)

• Create a new array and copy all non-zero values into it, then append zeroes.
• ✅ Correct but ❌ not in-place. So it’s invalid.

💡 Optimal In-Place Approach (Two Pointers)

We use the two-pointer technique:

• Use a nonZeroIndex to track the next position to place a non-zero.
• Traverse the array:
  • If current element is not 0, write it to nonZeroIndex, then increment nonZeroIndex.
• Finally, fill the remaining elements from nonZeroIndex to end with 0.

This is done in-place and only requires one pass + cleanup.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;

        // First pass: move all non-zero elements forward
        for (int num : nums) {
            if (num != 0) {
                nums[nonZeroIndex++] = num;
            }
        }

        // Second pass: fill the rest with zeros
        while (nonZeroIndex < nums.length) {
            nums[nonZeroIndex++] = 0;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) – single pass for placement + fill
• Space Complexity: O(1) – in-place manipulation

✍️ Summary

• The key is to use two pointers to separate writing and reading.
• Remember: “In-place” means no extra array.
• Common interview problem — focus on efficiency and clarity.

This pattern of tracking write position separately is widely used in array transformations.