Algorithm Interview Top 10
278. First Bad Version (第一个错误的版本)
Description:
You are a product manager and currently leading a team to develop a new product. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one. You are given an API bool isBadVersion(version). Implement a function to find the first bad version.
Solution
Key Idea:
Binary Search. This is a classic "find the left boundary" problem.
* If mid is bad (isBadVersion(mid) == true), it could be the first one, or the first one is to the left. So right = mid.
* If mid is good, the first bad one must be to the right. So left = mid + 1.
Time Complexity: \(O(\log N)\) Space Complexity: \(O(1)\)
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
42. Trapping Rain Water (接雨水)
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.
Solution
Key Idea:
Two Pointers. Maintain left and right pointers, and left_max and right_max heights.
* Water at a position depends on min(left_max, right_max).
* Move the pointer with the smaller max height inward, calculating water for that position: max(0, current_max - height[i]).
Time Complexity: \(O(N)\) Space Complexity: \(O(1)\)
class Solution {
public int trap(int[] height) {
if (height.length == 0) return 0;
int left = 0, right = height.length - 1;
int result = 0;
int lmax = height[left], rmax = height[right];
while (left < right) {
if (height[left] <= height[right]) {
result += Math.max(0, lmax - height[left]);
lmax = Math.max(lmax, height[left]);
left++;
} else {
result += Math.max(0, rmax - height[right]);
rmax = Math.max(rmax, height[right]);
right--;
}
}
return result;
}
}
146. LRU Cache (LRU 缓存)
Description:
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement LRUCache class with get(key) and put(key, value) operations, both in O(1) time complexity.
Solution
Key Idea:
Use a Hash Map combined with a Doubly Linked List.
* Map: Stores key -> Node for O(1) access.
* Doubly Linked List: Maintains the order of elements (Head = Most Recently Used, Tail = Least Recently Used).
* On get: Move accessed node to head.
* On put: If exists, update value and move to head. If new, add to head. If over capacity, remove tail node and remove from map.
Time Complexity: \(O(1)\) for get and put. Space Complexity: \(O(capacity)\).
class LRUCache {
class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private Map<Integer, Node> cache = new HashMap<>();
private int capacity;
private Node head, tail; // Pseudo head and tail
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
if (cache.size() > capacity) {
Node tailNode = removeTail();
cache.remove(tailNode.key);
}
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private Node removeTail() {
Node res = tail.prev;
removeNode(res);
return res;
}
}
39. Combination Sum (组合总和)
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. The same number may be chosen unlimited times.
Solution
Key Idea:
Backtracking (DFS).
* Sort candidates to allow pruning.
* Use a recursive function dfs(index, target, current_path).
* For each candidate from index to end:
* If candidate > target, break (pruning).
* Add candidate to path, recurse with target - candidate (keeping same index since we can reuse).
* Backtrack (remove candidate).
Time Complexity: \(O(2^N)\) (Strictly depends on target/min_candidate). Space Complexity: \(O(target/min\_candidate)\) for recursion stack.
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
dfs(0, candidates, target, new ArrayList<>(), result);
return result;
}
private void dfs(int index, int[] candidates, int target, List<Integer> list, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] > target) break; // Pruning
list.add(candidates[i]);
dfs(i, candidates, target - candidates[i], list, result);
list.remove(list.size() - 1); // Backtrack
}
}
}
212. Word Search II (单词搜索 II)
Description:
Given an m x n board of characters and a list of strings words, return all words on the board.
Solution
Key Idea:
Trie + DFS (Backtracking).
* Build a Trie (Prefix Tree) from all words in the list to efficiently check if a path corresponds to a valid word prefix.
* Iterate through every cell in the grid. If the character matches a Trie root child, start DFS.
* In DFS: mark visited, traverse 4 directions, match Trie nodes.
* Optimization: Remove matched words from Trie (or unmark isWord) to avoid duplicates and speed up.
Time Complexity: \(O(M \cdot N \cdot 4^L)\), where L is max word length. Trie construction \(O(\sum len)\). Space Complexity: \(O(\sum len)\) for Trie.
class Solution {
class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = null;
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> result = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, result);
}
}
return result;
}
private void dfs(char[][] board, int i, int j, TrieNode p, List<String> result) {
char c = board[i][j];
if (c == '#' || p.children[c - 'a'] == null) return;
p = p.children[c - 'a'];
if (p.word != null) {
result.add(p.word);
p.word = null; // De-duplicate
}
board[i][j] = '#'; // Mark visited
if (i > 0) dfs(board, i - 1, j, p, result);
if (j > 0) dfs(board, i, j - 1, p, result);
if (i < board.length - 1) dfs(board, i + 1, j, p, result);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, result);
board[i][j] = c; // Backtrack
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.word = w;
}
return root;
}
}
56. Merge Intervals (合并区间)
Description:
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals, and return the non-overlapping intervals.
Solution
Key Idea:
Sorting.
* Sort intervals by start time.
* Iterate through sorted intervals. Maintain a current interval (initially the first one).
* If next interval overlaps with current (next.start <= current.end), merge them: current.end = max(current.end, next.end).
* Else, add current to result and set current = next.
Time Complexity: \(O(N \log N)\) for sorting. Space Complexity: \(O(N)\) (or \(O(1)\) depending on implementation).
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
result.add(current);
for (int[] interval : intervals) {
if (interval[0] <= current[1]) {
current[1] = Math.max(current[1], interval[1]);
} else {
current = interval;
result.add(current);
}
}
return result.toArray(new int[result.size()][]);
}
}
200. Number of Islands (岛屿数量)
Description:
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
Solution
Key Idea:
DFS (or BFS).
* Iterate through the grid.
* When a '1' is found, increment count and start a DFS traversal from that cell.
* During DFS, mark connected '1's as visited (e.g., set to '0') to avoid recounting.
* Check 4 directions (up, down, left, right).
Time Complexity: \(O(M \cdot N)\) Space Complexity: \(O(M \cdot N)\) (recursion stack worst case).
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // Mark as visited
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
127. Word Ladder (单词接龙)
Description:
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord. O(1) letter change per step.
Solution
Key Idea:
BFS (Breadth-First Search).
* This is a shortest path problem in an unweighted graph.
* Start from beginWord. Level 1 is neighbors (differ by 1 char).
* Use a Queue for BFS and a Set for wordList (to check existence in O(1)).
* To find neighbors efficiently: for each char in current word, try replacing with 'a'-'z'. If resulting word is in Set, it's a neighbor. Remove visited words from Set to prevent cycles.
Time Complexity: \(O(M^2 \cdot N)\), where M is word length, N is number of words. Space Complexity: \(O(M \cdot N)\).
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String current = queue.poll();
if (current.equals(endWord)) return level;
char[] chars = current.toCharArray();
for (int j = 0; j < chars.length; j++) {
char original = chars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[j] = c;
String next = new String(chars);
if (set.contains(next)) {
queue.offer(next);
set.remove(next); // Mark visited
}
}
chars[j] = original; // Restore
}
}
level++;
}
return 0;
}
}
1254. Number of Closed Islands (统计封闭岛屿的数目)
Description:
Given a 2D grid consists of 0s (land) and 1s (water). Return the number of closed islands. A closed island is an island totally (all left, top, right, bottom) surrounded by 1s (cannot touch boundary).
Solution
Key Idea:
DFS with Boundary Check.
* Islands connected to the boundary are NOT closed.
* First, perform DFS on all 0s connected to the boundary (i=0, i=m-1, j=0, j=n-1) and turn them into 1s (or mark visited).
* Then, iterate through the remaining grid. Any remaining 0 belongs to a closed island. Perform DFS to count them.
Time Complexity: \(O(M \cdot N)\) Space Complexity: \(O(M \cdot N)\)
class Solution {
public int closedIsland(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
// Flood fill boundary islands
for (int i = 0; i < rows; i++) {
dfs(grid, i, 0);
dfs(grid, i, cols - 1);
}
for (int j = 0; j < cols; j++) {
dfs(grid, 0, j);
dfs(grid, rows - 1, j);
}
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(int[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == 1) {
return;
}
grid[r][c] = 1; // Mark as water/visited
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}
5. Longest Palindromic Substring (最长回文子串)
Description:
Given a string s, return the longest palindromic substring in s.
Solution
Key Idea:
Expand Around Center.
* A palindrome mirrors around its center. A center can be a character (odd length like "aba") or between two characters (even length like "abba").
* Iterate through each character i as a center.
* Expand for odd length (i, i) and even length (i, i+1).
* Track max length and start index.
Time Complexity: \(O(N^2)\) Space Complexity: \(O(1)\)
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); // Odd length
int len2 = expandAroundCenter(s, i, i + 1); // Even length
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}