SvenStack

🧩 Problem Description

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example:

1
2

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

💡 Brute Force (Not Acceptable)

• Sort the array → O(n log n)
• Check for the first missing positive
• ❌ Not allowed by problem constraints

💡 Optimal Approach: Index Placement (Cyclic Sort Pattern)

✨ Key Idea

• If nums[i] is in range [1, n], ideally it should be placed at nums[nums[i] - 1].
• Swap elements until every number is placed correctly.
• Then scan once to find the first index i where nums[i] != i + 1.

🔢 Java Code

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

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // Swap nums[i] with nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each number is swapped at most once.
• Space Complexity: O(1)
  In-place swaps only.

✍️ Summary

• This is a textbook application of the cyclic sort pattern.
• Focus on the fact that only numbers within [1, n] matter.
• Understand why O(n) solutions are possible by leveraging in-place swaps.

Problems like this appear often in data structure interviews where array indexing and in-place manipulation are tested.

🧩 Problem Description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The algorithm must run in O(n) time and without using division.

Example:

1
2

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

💡 Brute Force (Not Acceptable)

For each index, multiply all other elements:

• Time: O(n²)
• ❌ Not efficient for large inputs

💡 Optimal Approach: Prefix Product + Suffix Product

✨ Key Idea

We calculate:

• prefix[i]: product of all elements before index i
• suffix[i]: product of all elements after index i

Then:
answer[i] = prefix[i] * suffix[i]

But we can optimize to use only one output array.

🔢 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[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Step 1: Left products
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Step 2: Right products (suffix) and multiply on the fly
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right *= nums[i];
        }

        return answer;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Two passes over the array.
• Space Complexity: O(1) extra space (output array does not count as extra space in the problem statement)

✍️ Summary

• This is a classic prefix + suffix product pattern.
• No division is used.
• Space-optimized by combining both steps into a single result array.

Learning this approach helps with problems involving “all elements except…” patterns, such as sum, XOR, or custom aggregates.

🧩 Problem Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example:

1
2

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

💡 Naive Approach (Extra Array)

• Copy elements into a new array

• Place each element at (i + k) % n index

• Copy back to nums

• ✅ Works

• ❌ Uses O(n) extra space

💡 Optimal Approach: Reverse Method

🧠 Key Idea

1. Reverse the whole array
2. Reverse the first k elements
3. Reverse the remaining n - k elements

✅ Why It Works

Reversing segments restores them into rotated order.

🔢 Java Code

🔢 Java Code

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

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;  // Handle k >= n

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)
  In-place rotation using reversals

✍️ Summary

• This problem demonstrates an important array manipulation pattern.
• The reverse trick is efficient and widely applicable in other rotation-related problems.
• Avoid extra space when possible by reusing in-place algorithms.

Understand both the logic and implementation of reverse-in-place operations — this comes up in multiple array and string questions!

🧩 Problem Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

1
2

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

💡 Brute Force? Not Ideal

You could check every pair and try to merge, but:

• You would need to compare all combinations
• ❌ Time complexity is too high (O(n²) or worse)

💡 Optimal Approach: Sort + Merge

✨ Key Idea

1. Sort the intervals by start time
2. Iterate through intervals:
   • If the current interval overlaps with the previous one, merge them
   • Otherwise, add the previous interval to result

This approach ensures that we process all intervals in a linear scan after sorting.

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];

            if (current[1] >= next[0]) {
                // Merge overlapping intervals
                current[1] = Math.max(current[1], next[1]);
            } else {
                result.add(current);
                current = next;
            }
        }

        result.add(current); // Add the last interval

        return result.toArray(new int[result.size()][]);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n log n)
  For sorting the intervals
• Space Complexity: O(n)
  For the result list (output), auxiliary space is constant

✍️ Summary

• This is a classic sort-then-scan problem
• Make sure to handle edge cases like fully nested intervals (e.g., [1,10], [2,5])
• Very common pattern in scheduling, calendar, and timeline problems

Sorting followed by greedy merging is a powerful approach for interval problems.

🧩 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.