SvenStack

🧩 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

🧩 Problem Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
Return the answer in any order.

💬 Example

1
2

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

💡 Approach: Backtracking

This is a classic backtracking problem.
Each digit corresponds to a set of characters (phone keypad mapping).
We explore all possible combinations by building strings recursively.

🔢 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

import java.util.*;

class Solution {
    private static final String[] KEYS = {
        "",    "",    "abc",  "def", "ghi", 
        "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) return result;
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = KEYS[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, index + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

⏱ Complexity Analysis

• Time: O(4^n) → each digit can map to up to 4 letters
• Space: O(n) recursion depth

✍️ Summary

• Maps digits to characters based on phone keypad.
• Uses backtracking to explore all valid combinations.
• Very common interview question.

Related problems:

• lc-22 — Generate Parentheses
• lc-39 — Combination Sum
• lc-46 — Permutations
• lc-78 — Subsets

🧩 Problem Description

Given an array nums of distinct integers, return all the possible permutations.
You can return the answer in any order.

💬 Example

1
2

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

💡 Approach: Backtracking

We use backtracking to generate all permutations by swapping elements or by building a temporary path with used flags.

🔢 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>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, path, used, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

⏱ Complexity Analysis

• Time: O(n × n!) → each permutation takes O(n) to build, total n! permutations
• Space: O(n) recursion depth + O(n) used flags

✍️ Summary

• Classic backtracking problem.
• Generates all n! permutations.
• Useful in problems involving ordering, scheduling, or searching solution spaces.

Related problems:

• lc-47 — Permutations II (with duplicates)
• lc-77 — Combinations
• lc-78 — Subsets
• lc-90 — Subsets II

🧩 Problem Description

A trie (pronounced try) or prefix tree is a tree data structure used to efficiently store and search strings in a dataset of strings.

Implement the Trie class:

• Trie() initializes the object.
• void insert(String word) inserts the string word into the trie.
• boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) returns true if there is a previously inserted string word that starts with the given prefix.

💬 Example

1
2
3
4
5
6

Input:
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

Output:
[null,null,true,false,true,null,true]

💡 Approach: Trie Node Structure

We build a tree where each node contains up to 26 children (for each lowercase letter).
Each node also keeps a boolean flag isEnd to mark the end of a word.

🔢 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
46
47
48
49

class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

⏱ Complexity Analysis

• Insert: O(L), where L = length of the word
• Search: O(L)
• StartsWith: O(P), where P = length of the prefix
• Space: O(N * L), where N = number of words, L = average word length

✍️ Summary

• Trie is a powerful data structure for string searching.
• Operations are efficient: O(L).
• Widely used in autocomplete, spell check, IP routing, and word games.

Related problems:

• lc-211 — Design Add and Search Words Data Structure
• lc-212 — Word Search II
• lc-648 — Replace Words
• lc-720 — Longest Word in Dictionary

🧩 Problem Description

There are numCourses courses labeled from 0 to numCourses - 1.
You are given an array prerequisites where prerequisites[i] = [a, b] indicates that to take course a you must first take course b.

Return true if you can finish all courses. Otherwise, return false.

This is essentially asking whether the directed graph has a cycle. If there is no cycle, a topological ordering exists and you can finish all courses.

💬 Examples

Example 1

1
2
3

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0 first, then course 1.

Example 2

1
2
3

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 0 depends on 1 and 1 depends on 0 → cycle.

💡 Approach 1: Kahn’s Algorithm (BFS Topological Sort)

• Build adjacency list and in-degree array.
• Push all nodes with in-degree 0 into a queue.
• Pop from queue, decrement in-degree of neighbors, and push any that drop to 0.
• If we process all nodes, there is no cycle; otherwise, a cycle exists.

🔢 Java Code (BFS)

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 boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());

        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];
            graph.get(b).add(a);
            indeg[a]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);

        int taken = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            taken++;
            for (int nxt : graph.get(cur)) {
                if (--indeg[nxt] == 0) q.offer(nxt);
            }
        }
        return taken == numCourses;
    }
}

💡 Approach 2: DFS Cycle Detection (3-color / visiting states)

• Maintain a state[] array: 0 = unvisited, 1 = visiting, 2 = visited.
• During DFS, if we reach a node marked visiting (1), we found a cycle.
• If DFS finishes without back edges, there is no cycle.

🔢 Java Code (DFS)

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

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) graph.get(p[1]).add(p[0]);

        int[] state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i, graph, state)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u, List<List<Integer>> g, int[] state) {
        state[u] = 1; // visiting
        for (int v : g.get(u)) {
            if (state[v] == 1) return true;           // back edge
            if (state[v] == 0 && hasCycle(v, g, state)) return true;
        }
        state[u] = 2; // visited
        return false;
    }
}

⏱ Time and Space Complexity

• BFS (Kahn):
  • Time: O(V + E)
  • Space: O(V + E) for graph + queue + indegree
• DFS:
  • Time: O(V + E)
  • Space: O(V + E) for graph + recursion stack

V = numCourses, E = len(prerequisites).

✍️ Summary

• The problem reduces to cycle detection in a directed graph.
• Kahn (BFS) is usually simplest when you just need a yes/no; it also gives a topo order.
• DFS 3-color is elegant and stack-based.
• Pick based on your preference and constraints.

Related problems

• lc-210 — Course Schedule II (return topological order)
• lc-261 — Graph Valid Tree (undirected)
• lc-802 — Find Eventual Safe States