SvenStack

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

🧩 Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

💡 Brute Force? Not Enough

A naive solution would be to:

• Sort the array → O(n log n)
• Iterate to find longest streak

This fails the O(n) constraint, so we need a better approach.

💡 Optimized Approach (Using HashSet)

To achieve linear time:

1. Store all numbers in a HashSet for constant-time lookups.
2. Iterate through the array, and only start a new sequence if num - 1 is not in the set (i.e., it’s the start of a sequence).
3. Expand forward: check how long the consecutive streak goes.
4. Track the max length.

🔢 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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLen = 0;

        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;

                while (set.contains(current + 1)) {
                    current++;
                    length++;
                }

                maxLen = Math.max(maxLen, length);
            }
        }

        return maxLen;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each number is added and checked in constant time.
• Space Complexity: O(n)
  To store all unique numbers in the HashSet.

✍️ Summary

• This is a great example of using HashSet to eliminate redundant computation.
• The key optimization is only starting a streak when num - 1 is not in the set.
• Sorting is too slow for this problem — always check time constraints carefully.

This technique of using hash-based lookup to replace sorting is common in many “O(n)” constraint problems.

🧩 Problem Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all original letters exactly once.

Example:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

💡 Approach

🔸 Idea

Two strings are anagrams if their sorted character arrays are the same.

So we can:

• Sort each string.
• Use a hash map to group original strings by their sorted version.

🔧 Why Hash Table?

The sorted string acts as a unique key for anagram groups.
We use a Map<String, List<String>> to group anagrams efficiently.

🔢 Java Code

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

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars); // sorted string

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n * k log k)
  • n = number of strings
  • k = max length of a string (due to sorting)
• Space Complexity: O(n * k)
  • To store grouped anagrams in a hash map

✍️ Summary

• Key idea: Use the sorted string as hash map key.
• Efficient and elegant hash table application.
• Classic grouping problem using Java Map and sorting.

🧩 Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

💡 Naive Approach (Brute Force)

The most straightforward idea is to check all pairs using two nested loops.
This guarantees we find the solution, but it’s inefficient for large arrays.

🔢 Java Code – Brute Force

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {}; 
    }
}

⏱ Complexity

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

⚠️ This solution does not scale — it fails performance constraints on large inputs.

💡 Optimized Approach (Hash Map)

To reduce time complexity, we use a hash map to store values we’ve seen and their indices.
While iterating, we check whether target - current has already been seen.

🔎 Key Points

• In practice, hash tables are fast — usually O(1) for most operations.
• Worst case happens when many keys collide (bad hash function or high load factor).
• Java’s HashMap uses a red-black tree (Deeper explanation will be covered in a future post.) for long collision chains (O(log n) worst case for search).

🔢 Java Code – Hash Map

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // hashtable always 
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] {seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[] {}; 
    }
}

⏱ Complexity

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

✅ Efficient and suitable for large datasets.

✍️ Summary

• Always start with brute force to validate your logic.
• Then optimize using data structures like hash maps.