Two indices walk an array, and each step throws away a value that can never be in the answer. Sorted order, a shorter wall or a stalled stream says which one. n² pairs become n steps. 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.
Too small: a[l] fails even with the largest value left, so l moves right. Too big: a[r] fails even with the smallest, so r moves left.
numbers = [2, 3, 5, 9, 12], target = 17. What does twoSum return?
2 + 12 and 3 + 12 fall short, so l moves twice. Then 5 + 12 = 17, at positions 3 and 5.
s < target, so l moves right. Why can that never skip the answer?
Every r still in play is at most a[r], so every sum with a[l] is at most s. None of them reaches the target.
Two values that add up to a target, in an array that is already sorted, using O(1) extra space. Positions count from 1.
Start at both ends. A sum that is too small can only grow by moving l right; a sum that is too big can only shrink by moving r left. Each move throws away a value that can never be in the answer.
vector<int> twoSum(vector<int>& numbers, int target) { int l = 0, r = numbers.size() - 1; while (l < r) { int s = numbers[l] + numbers[r]; if (s == target) return {l + 1, r + 1}; if (s < target) l++; // numbers[l] is too small for every r left else r--; // numbers[r] is too big for every l left } return {}; // not reached: one answer is promised }
public int[] twoSum(int[] numbers, int target) { int l = 0, r = numbers.length - 1; while (l < r) { int s = numbers[l] + numbers[r]; if (s == target) return new int[]{l + 1, r + 1}; if (s < target) l++; // numbers[l] is too small for every r left else r--; // numbers[r] is too big for every l left } return new int[0]; // not reached: one answer is promised }
def twoSum(numbers, target): l, r = 0, len(numbers) - 1 while l < r: s = numbers[l] + numbers[r] if s == target: return [l + 1, r + 1] if s < target: l += 1 # numbers[l] is too small for every r left else: r -= 1 # numbers[r] is too big for every l left return []
Reaching for a hash map. It passes, but it uses O(n) space, which the problem rules out, and it ignores the one thing the input gives you for free: the order.
Two values at different positions that sum to x, and the positions are printed. The array is not sorted.
Sort, and the scan of row 1 finds the pair. Sorting loses the positions, so sort (value, position) pairs and print the positions they carry.
#include <bits/stdc++.h> using namespace std; int main() { int n; long long x; scanf("%d %lld", &n, &x); vector<pair<long long, int> > a(n); // (value, position) for (int i = 0; i < n; i++) { scanf("%lld", &a[i].first); a[i].second = i + 1; } sort(a.begin(), a.end()); int l = 0, r = n - 1; while (l < r) { long long s = a[l].first + a[r].first; if (s == x) { printf("%d %d\n", a[l].second, a[r].second); return 0; } if (s < x) l++; else r--; } puts("IMPOSSIBLE"); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); long x = (long) in.nval; long[] a = new long[n]; // value · 2^18 + position: one sortable key for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (long) in.nval * (1L << 18) + i + 1; } Random rnd = new Random(); // shuffle, so no input is slow for quicksort for (int i = n - 1; i > 0; i--) { int j = rnd.nextInt(i + 1); long t = a[i]; a[i] = a[j]; a[j] = t; } Arrays.sort(a); int l = 0, r = n - 1; while (l < r) { long s = (a[l] >> 18) + (a[r] >> 18); if (s == x) { System.out.println((a[l] & 262143) + " " + (a[r] & 262143)); return; } if (s < x) l++; else r--; } System.out.println("IMPOSSIBLE"); } }
import sys def main(): data = sys.stdin.buffer.read().split() n, x = int(data[0]), int(data[1]) a = sorted((int(data[2 + i]), i + 1) for i in range(n)) # (value, position) l, r = 0, n - 1 while l < r: s = a[l][0] + a[r][0] if s == x: print(a[l][1], a[r][1]) return if s < x: l += 1 else: r -= 1 print("IMPOSSIBLE") main()
Sorting the bare values. The scan then finds the right values and prints where they sit after sorting. Carry each value's original position through the sort.
Sum of Two Values with x = 6 and values 3 1 3. What does the program print?
After sorting the pairs, the two 3s carry positions 1 and 3. The pointers never share a cell, so position 1 is not used twice.
With a[k] the longest side, a passing a[l] + a[r] passes for every l' up to r − 1 as well. Count r − l at once and move r.
triangleNumber([2, 2, 3, 4])?
(2, 3, 4) works with either 2, and (2, 2, 3) works. (2, 2, 4) does not: 2 + 2 is not more than 4.
3Sum Closest runs unit 1's scan once per first value. What does the whole run cost?
n first values, and an O(n) scan for each. The sort, O(n log n), is smaller.
Three values whose sum is closest to a target. Not equal to it: closest, and the sum itself is returned.
Sort. Fix the first value, then run unit 1's scan on everything after it, keeping the sum that has come closest. A sum equal to the target cannot be beaten, so return it at once.
int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int n = nums.size(), best = nums[0] + nums[1] + nums[2]; for (int i = 0; i + 2 < n; i++) { int l = i + 1, r = n - 1; // unit 1's scan, for each first value while (l < r) { int s = nums[i] + nums[l] + nums[r]; if (abs(s - target) < abs(best - target)) best = s; if (s < target) l++; else if (s > target) r--; else return s; // distance 0 cannot be beaten } } return best; }
public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length, best = nums[0] + nums[1] + nums[2]; for (int i = 0; i + 2 < n; i++) { int l = i + 1, r = n - 1; // unit 1's scan, for each first value while (l < r) { int s = nums[i] + nums[l] + nums[r]; if (Math.abs(s - target) < Math.abs(best - target)) best = s; if (s < target) l++; else if (s > target) r--; else return s; // distance 0 cannot be beaten } } return best; }
def threeSumClosest(nums, target): nums.sort() n, best = len(nums), nums[0] + nums[1] + nums[2] for i in range(n - 2): l, r = i + 1, n - 1 # unit 1's scan, for each first value while l < r: s = nums[i] + nums[l] + nums[r] if abs(s - target) < abs(best - target): best = s if s < target: l += 1 elif s > target: r -= 1 else: return s # distance 0 cannot be beaten return best
Starting best at a huge number. best − target then overflows in C++ and Java. Start from a real sum, the first three values.
threeSumClosest([−1, 2, 1, −4], 1)?
−1 + 2 + 1 = 2, at distance 1. No triple sums to exactly 1.
Count the triples that can be the sides of a triangle. Counting, so a scan that finds one pair at a time is too slow.
Sort, and take a[k] as the longest side. A pair works when a[l] + a[r] > a[k]. When it does, every l' from l to r − 1 works with r too, because those values are at least a[l]: add r − l in one step.
int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int count = 0; for (int k = nums.size() - 1; k >= 2; k--) { // nums[k]: the longest side int l = 0, r = k - 1; while (l < r) { if (nums[l] + nums[r] > nums[k]) { count += r - l; // nums[l..r-1] each work with nums[r] r--; } else l++; // nums[l] is too short for every r left } } return count; }
public int triangleNumber(int[] nums) { Arrays.sort(nums); int count = 0; for (int k = nums.length - 1; k >= 2; k--) { // nums[k]: the longest side int l = 0, r = k - 1; while (l < r) { if (nums[l] + nums[r] > nums[k]) { count += r - l; // nums[l..r-1] each work with nums[r] r--; } else l++; // nums[l] is too short for every r left } } return count; }
def triangleNumber(nums): nums.sort() count = 0 for k in range(len(nums) - 1, 1, -1): # nums[k]: the longest side l, r = 0, k - 1 while l < r: if nums[l] + nums[r] > nums[k]: count += r - l # nums[l..r-1] each work with nums[r] r -= 1 else: l += 1 # nums[l] is too short for every r left return count
Fixing the shortest side instead of the longest. With a[i] fixed first, a passing test says nothing about the pairs beside it, and the scan cannot count them at once. The longest side has to be the fixed one.
Compare the sizes at the two ends and write the larger square at the back of the output. The smallest can be anywhere; the largest cannot.
sortedSquares([−7, −3, 2, 3, 11])?
11 has the largest size, then −7, then −3 and 3, then 2. Written from the back, the output comes out sorted.
Why does out fill from the back, not the front?
The smallest square sits where the sign changes, which can be the middle. The largest is always at one of the two ends.
Square every value of a sorted array and return the squares sorted. Negatives are allowed, so squaring breaks the order.
The largest square belongs to whichever end has the larger absolute value. Compare the two ends, write the larger square at the back of the output, and move that end in.
vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(), l = 0, r = n - 1; vector<int> out(n); for (int w = n - 1; w >= 0; w--) { // the largest square goes last if (abs(nums[l]) > abs(nums[r])) { out[w] = nums[l] * nums[l]; l++; } else { out[w] = nums[r] * nums[r]; r--; } } return out; }
public int[] sortedSquares(int[] nums) { int n = nums.length, l = 0, r = n - 1; int[] out = new int[n]; for (int w = n - 1; w >= 0; w--) { // the largest square goes last if (Math.abs(nums[l]) > Math.abs(nums[r])) { out[w] = nums[l] * nums[l]; l++; } else { out[w] = nums[r] * nums[r]; r--; } } return out; }
def sortedSquares(nums): n = len(nums) l, r, out = 0, n - 1, [0] * n for w in range(n - 1, -1, -1): # the largest square goes last if abs(nums[l]) > abs(nums[r]): out[w] = nums[l] * nums[l] l += 1 else: out[w] = nums[r] * nums[r] r -= 1 return out
Filling from the front. The smallest square can sit anywhere in the middle, where the sign changes. Only the largest is guaranteed to be at an end.
Every other container with the shorter wall is narrower and no taller. Measure, keep the best, and move the shorter wall in.
maxArea([4, 3, 2, 1, 4])?
The two 4s at the ends hold 4 × 4 = 16 between them, and no narrower pair beats it.
A solution moves the taller wall each time. What does it return on [1, 2, 4, 3]?
It drops the 3, then the 4, then the 2, keeping the 1 every time. The pair 2 and 3, which holds 4, is never measured.
Pick two walls; the water between them is min(h[l], h[r]) · (r − l). Maximise it over every pair.
Start with the widest pair. The shorter wall caps every container it is still part of, and each of those is narrower, so none can beat the one just measured. Drop the shorter wall and measure again.
int maxArea(vector<int>& height) { int l = 0, r = height.size() - 1, best = 0; while (l < r) { int area = min(height[l], height[r]) * (r - l); best = max(best, area); if (height[l] < height[r]) l++; // the shorter wall cannot do better else r--; } return best; }
public int maxArea(int[] height) { int l = 0, r = height.length - 1, best = 0; while (l < r) { int area = Math.min(height[l], height[r]) * (r - l); best = Math.max(best, area); if (height[l] < height[r]) l++; // the shorter wall cannot do better else r--; } return best; }
def maxArea(height): l, r, best = 0, len(height) - 1, 0 while l < r: best = max(best, min(height[l], height[r]) * (r - l)) if height[l] < height[r]: l += 1 # the shorter wall cannot do better else: r -= 1 return best
Moving the taller wall. The width shrinks and the height is still capped by the shorter wall, so it can only lose, and it may step past the answer.
Alice eats bars from the left, Bob from the right, at the same speed. Who gets each bar? On a tie for the last bar, Alice.
Keep how long each has been eating. Whoever has eaten for less time finishes first and takes the next bar from their end; on a tie it is Alice. Stop when the two ends cross.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<int> t(n); for (int i = 0; i < n; i++) scanf("%d", &t[i]); int l = 0, r = n - 1; long long ta = 0, tb = 0; // how long each has been eating while (l <= r) { if (ta <= tb) ta += t[l++]; // Alice is free first; a tie is hers else tb += t[r--]; } printf("%d %d\n", l, n - l); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; int[] t = new int[n]; for (int i = 0; i < n; i++) { in.nextToken(); t[i] = (int) in.nval; } int l = 0, r = n - 1; long ta = 0, tb = 0; // how long each has been eating while (l <= r) { if (ta <= tb) ta += t[l++]; // Alice is free first; a tie is hers else tb += t[r--]; } System.out.println(l + " " + (n - l)); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) t = list(map(int, data[1:1 + n])) l, r, ta, tb = 0, n - 1, 0, 0 # ta, tb: how long each has been eating while l <= r: if ta <= tb: # Alice is free first; a tie is hers ta += t[l] l += 1 else: tb += t[r] r -= 1 print(l, n - l) main()
ta < tb instead of ta ≤ tb. On a tie Bob would take the bar, and the statement gives it to Alice. On 1 1 1 that prints 1 2 instead of 2 1.
Alice, Bob and Chocolate with bars 1 1 1. What is printed?
Alice and Bob each eat one bar. Both finish at time 1 and reach the middle bar together, so it goes to Alice.
The heaviest person left needs a boat. The lightest rides along if they fit; if the lightest cannot, nobody can.
numRescueBoats([3, 2, 2, 1], 3)?
Sorted: 1 2 2 3. The 3 goes alone, 1 and 2 share, and the other 2 goes alone.
Why does the heaviest person ride with the lightest, and not with the heaviest partner that fits?
Anyone who could share with the heaviest is at least as heavy as the lightest. Taking the lightest leaves the heavier people, who are harder to pair, no worse off.
Each boat holds at most two people and at most limit in weight. The fewest boats for everyone.
Sort. The heaviest person left needs a boat now. If even the lightest cannot share it, nobody can, so they go alone; if the lightest can, they ride along, and no other choice would do better.
int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(), people.end()); int l = 0, r = people.size() - 1, boats = 0; while (l <= r) { if (people[l] + people[r] <= limit) l++; // the lightest rides along r--; // the heaviest always goes boats++; } return boats; }
public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int l = 0, r = people.length - 1, boats = 0; while (l <= r) { if (people[l] + people[r] <= limit) l++; // the lightest rides along r--; // the heaviest always goes boats++; } return boats; }
def numRescueBoats(people, limit): people.sort() l, r, boats = 0, len(people) - 1, 0 while l <= r: if people[l] + people[r] <= limit: l += 1 # the lightest rides along r -= 1 # the heaviest always goes boats += 1 return boats
while (l < r). The last person, alone in the middle, never gets a boat. With l ≤ r they do, and the test adding them to themselves only moves l.
Evens collect on the left and odds on the right. A misplaced pair, odd on the left and even on the right, is fixed by one swap.
sortArrayByParity([1, 2, 3, 4]), with the two-pointer code?
1 and 4 are both misplaced and swap. Then 2 is already even, l reaches r, and the scan stops.
At most how many swaps does the scan make on n values?
Each swap moves both pointers in by one, and they start n − 1 apart.
Move every even value before every odd value, in place. Any order inside each group is accepted.
Grow an even zone from the left and an odd zone from the right. A value already on its side just extends its zone. When the left holds an odd and the right an even, one swap fixes both.
vector<int> sortArrayByParity(vector<int>& nums) { int l = 0, r = nums.size() - 1; while (l < r) { if (nums[l] % 2 == 0) l++; // already on the even side else if (nums[r] % 2 == 1) r--; // already on the odd side else swap(nums[l++], nums[r--]); // both misplaced: trade them } return nums; }
public int[] sortArrayByParity(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { if (nums[l] % 2 == 0) l++; // already on the even side else if (nums[r] % 2 == 1) r--; // already on the odd side else { int t = nums[l]; nums[l++] = nums[r]; nums[r--] = t; } // trade them } return nums; }
def sortArrayByParity(nums): l, r = 0, len(nums) - 1 while l < r: if nums[l] % 2 == 0: l += 1 # already on the even side elif nums[r] % 2 == 1: r -= 1 # already on the odd side else: # both misplaced: trade them nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 return nums
Testing x % 2 == 1 for odd in a language with negative remainders. In C++ and Java, −3 % 2 is −1. The values here are never negative, but on a variant that allows them, test x % 2 != 0.
Two sorted streams. The smaller head can never meet its equal, so it leaves; equal heads are a match and both move.
intersect([1, 2, 2, 1], [2, 2])?
Both arrays hold two 2s, so 2 is output twice. The 1s have no partner.
Every value that appears in both arrays, as many times as it appears in both. Any order.
Sort both and read them as two rising streams. The smaller head can never meet its equal in the other stream, so it leaves. Equal heads are a match: take one copy and advance both.
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); int i = 0, j = 0; vector<int> out; while (i < nums1.size() && j < nums2.size()) { if (nums1[i] < nums2[j]) i++; // no partner left in nums2 else if (nums1[i] > nums2[j]) j++; // no partner left in nums1 else { out.push_back(nums1[i]); i++; j++; } } return out; }
public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int i = 0, j = 0, k = 0; int[] out = new int[Math.min(nums1.length, nums2.length)]; while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) i++; // no partner left in nums2 else if (nums1[i] > nums2[j]) j++; // no partner left in nums1 else { out[k++] = nums1[i]; i++; j++; } } return Arrays.copyOf(out, k); }
def intersect(nums1, nums2): nums1.sort() nums2.sort() i = j = 0 out = [] while i < len(nums1) and j < len(nums2): if nums1[i] < nums2[j]: i += 1 # no partner left in nums2 elif nums1[i] > nums2[j]: j += 1 # no partner left in nums1 else: out.append(nums1[i]) i += 1 j += 1 return out
A set instead of a count. A set keeps one copy of each value, but a value appearing twice in both arrays must be output twice. The merge, or a counter, keeps the copies.
Give apartments to applicants; applicant i accepts any size within k of a[i]. The most applicants housed.
Sort both. Take the smallest applicant and the smallest apartment. An apartment too small for this applicant is too small for every later one; an applicant for whom every apartment left is too big gets none. Otherwise the match is safe: take it.
#include <bits/stdc++.h> using namespace std; int main() { int n, m; long long k; scanf("%d %d %lld", &n, &m, &k); vector<long long> a(n), b(m); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); for (int j = 0; j < m; j++) scanf("%lld", &b[j]); sort(a.begin(), a.end()); sort(b.begin(), b.end()); int i = 0, j = 0, got = 0; while (i < n && j < m) { if (b[j] < a[i] - k) j++; // too small for everyone left else if (b[j] > a[i] + k) i++; // every apartment left is too big else { got++; i++; j++; } } printf("%d\n", got); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int m = (int) in.nval; in.nextToken(); long k = (long) in.nval; long[] a = new long[n], b = new long[m]; for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (long) in.nval; } for (int j = 0; j < m; j++) { in.nextToken(); b[j] = (long) in.nval; } shuffle(a); shuffle(b); // so no input is slow for quicksort Arrays.sort(a); Arrays.sort(b); int i = 0, j = 0, got = 0; while (i < n && j < m) { if (b[j] < a[i] - k) j++; // too small for everyone left else if (b[j] > a[i] + k) i++; // every apartment left is too big else { got++; i++; j++; } } System.out.println(got); } static void shuffle(long[] x) { Random rnd = new Random(); for (int i = x.length - 1; i > 0; i--) { int j = rnd.nextInt(i + 1); long t = x[i]; x[i] = x[j]; x[j] = t; } } }
import sys def main(): data = sys.stdin.buffer.read().split() n, m, k = int(data[0]), int(data[1]), int(data[2]) a = sorted(map(int, data[3:3 + n])) b = sorted(map(int, data[3 + n:3 + n + m])) i = j = got = 0 while i < n and j < m: if b[j] < a[i] - k: j += 1 # too small for everyone left elif b[j] > a[i] + k: i += 1 # every apartment left is too big else: got += 1 i += 1 j += 1 print(got) main()
int for a[i] + k. Both can be 10⁹, and the sum overflows a 32-bit int. Use 64-bit values for the comparison.
Apartments with k = 0, desired sizes 5 5 and apartments 5 6. What is printed?
One applicant gets the 5. The 6 is outside 5 ± 0, so the other gets nothing.
An apartment with b[j] < a[i] − k is skipped for good. Why is that safe?
The applicants are sorted, so a[i] − k only rises. An apartment below it now stays below it.
t always moves. s moves only when its wanted letter turns up, so the order of s is kept and the gaps in t are skipped.
isSubsequence("axc", "ahbgdc"). What is i when the scan ends?
a is found at once. x never turns up, so s stalls at i = 1 and the answer is false.
Can s be read out of t left to right, skipping letters of t? The order matters; the gaps do not.
Walk t once. i is the next letter of s still wanted. A letter of t that matches it is used, and i moves on; any other letter is skipped. s stalls while t keeps moving.
bool isSubsequence(string s, string t) { int i = 0; // the next letter of s to find for (int j = 0; j < t.size() && i < s.size(); j++) if (s[i] == t[j]) i++; // found it; look for the next return i == s.size(); }
public boolean isSubsequence(String s, String t) { int i = 0; // the next letter of s to find for (int j = 0; j < t.length() && i < s.length(); j++) if (s.charAt(i) == t.charAt(j)) i++; // found it; look for the next return i == s.length(); }
def isSubsequence(s, t): i = 0 # the next letter of s to find for c in t: if i < len(s) and s[i] == c: i += 1 # found it; look for the next return i == len(s)
Reading s[i] after i reaches the end. Once every letter is found, s[i] is past the end of s. Test i < |s| first.
Two strings typed into an editor where # is backspace. Are the results equal? Follow-up: O(1) extra space.
A # erases the letter before it, so read both strings from the back. Count the #s seen; a letter met while the count is positive is erased. Compare the surviving letters one pair at a time.
int survivor(const string& x, int k) { // the next letter that survives, or -1 int skip = 0; for (; k >= 0; k--) { if (x[k] == '#') skip++; else if (skip > 0) skip--; // erased by a later # else break; } return k; } bool backspaceCompare(string s, string t) { int i = (int)s.size() - 1, j = (int)t.size() - 1; while (true) { i = survivor(s, i); j = survivor(t, j); if (i < 0 || j < 0) return i < 0 && j < 0; if (s[i] != t[j]) return false; i--; j--; } }
int survivor(String x, int k) { // the next letter that survives, or -1 int skip = 0; for (; k >= 0; k--) { if (x.charAt(k) == '#') skip++; else if (skip > 0) skip--; // erased by a later # else break; } return k; } public boolean backspaceCompare(String s, String t) { int i = s.length() - 1, j = t.length() - 1; while (true) { i = survivor(s, i); j = survivor(t, j); if (i < 0 || j < 0) return i < 0 && j < 0; if (s.charAt(i) != t.charAt(j)) return false; i--; j--; } }
def backspaceCompare(s, t): def survivor(x, k): # the next letter that survives, or -1 skip = 0 while k >= 0: if x[k] == '#': skip += 1 elif skip: skip -= 1 # erased by a later # else: break k -= 1 return k i, j = len(s) - 1, len(t) - 1 while True: i, j = survivor(s, i), survivor(t, j) if i < 0 or j < 0: return i < 0 and j < 0 if s[i] != t[j]: return False i -= 1 j -= 1
Reading from the front. A letter's fate depends on #s that come after it, so the front cannot decide it without a stack. From the back, the #s arrive first.
What does "a##c" become once its backspaces are applied?
The first # erases a, and the second has nothing to erase. Then c is typed.
Why does Backspace String Compare read from the back?
From the back, each # is counted before the letter it erases, so one counter decides every letter.
i reads every value; k writes the kept ones. A value is kept unless the answer already ends in two copies of it: compare with a[k − 2].
removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3])?
Two 0s, two 1s, one 2 and two 3s are kept: 0 0 1 1 2 3 3.
A solution keeps a[i] when k < 2 || a[i] != a[i − 2], in place. What does it return on [1, 1, 1, 2, 2, 3]?
Writing the first 2 overwrites a[2]. The second 2 then matches a[2] and looks like a third copy, so it is dropped.
A sorted array; keep at most two copies of each value, in place, and return how many are kept.
a[0..k) is the answer so far. A value can join it unless the answer already ends in two copies of it, and because the array is sorted, that shows in one place: a[k − 2].
int removeDuplicates(vector<int>& nums) { int k = 0; // nums[0..k) is the answer so far for (int i = 0; i < nums.size(); i++) if (k < 2 || nums[i] != nums[k - 2]) // at most two copies of each nums[k++] = nums[i]; return k; }
public int removeDuplicates(int[] nums) { int k = 0; // nums[0..k) is the answer so far for (int i = 0; i < nums.length; i++) if (k < 2 || nums[i] != nums[k - 2]) // at most two copies of each nums[k++] = nums[i]; return k; }
def removeDuplicates(nums): k = 0 # nums[0..k) is the answer so far for i in range(len(nums)): if k < 2 or nums[i] != nums[k - 2]: # at most two copies of each nums[k] = nums[i] k += 1 return k
Comparing with nums[i − 2]. The write pointer may have overwritten that cell, so it no longer holds what was read. The rule is about the answer, so compare with nums[k − 2].
When h[l] < h[r], the right already holds a wall of at least h[r], so lmax is the lower wall at l. Settle it and move l. Otherwise settle r with rmax.
trap([4, 2, 0, 3, 2, 5])?
Every bar sits under the 4 on the left, the lower of the two end walls: 2 + 4 + 1 + 2 = 9.
h[l] < h[r], so the water at l is settled with lmax alone. Why is rmax not needed?
Water at l is the lower of the two walls. The right wall is at least h[r], and lmax has never beaten a right wall so far, so lmax is the lower one.
trap([2, 0, 2])?
The middle bar sits between two walls of 2, so 2 units of water stand on it.
Bars of width 1; how much rain is trapped between them? Water above a bar is the lower of the tallest walls on each side, minus the bar.
Walk in from both ends. When h[l] < h[r], the right side already has a wall at least h[r], so the lower wall at l is lmax, the tallest bar from the left. Settle l with lmax and move on. Otherwise settle r with rmax.
int trap(vector<int>& height) { int l = 0, r = height.size() - 1, lmax = 0, rmax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // the right wall is at least height[r] lmax = max(lmax, height[l]); water += lmax - height[l]; l++; } else { rmax = max(rmax, height[r]); water += rmax - height[r]; r--; } } return water; }
public int trap(int[] height) { int l = 0, r = height.length - 1, lmax = 0, rmax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // the right wall is at least height[r] lmax = Math.max(lmax, height[l]); water += lmax - height[l]; l++; } else { rmax = Math.max(rmax, height[r]); water += rmax - height[r]; r--; } } return water; }
def trap(height): l, r = 0, len(height) - 1 lmax = rmax = water = 0 while l < r: if height[l] < height[r]: # the right wall is at least height[r] lmax = max(lmax, height[l]) water += lmax - height[l] l += 1 else: rmax = max(rmax, height[r]) water += rmax - height[r] r -= 1 return water
Using lmax on the side that is taller. The water at l is bounded by the lower wall, and lmax is only known to be the lower one when h[l] < h[r]. Move the side with the smaller bar, and settle it with its own maximum.
Ten moves, and each has a phrase in the statement that gives it away.
pointers at both ends; the sum says which one moves
CONVERGEO(n)fix one value, converge on the rest; a passing test counts r − l pairs
CONVERGE IN A LOOPO(n²)the extremes sit at the ends; fill the output from the back
FILL FROM THE ENDSO(n)measure the widest, then drop the side that limits it
MOVE THE SHORTER SIDEO(n)sort; the heaviest goes now, the lightest rides along if it fits
PAIR THE ENDSO(n log n)two zones grow inward; swap a misplaced pair
SWAP FROM BOTH ENDSO(n)sort both; the smaller head leaves, equal heads match
TWO SORTED STREAMSO(n log n)the long stream always moves; the short one only on a match
ONE STREAM STALLSO(n)read with i, write with k; compare with the answer, a[k − 1] or a[k − 2]
WRITE POINTERO(n)two running maxima; settle the side whose wall is lower
TWO RUNNING MAXIMAO(n)A sorted array and a target. Count the pairs whose sum is less than the target. Which move?
When a[l] + a[r] < target, every r' from l + 1 to r works with l too: add r − l and move l. It is unit 2's counting step, mirrored.
Merge Sorted Array writes nums2 into the spare cells at the end of nums1. Which move fills nums1 without overwriting anything still unread?
Compare the largest unread value of each array and write it at the back. The back is empty, so nothing unread is overwritten.
Sort Colors puts the 0s, then the 1s, then the 2s, in one pass and in place. Which move does it grow from?
It is unit 6 with three zones: 0s grow from the left, 2s from the right, and a middle pointer swaps each value toward its zone.
Why is converging on an array O(n)?
The gap between l and r shrinks by one per step, so the scan ends within n − 1 steps.
None of these fail the samples. Each one fails a hidden test.
When the answer is positions, sort (value, position) pairs. Sorting the bare values finds the right values at the wrong places.
In the container, the taller wall is never the limit. Moving it shrinks the width without raising the cap, and can skip the answer.
l < r WHERE l ≤ r BELONGSWhen the middle value still needs handling, such as the last person waiting for a boat, the loop must run at l = r too.
A write pointer changes cells behind the read pointer. Compare with the answer, a[k − 2], not with a[i − 2].
Intersection II wants each value as often as it is in both. A set keeps one copy; the merge keeps every match.
Two values up to 10⁹ add up past a 32-bit int. CSES 1640 and 1084 need 64-bit sums and bounds.
Ten moves on one page. The right column is the cue for each.
A sum said which end to move; one passing test counted many pairs; the largest square came from an end; the shorter wall stepped in; the heaviest took a boat; a misplaced pair swapped; two sorted streams met; one stream stalled while the other read on; a write pointer kept what its rule allowed; and the lower wall settled the water. 3Sum and 4Sum (arrays 2) run unit 2's loop with one and two values fixed, Valid Palindrome (strings) converges on letters, Merge Sorted Array (arrays 1) fills from the back, and Ferris Wheel (CSES 1090) is unit 5 with a different input.
Module 5. Fifteen problems: twelve on LeetCode, two on CSES and one on Codeforces. Next: the sliding window, two pointers that move the same way.
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.