SvenStack

🧩 Problem Description

The MedianFinder class:

• MedianFinder() initializes the object.
• void addNum(int num) adds the integer num to the data structure.
• double findMedian() returns the median of all elements so far.

💬 Examples

Example 1

1
2
3
4
5
6

Input:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

Output:
[null, null, null, 1.5, null, 2.0]

💡 Intuition

To efficiently find the median:

• Use two heaps:

  • A max-heap (left) to store the smaller half of numbers.
  • A min-heap (right) to store the larger half of numbers.

• Balancing rule:

  • Either both heaps have equal size, or left has one more element.
  • Median = root of max-heap (if odd) or average of roots (if even).

🔢 Java Code (Two Heaps)

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

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> left;  // max-heap
    private PriorityQueue<Integer> right; // min-heap

    public MedianFinder() {
        left = new PriorityQueue<>(Collections.reverseOrder());
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll());
        
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        } else {
            return (left.peek() + right.peek()) / 2.0;
        }
    }
}

⏱ Complexity Analysis

• Time (per operation): O(log n)
• Space: O(n)

✍️ Summary

• Two Heaps maintain balance between left and right halves.
• Ensures O(log n) per insertion and O(1) median query.

Related problems

• lc-480 — Sliding Window Median
• lc-703 — Kth Largest Element in a Stream
• lc-220 — Contains Duplicate III

🧩 Problem Description

Given an integer array nums and an integer k, return the k most frequent elements.
You may return the answer in any order.

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

💡 Intuition

Two common solutions:

1. Heap (PriorityQueue):

   • Count frequencies using HashMap.
   • Maintain a min-heap of size k.
   • Time: O(n log k).

2. Bucket Sort:

   • Frequencies range from 1 to n.
   • Place numbers into buckets indexed by frequency.
   • Traverse from high frequency to low until k elements are collected.
   • Time: O(n).

🔢 Java Code (Heap)

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

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            heap.offer(new int[]{entry.getKey(), entry.getValue()});
            if (heap.size() > k) {
                heap.poll();
            }
        }
        
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = heap.poll()[0];
        }
        return result;
    }
}

🔢 Java Code (Bucket Sort)

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

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : freqMap.keySet()) {
            int freq = freqMap.get(key);
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(key);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
            if (buckets[i] != null) {
                result.addAll(buckets[i]);
            }
        }
        
        return result.stream().mapToInt(x -> x).toArray();
    }
}

⏱ Complexity Analysis

Heap Solution

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

Bucket Sort Solution

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

✍️ Summary

• Use heap for balanced performance.
• Use bucket sort for O(n) solution.

Related problems

• lc-215 — Kth Largest Element in an Array
• lc-451 — Sort Characters By Frequency
• lc-973 — K Closest Points to Origin

🧩 Problem Description

Given an integer array nums and an integer k, return the k-th largest element in the array.
Note: It is the k-th largest element in the sorted order, not the k-th distinct element.

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

💡 Intuition

There are two common approaches:

1. Heap (Min-Heap of size k):

   • Maintain a heap of the largest k elements.
   • The root of the heap is the answer.
   • Time: O(n log k).

2. Quickselect (Hoare’s selection algorithm):

   • Similar to quicksort partitioning.
   • Average time: O(n), worst-case O(n²).
   • More efficient in practice.

🔢 Java Code (Heap)

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

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

🔢 Java Code (Quickselect)

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 findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, 0, n - 1, n - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int p = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                swap(nums, i, p);
                p++;
            }
        }
        swap(nums, p, right);
        
        if (p == k) return nums[p];
        else if (p < k) return quickSelect(nums, p + 1, right, k);
        else return quickSelect(nums, left, p - 1, k);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

⏱ Complexity Analysis

Heap Solution

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

Quickselect Solution

• Time: O(n) on average, O(n²) worst-case
• Space: O(1)

✍️ Summary

