Most O(n²) loops keep asking the same three things. Have I seen this? How often? What was the sum up to here? A hash map answers the first two in O(1), and a prefix array the third. Ten moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
A hash set files x under bucket h(x). Asking for x reads that bucket only, so a lookup costs O(1) on average.
A hash set with buckets x % 4 holds 8, 3 and 12. A lookup of 20 compares it with which values?
20 % 4 = 0, the bucket of 8 and 12. 3 is in bucket 3, which is never read.
Why is a hash-set lookup O(1) on average but O(n) in the worst case?
With a bad hash, all n values share a bucket and a lookup scans every one.
GIVEN · ASKEDAn integer array. Return true if any value appears at least twice.
“Does any value appear twice?” One question per value: have I seen it before?
Keep a set of what has been read. A value already in the set is the duplicate.
bool containsDuplicate(vector<int>& nums) { unordered_set<int> seen; for (int x : nums) { if (seen.count(x)) return true; // read before seen.insert(x); } return false; }
public boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int x : nums) if (!seen.add(x)) return true; // add() is false if x was there return false; }
def containsDuplicate(nums): seen = set() for x in nums: if x in seen: return True # read before seen.add(x) return False
Sorting when you could hash. Sorting and comparing neighbours is correct, but O(n log n), and it reorders the input.
GIVEN · ASKEDA 9 × 9 Sudoku board, partly filled. Return true if no row, column or 3 × 3 box repeats a digit among its filled cells.
Each digit may appear once per row, once per column and once per 3 × 3 box. Three kinds of “seen before”.
One set per row, column and box, or one set of tagged keys. A digit already in any of its three units breaks the rule.
bool isValidSudoku(vector<vector<char>>& board) { bool row[9][9] = {}, col[9][9] = {}, box[9][9] = {}; // [unit][digit] for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) { if (board[r][c] == '.') continue; int d = board[r][c] - '1', b = (r / 3) * 3 + c / 3; if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } return true; }
public boolean isValidSudoku(char[][] board) { boolean[][] row = new boolean[9][9], col = new boolean[9][9], box = new boolean[9][9]; for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) { if (board[r][c] == '.') continue; int d = board[r][c] - '1', b = (r / 3) * 3 + c / 3; if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } return true; }
def isValidSudoku(board): seen = set() for r in range(9): for c in range(9): d = board[r][c] if d == '.': continue keys = (('row', r, d), ('col', c, d), ('box', r // 3, c // 3, d)) if any(k in seen for k in keys): return False # d is already in one of its units seen.update(keys) return True
Solving the puzzle. The question is only whether the filled cells break a rule. A board can be valid and still have no solution.
A 5 sits at row 4, column 7 of a Sudoku board. Which box is it in, with b = (r / 3) · 3 + c / 3?
(4 / 3) · 3 + 7 / 3 = 3 + 2 = 5: the middle band of boxes, the right column.
Sort a word's letters and every anagram gives the same key. A map from key to list collects each group in one pass.
Which key wrongly puts two strings that are not anagrams in one group?
a + d and b + c have the same total, so ad and bc share it.
groupAnagrams(["abc", "bca", "cab", "abd"]). How many groups?
abc, bca and cab all sort to abc. abd has its own key.
The words are long. Which key avoids sorting each one?
Counting is O(m) per word, and the counts fix the anagram group exactly.
GIVEN · ASKEDAn array of strings. Group the anagrams together, in any order.
“Group the strings that are anagrams.” Equal as multisets of letters, in any order.
Give every string a key that ignores order: its letters sorted. Anagrams get the same key, and a map from key to list collects them.
vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> g; for (string& s : strs) { string key = s; sort(key.begin(), key.end()); // anagrams share this key g[key].push_back(s); } vector<vector<string>> out; for (auto& p : g) out.push_back(p.second); return out; }
public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> g = new HashMap<>(); for (String s : strs) { char[] a = s.toCharArray(); Arrays.sort(a); // anagrams share this key g.computeIfAbsent(new String(a), x -> new ArrayList<>()).add(s); } return new ArrayList<>(g.values()); }
def groupAnagrams(strs): g = {} for s in strs: key = ''.join(sorted(s)) # anagrams share this key g.setdefault(key, []).append(s) return list(g.values())
A key that collides. The sum of the letters, or the set of letters, gives "ab" and "aab" or "ad" and "bc" the same key. The key must determine every count.
Pass 1 counts each letter. Pass 2 reads the string again and stops at the first count of 1. A count is final only at the end.
No value appears more than n times, so bucket[f] holds the values seen f times. Read from the top down: no sort.
firstUniqChar("aabb")?
Both letters appear twice, so pass 2 never finds a count of 1.
GIVEN · ASKEDA string of lowercase letters. Return the index of the first character that appears exactly once, or −1.
“The first character that does not repeat.” Whether it repeats depends on the whole string.
Count every letter in one pass. Then read the string again and return the first index whose letter has count 1.
int firstUniqChar(string s) { int cnt[26] = {}; for (char c : s) cnt[c - 'a']++; // pass 1: count for (int i = 0; i < (int)s.size(); i++) if (cnt[s[i] - 'a'] == 1) return i; // pass 2: read the counts return -1; }
public int firstUniqChar(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) cnt[c - 'a']++; // pass 1: count for (int i = 0; i < s.length(); i++) if (cnt[s.charAt(i) - 'a'] == 1) return i; // pass 2: read the counts return -1; }
def firstUniqChar(s): cnt = {} for c in s: cnt[c] = cnt.get(c, 0) + 1 # pass 1: count for i, c in enumerate(s): if cnt[c] == 1: return i # pass 2: read the counts return -1
Deciding during the first pass. A letter with count 1 so far can still get a second copy later. Only finished counts are safe to read.
GIVEN · ASKEDAn integer array and k. Return the k most frequent values, in any order; the answer is unique.
“The k most frequent values.” Counts are at most n, so they can index an array.
Count each value. Put each value in bucket[count]. Read the buckets from count n down until k values are out.
vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> cnt; for (int x : nums) cnt[x]++; vector<vector<int>> bucket(nums.size() + 1); // bucket[f]: seen f times for (auto& p : cnt) bucket[p.second].push_back(p.first); vector<int> out; for (int f = nums.size(); f >= 1; f--) for (int x : bucket[f]) { out.push_back(x); if ((int)out.size() == k) return out; } return out; }
public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) cnt.merge(x, 1, Integer::sum); List<List<Integer>> bucket = new ArrayList<>(); for (int f = 0; f <= nums.length; f++) bucket.add(new ArrayList<>()); for (Map.Entry<Integer, Integer> e : cnt.entrySet()) bucket.get(e.getValue()).add(e.getKey()); // bucket[f]: seen f times int[] out = new int[k]; int m = 0; for (int f = nums.length; f >= 1; f--) for (int x : bucket.get(f)) { out[m++] = x; if (m == k) return out; } return out; }
def topKFrequent(nums, k): cnt = {} for x in nums: cnt[x] = cnt.get(x, 0) + 1 bucket = [[] for _ in range(len(nums) + 1)] # bucket[f]: seen f times for x, f in cnt.items(): bucket[f].append(x) out = [] for f in range(len(nums), 0, -1): for x in bucket[f]: out.append(x) if len(out) == k: return out return out
Sorting the map by count. It works in O(n log n). The follow-up asks for better than that, and the counts are small integers, so they can index buckets.
nums = [5, 5, 5, 7, 7, 9], k = 1. Which bucket is read first that is not empty, and what is returned?
5 is seen 3 times, the most. Buckets 6 to 4 are empty, so bucket 3 comes first.
Why does bucket have n + 1 cells?
If one value fills the array, its count is n, so index n must exist.
P[i] is the sum of the first i values, with P[0] = 0. Then the sum of l..r is P[r + 1] − P[l].
nums = [1, 2, 3, 4]. What is P, and what is sumRange(1, 3)?
P[4] − P[1] = 10 − 1 = 9, which is 2 + 3 + 4.
GIVEN · ASKEDAn integer array, then many queries sumRange(left, right). Return each sum, both ends included.
Many range-sum queries on an array that never changes.
Build P with P[0] = 0 and P[i + 1] = P[i] + nums[i]. The sum of nums[l..r] is P[r + 1] − P[l].
class NumArray { vector<int> P; // P[i]: sum of the first i public: NumArray(vector<int>& nums) : P(nums.size() + 1, 0) { for (int i = 0; i < (int)nums.size(); i++) P[i + 1] = P[i] + nums[i]; } int sumRange(int left, int right) { return P[right + 1] - P[left]; } };
class NumArray { private final int[] P; // P[i]: sum of the first i public NumArray(int[] nums) { P = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) P[i + 1] = P[i] + nums[i]; } public int sumRange(int left, int right) { return P[right + 1] - P[left]; } }
class NumArray: def __init__(self, nums): self.P = [0] # P[i]: sum of the first i for x in nums: self.P.append(self.P[-1] + x) def sumRange(self, left, right): return self.P[right + 1] - self.P[left]
P of length n. Without the leading 0, a range that starts at index 0 needs its own case, and P[r] − P[l − 1] reads P[−1].
GIVEN · ASKEDAn integer array. Return the leftmost index whose left sum equals its right sum, or −1.
“The sum to the left equals the sum to the right.” Two prefix sums, but one is the total minus the other.
Keep the sum to the left of i. The sum to the right is total − left − nums[i]. Return the first i where they match.
int pivotIndex(vector<int>& nums) { int total = 0, left = 0; for (int x : nums) total += x; for (int i = 0; i < (int)nums.size(); i++) { if (left == total - left - nums[i]) return i; // right side, without nums[i] left += nums[i]; } return -1; }
public int pivotIndex(int[] nums) { int total = 0, left = 0; for (int x : nums) total += x; for (int i = 0; i < nums.length; i++) { if (left == total - left - nums[i]) return i; // right side, without nums[i] left += nums[i]; } return -1; }
def pivotIndex(nums): total, left = sum(nums), 0 for i, x in enumerate(nums): if left == total - left - x: return i # the right side, without x itself left += x return -1
Updating left before the test. Then left includes nums[i] itself, and the pivot is found one place late, or not at all.
pivotIndex([2, 1, −1])?
At index 0 the left sum is 0, and the right sum is 1 + (−1) = 0. An empty side is 0.
A solution does left += nums[i] before the test. What does it return on [1, 7, 3, 6, 5, 6], whose pivot is 3?
left now includes nums[i], so the sides never match: at index 3 it compares 17 with 5.
Pass 1 writes the product to the left of each index. Pass 2 walks back and multiplies in the product to the right.
productExceptSelf([1, 2, 0, 4])?
Every product but index 2's includes the 0. Index 2 gets 1 · 2 · 4 = 8.
On [3, 1, 2, 5], what does ans hold after the first pass?
The product to the left of each index: nothing, 3, 3 · 1, then 3 · 1 · 2.
GIVEN · ASKEDAn integer array. Return ans where ans[i] is the product of every other element, in O(n) and without division.
“The product of all the others, without division, in O(n).”
ans[i] is (product to the left) × (product to the right). Write the left products in one pass, then multiply in the right products walking back.
vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> ans(n, 1); int pre = 1, suf = 1; for (int i = 0; i < n; i++) { ans[i] = pre; pre *= nums[i]; } // left for (int i = n - 1; i >= 0; i--) { ans[i] *= suf; suf *= nums[i]; } // right return ans; }
public int[] productExceptSelf(int[] nums) { int n = nums.length, pre = 1, suf = 1; int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[i] = pre; pre *= nums[i]; } // left for (int i = n - 1; i >= 0; i--) { ans[i] *= suf; suf *= nums[i]; } // right return ans; }
def productExceptSelf(nums): n = len(nums) ans, pre, suf = [1] * n, 1, 1 for i in range(n): ans[i] = pre # the product to the left pre *= nums[i] for i in range(n - 1, -1, -1): ans[i] *= suf # times the product to the right suf *= nums[i] return ans
Total product divided by nums[i]. One zero makes the total 0 and the division undefined, and the problem forbids division anyway.
A subarray sums to k when two prefixes differ by k. Look up p − k; record p only the first time, so starts stay far left.
arr = [1, −1, 5, −2, 3], k = 3. What is the longest length?
The prefixes are 1, 0, 5, 3, 6. At index 3, p − k = 0, first seen at −1: length 4.
Why can a sliding window not solve this when values may be negative?
A window shrinks when the sum is too big, which only works if growing never lowers it.
GIVEN · ASKEDAn integer array, values may be negative, and k. Return the length of the longest subarray with sum k, or 0.
The longest subarray with sum exactly k, and values may be negative. A sliding window cannot work.
A subarray (j, i] sums to k when p(i) − p(j) = k. Map each prefix sum to the earliest index it appears at; at each i, look up p − k.
int longestSubarray(vector<int>& arr, int k) { unordered_map<long long, int> first; // prefix sum -> earliest index first[0] = -1; long long p = 0; int best = 0; for (int i = 0; i < (int)arr.size(); i++) { p += arr[i]; auto it = first.find(p - k); if (it != first.end()) best = max(best, i - it->second); if (!first.count(p)) first[p] = i; // keep the earliest } return best; }
public int longestSubarray(int[] arr, int k) { Map<Long, Integer> first = new HashMap<>(); // prefix sum -> earliest index first.put(0L, -1); long p = 0; int best = 0; for (int i = 0; i < arr.length; i++) { p += arr[i]; Integer j = first.get(p - k); if (j != null) best = Math.max(best, i - j); first.putIfAbsent(p, i); // keep the earliest } return best; }
def longestSubarray(arr, k): first = {0: -1} # prefix sum -> earliest index p = best = 0 for i, x in enumerate(arr): p += x if p - k in first: best = max(best, i - first[p - k]) if p not in first: first[p] = i # keep the earliest return best
Overwriting the index. first[p] = i every time keeps the latest start, which gives the shortest subarray, not the longest.
GIVEN · ASKEDA binary array. Return the length of the longest subarray with as many 0s as 1s.
“Equal numbers of 0s and 1s.” Count a 0 as −1 and it becomes a subarray with sum 0.
Keep a balance: +1 for a 1, −1 for a 0. Two equal balances enclose a balanced subarray. Keep the earliest index of each balance.
int findMaxLength(vector<int>& nums) { unordered_map<int, int> first; // balance -> earliest index first[0] = -1; int bal = 0, best = 0; for (int i = 0; i < (int)nums.size(); i++) { bal += nums[i] == 1 ? 1 : -1; // a 0 counts as -1 auto it = first.find(bal); if (it != first.end()) best = max(best, i - it->second); else first[bal] = i; } return best; }
public int findMaxLength(int[] nums) { Map<Integer, Integer> first = new HashMap<>(); // balance -> earliest index first.put(0, -1); int bal = 0, best = 0; for (int i = 0; i < nums.length; i++) { bal += nums[i] == 1 ? 1 : -1; // a 0 counts as -1 Integer j = first.get(bal); if (j != null) best = Math.max(best, i - j); else first.put(bal, i); } return best; }
def findMaxLength(nums): first = {0: -1} # balance -> earliest index bal = best = 0 for i, x in enumerate(nums): bal += 1 if x == 1 else -1 # a 0 counts as -1 if bal in first: best = max(best, i - first[bal]) else: first[bal] = i return best
Forgetting first[0] = −1. A balanced prefix such as [0, 1] then has no earlier balance to match, and the answer comes out short.
findMaxLength([0, 1, 1, 0, 1, 1, 1, 0])?
The balance is 0 again at index 3, so indices 0 to 3 hold two of each. No balance repeats further apart.
A subarray XORs to k when the prefix before it XORs to x ^ k. Add how often that prefix was seen, then record x.
Two prefixes with equal remainders mod k enclose a sum divisible by k. Count remainders, kept in 0..k − 1.
arr = [5, 6, 7, 8, 9], k = 5. How many subarrays XOR to 5?
[5] and the whole array: 5 ^ 6 ^ 7 ^ 8 ^ 9 = 5.
Subarray Sum Equals K, in Arrays I, counts subarrays with sum k. What does it look up at each step?
The same shape as XOR K with − for ^: an earlier prefix of p − k leaves exactly k.
GIVEN · ASKEDAn integer array and k. Return how many subarrays have XOR equal to k.
“How many subarrays XOR to k?” The same shape as counting subarrays with a given sum, with ^ in place of −.
Let x be the prefix XOR. A subarray XORs to k when the prefix before it XORs to x ^ k. Count how often each prefix XOR has appeared.
long subarrayXor(vector<int>& arr, int k) { unordered_map<int, long> cnt; // prefix XOR -> how many times cnt[0] = 1; int x = 0; long total = 0; for (int a : arr) { x ^= a; auto it = cnt.find(x ^ k); // the XOR before the start if (it != cnt.end()) total += it->second; cnt[x]++; } return total; }
public long subarrayXor(int[] arr, int k) { Map<Integer, Long> cnt = new HashMap<>(); // prefix XOR -> how many times cnt.put(0, 1L); int x = 0; long total = 0; for (int a : arr) { x ^= a; total += cnt.getOrDefault(x ^ k, 0L); // the XOR before the start cnt.merge(x, 1L, Long::sum); } return total; }
def subarrayXor(arr, k): cnt = {0: 1} # prefix XOR -> how many times x = total = 0 for a in arr: x ^= a total += cnt.get(x ^ k, 0) # the XOR before the start cnt[x] = cnt.get(x, 0) + 1 return total
Recording x before the lookup. When k = 0, x ^ k is x itself, and the prefix just added would count an empty subarray.
GIVEN · ASKEDAn integer array, values may be negative, and k. Return how many subarrays have a sum divisible by k.
“Sum divisible by k.” Two prefixes with the same remainder enclose a multiple of k.
Count prefixes by remainder mod k. Each earlier prefix with the same remainder starts one valid subarray ending here. Keep remainders in 0..k − 1.
int subarraysDivByK(vector<int>& nums, int k) { vector<int> cnt(k, 0); // remainder -> how many prefixes cnt[0] = 1; int p = 0, total = 0; for (int x : nums) { p = ((p + x) % k + k) % k; // C++ % can be negative total += cnt[p]; cnt[p]++; } return total; }
public int subarraysDivByK(int[] nums, int k) { int[] cnt = new int[k]; // remainder -> how many prefixes cnt[0] = 1; int p = 0, total = 0; for (int x : nums) { p = ((p + x) % k + k) % k; // Java % can be negative total += cnt[p]; cnt[p]++; } return total; }
def subarraysDivByK(nums, k): cnt = [0] * k # remainder -> how many prefixes cnt[0] = 1 p = total = 0 for x in nums: p = (p + x) % k # Python's % is never negative here total += cnt[p] cnt[p] += 1 return total
A negative remainder. In C++ and Java, -1 % 5 is −1, so −1 and 4 land in different counters, or off the array. Add k and take % again.
subarraysDivByK([−1, 2, 9], 2)?
The remainders are 1, 1, 0, after the empty prefix's 0. Two pairs match: [2] and the whole array, sum 10.
A range update writes +s where it starts and −s just after it ends. One running sum rebuilds every value.
n = 4 and bookings [[1, 3, 5], [2, 4, 2]]. What is d before the sweep?
+5 at d[0] and −5 at d[3], just after flight 3; +2 at d[1] and −2 at d[4].
The running sums of that d are the answer. What is it?
5, then 5 + 2, then 7 + 0, then 7 − 5. The last cell, d[4], is never read.
GIVEN · ASKEDn flights and bookings (first, last, seats). Return the total seats booked on each flight.
Each booking adds seats to a whole range of flights. Many range updates, then read every value once.
Mark +seats where a range starts and −seats just after it ends. A running sum turns the marks back into the values.
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { vector<int> d(n + 1, 0); for (auto& b : bookings) { d[b[0] - 1] += b[2]; // seats start at flight first d[b[1]] -= b[2]; // and stop after flight last } vector<int> ans(n); int run = 0; for (int i = 0; i < n; i++) { run += d[i]; ans[i] = run; } return ans; }
public int[] corpFlightBookings(int[][] bookings, int n) { int[] d = new int[n + 1]; for (int[] b : bookings) { d[b[0] - 1] += b[2]; // seats start at flight first d[b[1]] -= b[2]; // and stop after flight last } int[] ans = new int[n]; for (int i = 0, run = 0; i < n; i++) { run += d[i]; ans[i] = run; } return ans; }
def corpFlightBookings(bookings, n): d = [0] * (n + 1) for first, last, s in bookings: d[first - 1] += s # seats start at flight first d[last] -= s # and stop after flight last ans, run = [], 0 for i in range(n): run += d[i] ans.append(run) return ans
Ending the range one place early. Flights are numbered from 1, so d[last] is the cell just after flight last. d[last − 1] stops a flight too soon.
P[r][c] is the block above and left. Build it with one cell, two neighbours and the corner taken off; query with four reads.
m = [[1, 2], [3, 4]]. What is P[2][2]?
P[2][2] is the whole 2 × 2 block: 1 + 2 + 3 + 4.
sumRegion(0, 0, r2, c2) starts at the top-left corner. Which term of the formula is not zero?
Row 0 and column 0 of P are zero, so the query is that one cell.
GIVEN · ASKEDA matrix, then many queries sumRegion(row1, col1, row2, col2). Return each rectangle's sum.
Many rectangle-sum queries on a matrix that never changes.
P[r][c] is the sum of the block above row r and left of column c. A rectangle is a big block, minus two strips, plus their overlap.
class NumMatrix { vector<vector<int>> P; // P[r][c]: block above r, left of c public: NumMatrix(vector<vector<int>>& m) { int R = m.size(), C = m[0].size(); P.assign(R + 1, vector<int>(C + 1, 0)); for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) P[r + 1][c + 1] = m[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]; } int sumRegion(int r1, int c1, int r2, int c2) { return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]; } };
class NumMatrix { private final int[][] P; // P[r][c]: block above r, left of c public NumMatrix(int[][] m) { int R = m.length, C = m[0].length; P = new int[R + 1][C + 1]; for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) P[r + 1][c + 1] = m[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]; } public int sumRegion(int r1, int c1, int r2, int c2) { return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]; } }
class NumMatrix: def __init__(self, matrix): R, C = len(matrix), len(matrix[0]) P = [[0] * (C + 1) for _ in range(R + 1)] # P[r][c]: block above r, left of c for r in range(R): for c in range(C): P[r + 1][c + 1] = matrix[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c] self.P = P def sumRegion(self, row1, col1, row2, col2): P = self.P return P[row2 + 1][col2 + 1] - P[row1][col2 + 1] - P[row2 + 1][col1] + P[row1][col1]
Forgetting to add the overlap back. Both strips contain the block above and left of the query, so subtracting both removes it twice.
Only 1..n can be the answer. Swap each such value home, then the first index without its value is the smallest missing positive.
firstMissingPositive([1, 2, 0])?
1 and 2 are home, and 0 has no home. Every index holds its value, so return n + 1 = 3.
The while tests nums[i] != i + 1 instead of nums[v − 1] != v. What happens on [1, 1]?
At index 1, v = 1 and nums[1] ≠ 2, so it swaps two 1s, and nothing changes.
GIVEN · ASKEDAn unsorted integer array. Return the smallest positive integer that is not in it, in O(n) time and O(1) extra space.
“The smallest missing positive, in O(n) time and O(1) extra space.” No room for a set, so the array becomes one.
The answer is in 1..n + 1, so only values 1 to n matter. Swap each one to index v − 1. Then the first index i that does not hold i + 1 gives the answer.
int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { int v = nums[i]; while (v >= 1 && v <= n && nums[v - 1] != v) { swap(nums[i], nums[v - 1]); // v goes home, to index v - 1 v = nums[i]; } } for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1; // the first home still wrong return n + 1; }
public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { int v = nums[i]; while (v >= 1 && v <= n && nums[v - 1] != v) { nums[i] = nums[v - 1]; // v goes home, to index v - 1 nums[v - 1] = v; v = nums[i]; } } for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1; // the first home still wrong return n + 1; }
def firstMissingPositive(nums): n = len(nums) for i in range(n): v = nums[i] while 1 <= v <= n and nums[v - 1] != v: nums[i], nums[v - 1] = nums[v - 1], v # v goes home, to index v - 1 v = nums[i] for i in range(n): if nums[i] != i + 1: return i + 1 # the first home still wrong return n + 1
Testing nums[i] ≠ i + 1 in the while. With a duplicate, such as two 1s, the loop swaps the same value back and forth forever. Test whether v's home already holds v.
Ten moves, and each has a phrase in the statement that gives it away.
a set of what has been read; a lookup searches one bucket
SEEN BEFOREO(n)a key equal across the group; a map from key to list
A KEY FOR THE GROUPO(n · key)count everything, then read; bucket[count] when the counts must be ordered
COUNT, THEN READO(n)P[0] = 0 and P[i + 1] = P[i] + nums[i]; a range is P[r + 1] − P[l]
PREFIX SUMSO(1) per querythe left part times the right part, one pass each way
FROM BOTH SIDESO(n)map each prefix to its earliest index; look up p − k
THE EARLIEST PREFIXO(n)count prefixes in a map; add the count of the partner, then record
COUNT MATCHING PREFIXESO(n)+s at l, −s just after r; one running sum at the end
DIFFERENCE ARRAYO(n + updates)P[r][c] is the block above and left; four reads per query
2D PREFIXO(1) per querysend v to index v − 1; the first index without its value
THE ARRAY AS ITS OWN TABLEO(n)Return the length of the longest subarray whose sum is 0. Which move?
Two equal prefix sums enclose a zero sum. Keep the earliest index of each one.
Count the pairs i < j whose song lengths add up to a multiple of 60. Which move?
For each length, add how many earlier lengths have remainder (60 − r) % 60, then record r. A map of remainders, counted as you go.
Which of these starts its map with first[0] = −1 rather than cnt[0] = 1?
It asks for a length, so its map holds the earliest index. The counting rows hold how many.
A difference array takes b range updates on n cells, then one sweep. What is the total cost?
Each update writes two cells, and the sweep reads n.
None of these fail the samples. Each one fails a hidden test.
For a longest subarray, record a prefix only the first time. Writing it every time keeps the latest start, which is the shortest.
first[0] = −1, cnt[0] = 1. Without it, every subarray that starts at index 0 is missed.
In C++ and Java, −1 % 5 is −1. Add k and take % again, or −1 and 4 never meet.
Growing a window can lower its sum, so shrinking on “too big” is wrong. Use prefix sums and a map.
Look up the partner, then record the current prefix. The other order counts an empty subarray when k = 0.
Summing the letter codes puts ad and bc together. The key must fix every letter's count.
Ten moves on one page. The right column is the cue for each.
Buckets answered “seen?”; sorted letters made a key; counts were read after they were final; prefixes turned ranges into subtractions, from one side, both sides, and in two dimensions; a map of prefixes found the earliest start or counted partners; edges stood in for whole ranges; and the array held its own values.
Module 4. Fifteen problems: thirteen on LeetCode, two on GeeksforGeeks. Next: two pointers.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.