SvenStack

🧩 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

🧩 Problem Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the queen placements, represented as an array of strings, where 'Q' and '.' indicate a queen and an empty space, respectively.

💬 Example

Example 1

1
2
3
4
5
6
7
8
9
10
11

Input: n = 4
Output: [
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

Example 2

1
2

Input: n = 1
Output: [["Q"]]

💡 Intuition

This is a classic backtracking problem.
We need to try placing queens row by row, ensuring each placement is valid:

1. A queen cannot share the same column.
2. A queen cannot share the same diagonal.

We backtrack:

• Place a queen in a valid column for the current row.
• Move to the next row.
• If all rows are filled, store the board as one solution.

🔢 Java Code (Backtracking)

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
46
47

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(res, board, 0);
        return res;
    }

    private void backtrack(List<List<String>> res, char[][] board, int row) {
        if (row == board.length) {
            res.add(construct(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(res, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col) {
        // check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // check upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }
}

⏱ Complexity Analysis

Let n be the board size:

• Time: O(n!) — Each row has up to n choices, pruning reduces but worst case exponential.
• Space: O(n^2) for board + O(n) recursion depth.

✍️ Summary

• Use backtracking to try placing queens row by row.
• Check columns and diagonals for validity.
• Collect solutions when all rows are filled.

Related problems

• lc-52 — N-Queens II (count solutions)

🧩 Problem Description

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

💬 Example

Example 1

1
2

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2

1
2

Input: s = "a"
Output: [["a"]]

💡 Intuition

We need to explore all possible partitions of the string and check if each substring is a palindrome.

This is a classic backtracking problem:

1. Start from index 0.
2. Expand substring [start..i].
3. If it is a palindrome, recursively partition the rest.
4. Collect valid partitions when we reach the end.

🔢 Java Code (Backtracking)

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

import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), s, 0);
        return res;
    }

    private void backtrack(List<List<String>> res, List<String> path, String s, int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(res, path, s, end + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

⏱ Complexity Analysis

Let n = s.length().

• Time: O(n × 2^n) — because each index can start a new partition cut, and palindrome check takes O(n).
• Space: O(n) recursion depth + O(n) for substring storage.

✍️ Summary

• Use backtracking to explore all partitions.
• Only continue recursion if substring is a palindrome.
• Collect valid partitions when reaching the end.

Related problems

• lc-132 — Palindrome Partitioning II (min cuts)
• lc-647 — Palindromic Substrings
• lc-5 — Longest Palindromic Substring

🧩 Problem Description

Given an m x n board of characters and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

💬 Examples

Example 1

1
2
3
4

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2

1
2
3
4

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "SEE"
Output: true

Example 3

1
2
3
4

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCB"
Output: false

💡 Intuition

This is a classic backtracking on a grid problem.

• Try to start from every cell that matches word[0].
• From each start, run DFS with index k into word.
• Mark the current cell as visited during the recursion to avoid reuse.
• Backtrack (unmark) when returning.

A tiny optimization: early-exit if remaining occurrences of a letter are impossible (optional).

🔢 Java Code (Backtracking + In-place Visited)

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 boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] b, String w, int i, int j, int k) {
        if (k == w.length()) return true;
        if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != w.charAt(k)) return false;

        char temp = b[i][j];
        b[i][j] = '#'; // mark visited

        boolean found = dfs(b, w, i + 1, j, k + 1) ||
                        dfs(b, w, i - 1, j, k + 1) ||
                        dfs(b, w, i, j + 1, k + 1) ||
                        dfs(b, w, i, j - 1, k + 1);

        b[i][j] = temp; // unmark
        return found;
    }
}

⏱ Complexity Analysis

Let L = word.length, m x n = board size.

• Time: O(m × n × 4^L) in the worst case (tight upper bound). Pruning from mismatches helps in practice.
• Space: O(L) recursion depth; in-place marking avoids extra visited arrays.

✍️ Summary

• Backtracking with DFS from any matching start cell.
• Use in-place marking to avoid revisiting the same cell in a path.
• Return true immediately when k == L.

Related problems

• lc-212 — Word Search II (Trie + backtracking)
• lc-200 — Number of Islands
• lc-79 variations — diagonal/knight moves (custom)

🧩 Problem Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

You may choose the same number from candidates an unlimited number of times.
Two combinations are unique if the frequency of at least one number is different.

Return the combinations in any order.

💬 Example

1
2

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

1
2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

💡 Approach: Backtracking with Start Index

• Sort candidates (optional, helps early pruning).
• Use DFS to build combinations:
  • Maintain start index to avoid permutations of the same combination.
  • At each step, you can reuse the same index (unlimited usage).
  • If sum == target, push the current path.
  • If sum > target, backtrack (prune).

🔢 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

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // optional but useful for pruning
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] cand, int remain, int start, List<Integer> path, List<List<Integer>> res) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            int val = cand[i];
            if (val > remain) break; // prune
            path.add(val);
            dfs(cand, remain - val, i, path, res); // i (not i+1) allows reuse
            path.remove(path.size() - 1);
        }
    }
}

⏱ Complexity Analysis

Let N = len(candidates), T = target, and assuming reasonable pruning:

• Time: ~O(number of valid combos) in practice; upper bound often expressed as O(N^(T/minVal)) in worst cases.
• Space: O(T/minVal) recursion depth + output size.

✍️ Summary

• Classic unbounded knapsack (combinations) via backtracking.
• Use a start index to avoid duplicate permutations.
• Prune when the partial sum exceeds target.

Related problems:

• lc-40 — Combination Sum II (each number used at most once, with duplicates)
• lc-216 — Combination Sum III
• lc-377 — Combination Sum IV (order matters, DP)

🧩 Problem Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

💬 Example

1
2

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

1
2

Input: n = 1
Output: ["()"]

💡 Approach: Backtracking

We need to ensure:

• We never place ')' unless there is a matching '(' available.
• The number of '(' used cannot exceed n.
• The number of ')' cannot exceed the number of '(' at any point.

So the recursive function tracks:

• open: how many '(' have been used.
• close: how many ')' have been used.

Valid recursion continues while open <= n and close <= open.

🔢 Java Code

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

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }

    private void backtrack(List<String> res, String cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            res.add(cur);
            return;
        }
        if (open < max) {
            backtrack(res, cur + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(res, cur + ")", open, close + 1, max);
        }
    }
}

⏱ Complexity Analysis

• Time: O(4^n / √n), which is the Catalan number count.
• Space: O(n) recursion depth + output size.

✍️ Summary

• Classic backtracking problem generating balanced parentheses.
• Use counts of open and close to ensure validity.
• Total solutions = nth Catalan number.

Related problems:

• lc-301 — Remove Invalid Parentheses
• lc-856 — Score of Parentheses
• lc-678 — Valid Parenthesis String

🧩 Problem Description

Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.

💬 Example

1
2

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

💡 Approach: Backtracking

We explore each element’s choice: include or exclude.
Alternatively, we can also use bitmask enumeration.

🔢 Java Code (Backtracking)

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

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

⏱ Complexity Analysis

• Time: O(n × 2^n) → there are 2^n subsets, each takes up to O(n) to copy
• Space: O(n) recursion depth (excluding output storage)

✍️ Summary

• Generates the power set of nums.
• Backtracking and bitmasking are both standard approaches.
• Useful in combinatorial problems.

Related problems:

• lc-90 — Subsets II (with duplicates)
• lc-46 — Permutations
• lc-39 — Combination Sum
• lc-40 — Combination Sum II