• Use min-heap for simplicity.
• Use quickselect for optimal performance on average.

Related problems

• lc-347 — Top K Frequent Elements
• lc-973 — K Closest Points to Origin
• lc-703 — Kth Largest Element in a Stream

🧩 Problem Description

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

💬 Examples

Example 1

1
2
3

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by bars with height 5 and 6, width = 2 → area = 10.

Example 2

1
2

Input: heights = [2,4]
Output: 4

💡 Intuition

We want to find the largest rectangle area in a histogram.
A monotonic increasing stack helps track the left and right boundaries for each bar:

• Traverse the bars.
• While current height is less than the top of stack, pop from stack and calculate area.
• Area = poppedHeight * (currentIndex - stackTopAfterPop - 1).
• Push current index onto the stack.
• Add sentinel 0 at the end to flush out remaining bars.

🔢 Java Code (Monotonic Stack)

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

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            int h = (i == n ? 0 : heights[i]);
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

⏱ Complexity Analysis

• Time: O(n) — each bar pushed and popped at most once.
• Space: O(n) — stack storage.

✍️ Summary

• Use monotonic increasing stack to efficiently compute rectangle areas.
• Each bar defines a rectangle extended until a smaller bar appears.

Related problems

• lc-85 — Maximal Rectangle
• lc-42 — Trapping Rain Water
• lc-239 — Sliding Window Maximum

🧩 Problem Description

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature.
If there is no future day for which this is possible, keep answer[i] == 0 instead.

💬 Examples

Example 1

1
2

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2

1
2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3

1
2

Input: temperatures = [30,60,90]
Output: [1,1,0]

💡 Intuition

We can use a monotonic decreasing stack to keep track of temperatures indices:

• Iterate through the array.
• For each day, check if current temperature is higher than the one on top of the stack.
• If yes, pop the index and calculate the difference in days.
• Push the current index onto the stack.

🔢 Java Code (Monotonic Stack)

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

import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        
        return answer;
    }
}

⏱ Complexity Analysis

• Time: O(n) — each element pushed and popped at most once.
• Space: O(n) — stack storage.

✍️ Summary

• Use monotonic decreasing stack to track indices of temperatures.
• For each warmer day, update result for all previous colder days.

Related problems

• lc-496 — Next Greater Element I
• lc-503 — Next Greater Element II
• lc-42 — Trapping Rain Water

🧩 Problem Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Note that k is guaranteed to be a positive integer.

💬 Examples

Example 1

1
2

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2

1
2

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3

1
2

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4

1
2

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

💡 Intuition

We can use two stacks to decode the string:

• One stack for numbers (repeat counts).
• One stack for strings (previous built results).
• Traverse the input string:
  • If digit → build number.
  • If [ → push current string and number to stacks.
  • If ] → pop count and previous string, repeat current substring and append.
  • Otherwise → append characters to current string.

🔢 Java Code (Stack Approach)

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

import java.util.*;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> counts = new Stack<>();
        Stack<StringBuilder> resultStack = new Stack<>();
        StringBuilder current = new StringBuilder();
        int k = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                counts.push(k);
                resultStack.push(current);
                current = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                int count = counts.pop();
                StringBuilder decoded = resultStack.pop();
                for (int i = 0; i < count; i++) {
                    decoded.append(current);
                }
                current = decoded;
            } else {
                current.append(c);
            }
        }
        
        return current.toString();
    }
}

⏱ Complexity Analysis

• Time: O(n) — each character processed once.
• Space: O(n) — stacks for numbers and strings.

✍️ Summary

• Use two stacks: one for counts, one for partial strings.
• Build substrings iteratively while handling nested brackets.

Related problems

• lc-224 — Basic Calculator
• lc-227 — Basic Calculator II
• lc-20 — Valid Parentheses

🧩 Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement all the functions of the stack such that each function works in O(1) time complexity.

💬 Examples

Example 1

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

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

💡 Intuition

