SvenStack

🧩 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

🧩 Problem Description

There is an integer array nums sorted in ascending order (with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length).

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not.

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

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

Example 3

1
2

Input: nums = [1], target = 0
Output: -1

💡 Intuition

Since the array is rotated sorted, one half is always sorted:

• If the target lies within the sorted half, continue searching in that half.
• Otherwise, search in the other half.

This is a modified binary search.

🔢 Java Code (Binary Search)

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

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

            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

⏱ Complexity Analysis

• Time: O(log n) — modified binary search.
• Space: O(1) — no extra space.

✍️ Summary

• Use binary search with conditions to detect the sorted half.
• Move search boundaries accordingly.

Related problems

• lc-34 — Find First and Last Position of Element
• lc-81 — Search in Rotated Sorted Array II

🧩 Problem Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

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

💬 Examples

Example 1

1
2

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2

1
2

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3

1
2

Input: nums = [], target = 0
Output: [-1,-1]

💡 Intuition

Since the array is sorted, we can use binary search to find:

• The leftmost index of the target.
• The rightmost index of the target.

This avoids scanning linearly and ensures O(log n) complexity.

🔢 Java Code (Binary Search)

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findBound(nums, target, true);
        int right = findBound(nums, target, false);
        return new int[]{left, right};
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0, right = nums.length - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                ans = mid;
                if (isFirst) {
                    right = mid - 1; // keep searching left
                } else {
                    left = mid + 1; // keep searching right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

⏱ Complexity Analysis

• Time: O(log n) — two binary searches.
• Space: O(1) — constant extra space.

✍️ Summary

• Use two binary searches to find the first and last occurrence.
• If target not found, return [-1, -1].

Related problems

• lc-35 — Search Insert Position
• lc-704 — Binary Search

🧩 Problem Description

You are given an m x n integer matrix matrix with the following properties:

1. Each row is sorted in ascending order.
2. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix or false otherwise.

💬 Examples

Example 1

1
2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

1
2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

💡 Intuition

The matrix has a special structure:

• If we flatten it into a single array, it is fully sorted.
• Thus, we can apply binary search over the virtual array.

Mapping from index in flattened array:

• row = mid / n
• col = mid % n

🔢 Java Code (Binary Search)

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

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = matrix[mid / n][mid % n];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

⏱ Complexity Analysis

• Time: O(log(m × n)) — binary search on m*n elements.
• Space: O(1) — only pointers are used.

✍️ Summary

• Flatten the 2D matrix into a sorted 1D array conceptually.
• Apply binary search on indices.

Related problems

• lc-240 — Search a 2D Matrix II
• lc-33 — Search in Rotated Sorted Array

🧩 Problem Description

Given a sorted array of distinct integers and a target value, return the index if the target is found.
If not, return the index where it would be if it were inserted in order.

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

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

Example 3

1
2

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

💡 Intuition

The array is sorted, so binary search is the best choice.

• Maintain two pointers left and right.
• While left <= right, check the middle value.
• If nums[mid] == target, return mid.
• If nums[mid] < target, move left = mid + 1.
• Else move right = mid - 1.

Finally, left will be the correct insert position.

🔢 Java Code (Binary Search)

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

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

⏱ Complexity Analysis

• Time: O(log n) due to binary search.
• Space: O(1) since no extra memory is used.

✍️ Summary

• Use binary search instead of linear scan.
• If target not found, the correct insert position is left.

Related problems

• lc-34 — Find First and Last Position of Element in Sorted Array
• lc-704 — Binary Search