We need a stack that can return the minimum element in constant time.

• Use two stacks:
  1. One for storing all values.
  2. Another for storing the current minimum at each level.
• When pushing, also update the min stack with the smaller value between new element and current min.
• When popping, remove from both stacks.

🔢 Java Code (Two Stacks)

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 MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

⏱ Complexity Analysis

• Time: O(1) for all operations (push, pop, top, getMin).
• Space: O(n) — extra stack to track minimums.

✍️ Summary

• Maintain a parallel min stack to track current minimum.
• Ensures constant time retrieval of min element.

Related problems

• lc-716 — Max Stack
• lc-20 — Valid Parentheses

🧩 Problem Description

Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

💬 Examples

Example 1

1
2

Input: s = "()"
Output: true

Example 2

1
2

Input: s = "()[]{}"
Output: true

Example 3

1
2

Input: s = "(]"
Output: false

Example 4

1
2

Input: s = "([)]"
Output: false

Example 5

1
2

Input: s = "{[]}"
Output: true

💡 Intuition

We can use a stack to track opening brackets:

• When encountering an opening bracket, push it onto the stack.
• When encountering a closing bracket, check if it matches the top of the stack.
• If not matched or stack is empty, return false.
• At the end, if the stack is empty, the string is valid.

🔢 Java Code (Stack)

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

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

⏱ Complexity Analysis

• Time: O(n) — each character processed once.
• Space: O(n) — in worst case stack holds all characters.

✍️ Summary

• Use stack to validate parentheses.
• Each closing bracket must match the latest opening bracket.

Related problems

• lc-22 — Generate Parentheses
• lc-32 — Longest Valid Parentheses

🧩 Problem Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall runtime complexity should be O(log (m+n)).

💬 Examples

Example 1

1
2

Input: nums1 = [1,3], nums2 = [2]
Output: 2.0

Example 2

1
2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5

Example 3

1
2

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.0

💡 Intuition

We need to find the k-th smallest element in two sorted arrays efficiently.

• Partition both arrays so that the left half and right half are balanced.
• Ensure all elements in the left half are ≤ all elements in the right half.
• Depending on the total length being odd/even, return middle or average of two middle values.

This can be solved with binary search on the partition.

🔢 Java Code (Binary Search Partition)

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

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length, n = nums2.length;
        int left = 0, right = m;
        
        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;
            
            int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            
            if (left1 <= right2 && left2 <= right1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
                } else {
                    return Math.max(left1, left2);
                }
            } else if (left1 > right2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        throw new IllegalArgumentException();
    }
}

⏱ Complexity Analysis

• Time: O(log(min(m, n))) — binary search only on smaller array.
• Space: O(1).

✍️ Summary

• Partition both arrays using binary search.
• Compare partition edges to decide where to move.
• Handle odd/even total length cases.

Related problems

• lc-33 — Search in Rotated Sorted Array
• lc-153 — Find Minimum in Rotated Sorted Array

🧩 Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.

For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if rotated 4 times.
• [0,1,2,4,5,6,7] if rotated 7 times.

Given the rotated sorted array nums of unique elements, return the minimum element of this array.

You must write an algorithm with O(log n) runtime complexity.

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

Example 3

1
2

Input: nums = [11,13,15,17]
Output: 11

💡 Intuition

The minimum value is the “pivot point” where rotation happens.

• If nums[mid] > nums[right], the minimum lies in the right half.
• Otherwise, it lies in the left half (including mid).

This ensures O(log n) with binary search.

🔢 Java Code (Binary Search)

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

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

⏱ Complexity Analysis

• Time: O(log n) — binary search.
• Space: O(1) — constant space.

✍️ Summary

• Use binary search to find the pivot (minimum element).
• Compare nums[mid] with nums[right] to decide which half to search.

Related problems

• lc-33 — Search in Rotated Sorted Array
• lc-154 — Find Minimum in Rotated Sorted Array II