These are the notes for DSA episode 89. In an interview nobody tells you "use a sliding window". This episode teaches a four-step method that finds the pattern for you: (1) read the constraints to get the time budget, (2) spot the cue words and the shape of the input, (3) write and run the brute force first, (4) find the waste the brute force repeats, and pick the pattern that removes it. Then the method is used on three fresh problems, end to end: a canteen (longest run of days with at most k different dishes: sliding window), a delivery van (smallest capacity for d trips: binary search on the answer) and a warehouse robot (fewest button presses: BFS). Every brute force was run on a big input and hit the time limit; every optimal solution was typed and run. Every program below was run with javac 21 (25-second limit, -Xmx1536m, like the SyntaxPilot compiler), g++ 13 (-O2) and Python 3, and every output shown is real (timings vary by machine).
The problems, in real life
| Real life | In code | Pattern |
|---|---|---|
| A canteen writes down the dish served each day; the owner wants the longest run of days with at most k dishes | longest contiguous subarray with at most k distinct values |
sliding window |
A van carries parcels in a fixed order, in d trips; how big must it be? |
smallest capacity so the greedy loading needs ≤ d trips |
binary search on the answer |
A robot on a rail with two buttons, "+u" and "−d"; fewest presses from slot s to slot g |
shortest path where every move costs 1 | BFS |
Every word, from zero
- Pattern: a known technique that solves a whole family of problems (sliding window, BFS, DP, ...).
- Constraints: the limits in the statement, like
1 ≤ n ≤ 2·10⁵. They tell you how fast your solution must be. - Big O / complexity: how the number of steps (or memory) grows with the input size
n.O(n²)means "about n × n steps". - Time budget: a judge runs about 10⁸ simple steps a second, so
ndecides which complexity fits. - Brute force: the simplest correct solution: try every possibility.
- Waste: work the brute force repeats again and again; removing it is the whole job of the pattern.
- Time Limit Exceeded (TLE): the judge stopped your program because it ran too long (25 s here).
- Contiguous / subarray: elements next to each other, with no gaps.
- Sliding window: two indices
landrmarking a contiguous part;rgrows it,lshrinks it, each moves only forward. - HashSet: a set that keeps each value once, with O(1) average add and lookup.
- HashMap / count map: a map from a value to how many times it occurs (here: inside the window).
- Monotonic: only goes one way (never up, or never down). "Trips needed" is monotonic in the capacity.
- Binary search on the answer: binary search over the possible answer values, using a yes/no check, when the yes/no answers form a cliff (no, no, ..., yes, yes, ...).
- Greedy check: fill each trip until the next parcel doesn't fit; it gives the fewest trips for a capacity.
- Integer overflow: a value too big for its type wraps around;
lo + (hi - lo) / 2avoids it inmid. - Graph / node / edge: places (nodes) connected by moves (edges). Here: slots and button presses.
- BFS (breadth-first search): explore a graph ring by ring: everything 1 move away, then 2, then 3. The first time it reaches a node is the fewest moves.
- Queue / ArrayDeque: first in, first out.
addputs at the back,polltakes from the front. - Bitmask DP: dynamic programming whose state includes a set stored as bits of an integer (used when
n ≤ 20).
The four-step method
- Read the constraints. About 10⁸ simple steps a second:
| Constraint | Allowed complexity | Typical patterns |
|---|---|---|
| n ≤ 10 | O(n!) | try every order |
| n ≤ 20 | O(2ⁿ) | backtracking, bitmask DP |
| n ≤ 500 | O(n³) | three loops, interval DP, Floyd-Warshall |
| n ≤ 5,000 | O(n²) | every pair, 2D DP |
| n ≤ 10⁵ to 10⁶ | O(n log n) or O(n) | sorting, heap, sliding window, two pointers, binary search, BFS/DFS |
| values up to 10⁹ or 10¹⁸ | O(log) | binary search on the answer, math, fast power |
- Find the cue words and the shape of the input.
| Cue in the statement | Pattern |
|---|---|
| longest / shortest contiguous part with a condition | sliding window |
| smallest X that works / minimise the maximum (and "is X enough?" is easy to check) | binary search on the answer |
| fewest steps / moves, every move costs the same | BFS |
| shortest path with different weights | Dijkstra |
| sorted array, find a pair / triple | two pointers |
| "seen before?", "how many of each?" | hash map / hash set |
| sum of a range, many queries | prefix sums (or segment / Fenwick tree with updates) |
| next greater / previous smaller | monotonic stack |
| top k, k-th largest, always the smallest next | heap |
| connected groups, islands, provinces | DFS / BFS / union-find |
| order with prerequisites | topological sort |
| number of ways, best total over choices | dynamic programming |
| all combinations / arrangements, n small | backtracking |
| a dictionary of words, prefixes | trie |
- Write the brute force first, and run it. It gives answers you trust, and something to test the fast version against.
- Find the waste. What does the brute force recompute? The pattern is the tool that removes exactly that.
Problem 1: the canteen (sliding window)
a[i] is the dish served on day i. Find the length of the longest run of consecutive days with at most k different dishes. 0 ≤ n ≤ 2·10⁵.
| Input | Output | Why |
|---|---|---|
a = [1, 2, 1, 2, 3, 3, 3, 3, 4], k = 2 |
5 |
2 3 3 3 3 |
[5, 5, 5], k = 1 |
3 |
one dish |
[], k = 2 |
0 |
no days |
[1, 2, 3], k = 0 |
0 |
no dish allowed |
Step 1: n = 2·10⁵, so O(n²) = 2·10¹⁰ steps is too slow. Step 2: "longest" + "in a row" (contiguous) + "at most" → sliding window.
Brute force: every start, every end
import java.util.*;
public class Main {
static int longest(int[] a, int k) {
int best = 0;
for (int i = 0; i < a.length; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i; j < a.length; j++) {
seen.add(a[j]);
if (seen.size() > k) break;
best = Math.max(best, j - i + 1);
}
}
return best;
}
public static void main(String[] args) {
System.out.println(longest(new int[]{1, 2, 1, 2, 3, 3, 3, 3, 4}, 2));
System.out.println(longest(new int[]{5, 5, 5}, 1));
System.out.println(longest(new int[]{}, 2));
System.out.println(longest(new int[]{1, 2, 3}, 0));
}
}
Output (real):
5
3
0
0
On 200,000 days of only dal and rice (a[i] = i % 2), the set never exceeds two dishes, so no inner loop stops early:
int n = 200_000;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i % 2;
long t0 = System.nanoTime();
int best = longest(a, 2);
System.out.println(best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
With the brute force: Time Limit Exceeded (about 2·10¹⁰ set operations).
The waste and the key insight
The run from day i and the run from day i + 1 share almost all their days, but the brute force throws its set away and recounts. Keep one window: grow it on the right; while it has more than k kinds, shrink it from the left. A set can't tell when the last copy of a dish leaves, so keep a count map.
dish: 1 2 1 2 3 3 3 3 4 k = 2
r = 3: [1 2 1 2] {1:2, 2:2} best 4
r = 4: [1 2 1 2 3] 3 kinds -> shrink: 1, 2, 1 leave
[2 3] {2:1, 3:1}
r = 7: [2 3 3 3 3] {2:1, 3:4} best 5
r = 8: [3 3 3 3 4] drop the 2 answer 5
Solution in Java
import java.util.*;
public class Main {
static int longest(int[] a, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
int best = 0;
for (int l = 0, r = 0; r < a.length; r++) {
cnt.put(a[r], cnt.getOrDefault(a[r], 0) + 1);
while (cnt.size() > k) {
cnt.put(a[l], cnt.get(a[l]) - 1);
if (cnt.get(a[l]) == 0) cnt.remove(a[l]);
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(longest(new int[]{1, 2, 1, 2, 3, 3, 3, 3, 4}, 2));
System.out.println(longest(new int[]{5, 5, 5}, 1));
System.out.println(longest(new int[]{}, 2));
System.out.println(longest(new int[]{1, 2, 3}, 0));
}
}
Output (real):
5
3
0
0
The big test with the window: 200000, 27 ms (real; the time varies). Each day enters once and leaves once: O(n).
A real bug: a dish at count 0 stays in the map
Without if (cnt.get(a[l]) == 0) cnt.remove(a[l]); the map's size never drops, l runs past r onto a dish that was never added, and get returns null:
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null
at Main.longest(Main.java:10)
at Main.main(Main.java:18)
Problem 2: the delivery van (binary search on the answer)
Parcels with weights w[0..n-1] must be delivered in this order in d trips; each trip takes the next few parcels. Find the smallest van capacity. 1 ≤ n ≤ 10⁵, 1 ≤ w[i] ≤ 10⁴.
| Input | Output | Why |
|---|---|---|
w = [4, 8, 5, 1, 2, 7, 3], d = 3 |
12 |
4 8 / 5 1 2 / 7 3 |
same, d = 1 |
30 |
the total |
same, d = 7 |
8 |
the heaviest parcel |
[9], d = 2 |
9 |
one parcel |
Step 1: the capacity can be up to 10⁵ · 10⁴ = 10⁹: you cannot try them all. Step 2: "smallest capacity that works" + checking one capacity is easy (load greedily) → binary search on the answer.
Brute force: try capacity max, max + 1, max + 2, ...
import java.util.*;
public class Main {
static int trips(int[] w, int cap) {
int t = 1, load = 0;
for (int x : w) {
if (load + x > cap) { t++; load = 0; }
load += x;
}
return t;
}
static int minCap(int[] w, int d) {
int cap = 0;
for (int x : w) cap = Math.max(cap, x);
while (trips(w, cap) > d) cap++;
return cap;
}
public static void main(String[] args) {
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 3));
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 1));
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 7));
System.out.println(minCap(new int[]{9}, 2));
}
}
Output (real):
12
30
8
9
On 100,000 parcels and 5 trips:
int n = 100_000;
int[] w = new int[n];
for (int i = 0; i < n; i++) w[i] = 1 + (i * 7919) % 10_000;
long t0 = System.nanoTime();
int cap = minCap(w, 5);
System.out.println(cap + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
With the brute force: Time Limit Exceeded: the answer is about 10⁸, so it tries about 10⁸ capacities, each checking 10⁵ parcels.
The waste and the key insight
A bigger van never needs more trips, so "is it enough for d trips?" is no, no, ..., no, yes, yes, ...: a cliff. Binary search finds the first yes in about log₂(10⁹) ≈ 30 checks.
| capacity | 8 | 9 | 10 | 11 | 12 | 13 | ... | 19 | ... | 30 |
|---|---|---|---|---|---|---|---|---|---|---|
| trips | 5 | 5 | 4 | 4 | 3 | 3 | ... | 2 | ... | 1 |
lo = 8, hi = 30 → try 19 (2 trips, enough, hi = 19) → 13 (enough, hi = 13) → 10 (4, not, lo = 11) → 12 (enough, hi = 12) → 11 (not, lo = 12) → 12, after 5 checks.
Solution in Java
import java.util.*;
public class Main {
static int trips(int[] w, int cap) {
int t = 1, load = 0;
for (int x : w) {
if (load + x > cap) { t++; load = 0; }
load += x;
}
return t;
}
static int minCap(int[] w, int d) {
int lo = 0, hi = 0;
for (int x : w) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (trips(w, mid) <= d) hi = mid;
else lo = mid + 1;
}
return lo;
}
public static void main(String[] args) {
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 3));
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 1));
System.out.println(minCap(new int[]{4, 8, 5, 1, 2, 7, 3}, 7));
System.out.println(minCap(new int[]{9}, 2));
}
}
Output (real):
12
30
8
9
The big test: 100010000, 15 ms (real; the time varies).
A real bug: lo starts at 0
If lo is 0 instead of the heaviest parcel, a capacity smaller than a parcel still "counts a trip" for it, and the search can return an impossible van:
Output (real):
12
30
3
0
Start the search range at a value that can really work (lo = max(w)).
Problem 3: the warehouse robot (BFS)
A robot sits on a rail of slots 1..n. One button moves it u slots ahead, the other d slots back; it can never leave the rail. Find the fewest presses from slot s to slot g, or -1 if impossible. n ≤ 10⁶.
Input (n, s, g, u, d) |
Output | Why |
|---|---|---|
(10, 1, 10, 2, 1) |
6 |
e.g. 1 → 3 → 5 → 7 → 9 → 8 → 10 |
(10, 4, 4, 2, 1) |
0 |
already there |
(10, 1, 10, 2, 0) |
-1 |
only odd slots are reachable |
Step 2: "fewest presses", every press costs 1 → BFS.
Brute force: every sequence of k presses, k = 0, 1, 2, ...
import java.util.*;
public class Main {
static boolean can(int n, int x, int g, int u, int d, int left) {
if (left == 0) return x == g;
if (x + u <= n && can(n, x + u, g, u, d, left - 1)) return true;
return x - d >= 1 && can(n, x - d, g, u, d, left - 1);
}
static int presses(int n, int s, int g, int u, int d) {
for (int k = 0; k <= n; k++)
if (can(n, s, g, u, d, k)) return k;
return -1;
}
public static void main(String[] args) {
System.out.println(presses(10, 1, 10, 2, 1));
System.out.println(presses(10, 4, 4, 2, 1));
System.out.println(presses(10, 1, 10, 2, 0));
}
}
Output (real):
6
0
-1
On a million slots, u = 25,000, d = 1, the answer is 41 presses, so the brute force needs about 2⁴¹ ≈ 2.2 trillion sequences: Time Limit Exceeded.
long t0 = System.nanoTime();
int p = presses(1_000_000, 1, 1_000_000, 25_000, 1);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(p + " presses, " + ms + " ms");
The waste and the key insight
Thousands of different sequences end on the same slot, and from each of them the brute force explores the whole future again. Treat slots as nodes and presses as edges; BFS visits each slot once, nearest first:
| slot | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| presses | 0 | 2 | 1 | 3 | 2 | 4 | 3 | 5 | 4 | 6 |
Solution in Java
import java.util.*;
public class Main {
static int presses(int n, int s, int g, int u, int d) {
int[] dist = new int[n + 1];
Arrays.fill(dist, -1);
ArrayDeque<Integer> q = new ArrayDeque<>();
dist[s] = 0;
q.add(s);
while (!q.isEmpty()) {
int x = q.poll();
if (x == g) return dist[x];
for (int y : new int[]{x + u, x - d})
if (y >= 1 && y <= n && dist[y] == -1) {
dist[y] = dist[x] + 1;
q.add(y);
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(presses(10, 1, 10, 2, 1));
System.out.println(presses(10, 4, 4, 2, 1));
System.out.println(presses(10, 1, 10, 2, 0));
}
}
Output (real):
6
0
-1
The big test: 41 presses, 6 ms (real; the time varies).
A real bug: no rail check
With only if (dist[y] == -1), slot 1 − 1 = 0 is accepted (the array has index 0), and then 0 − 1 = −1 crashes:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 11
at Main.presses(Main.java:14)
at Main.main(Main.java:22)
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// Problem 1: longest run with at most k different dishes (sliding window)
int longest(const vector<int>& a, int k) {
unordered_map<int, int> cnt;
int best = 0;
for (int l = 0, r = 0; r < (int)a.size(); r++) {
cnt[a[r]]++;
while ((int)cnt.size() > k) {
if (--cnt[a[l]] == 0) cnt.erase(a[l]);
l++;
}
best = max(best, r - l + 1);
}
return best;
}
// Problem 2: smallest van capacity for d trips (binary search on the answer)
int trips(const vector<int>& w, long long cap) {
int t = 1; long long load = 0;
for (int x : w) {
if (load + x > cap) { t++; load = 0; }
load += x;
}
return t;
}
long long minCap(const vector<int>& w, int d) {
long long lo = 0, hi = 0;
for (int x : w) { lo = max(lo, (long long)x); hi += x; }
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (trips(w, mid) <= d) hi = mid;
else lo = mid + 1;
}
return lo;
}
// Problem 3: fewest presses for the robot (BFS)
int presses(int n, int s, int g, int u, int d) {
vector<int> dist(n + 1, -1);
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
int x = q.front(); q.pop();
if (x == g) return dist[x];
for (int y : {x + u, x - d})
if (y >= 1 && y <= n && dist[y] == -1) { dist[y] = dist[x] + 1; q.push(y); }
}
return -1;
}
int main() {
cout << longest({1, 2, 1, 2, 3, 3, 3, 3, 4}, 2) << " " << longest({5, 5, 5}, 1) << " "
<< longest({}, 2) << " " << longest({1, 2, 3}, 0) << "\n";
vector<int> w = {4, 8, 5, 1, 2, 7, 3};
cout << minCap(w, 3) << " " << minCap(w, 1) << " " << minCap(w, 7) << " " << minCap({9}, 2) << "\n";
cout << presses(10, 1, 10, 2, 1) << " " << presses(10, 4, 4, 2, 1) << " " << presses(10, 1, 10, 2, 0) << "\n";
vector<int> a(200000); for (int i = 0; i < 200000; i++) a[i] = i % 2;
vector<int> big(100000); for (int i = 0; i < 100000; i++) big[i] = 1 + (int)((long long)i * 7919 % 10000);
cout << longest(a, 2) << " " << minCap(big, 5) << " " << presses(1000000, 1, 1000000, 25000, 1) << "\n";
}
Output (real):
5 3 0 0
12 30 8 9
6 0 -1
200000 100010000 41
The same solutions in Python
from collections import deque
def longest(a, k): # Problem 1: sliding window
cnt, best, l = {}, 0, 0
for r, x in enumerate(a):
cnt[x] = cnt.get(x, 0) + 1
while len(cnt) > k:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]]
l += 1
best = max(best, r - l + 1)
return best
def trips(w, cap):
t, load = 1, 0
for x in w:
if load + x > cap:
t, load = t + 1, 0
load += x
return t
def min_cap(w, d): # Problem 2: binary search on the answer
lo, hi = max(w), sum(w)
while lo < hi:
mid = (lo + hi) // 2
if trips(w, mid) <= d:
hi = mid
else:
lo = mid + 1
return lo
def presses(n, s, g, u, d): # Problem 3: BFS
dist = [-1] * (n + 1)
dist[s] = 0
q = deque([s])
while q:
x = q.popleft()
if x == g:
return dist[x]
for y in (x + u, x - d):
if 1 <= y <= n and dist[y] == -1:
dist[y] = dist[x] + 1
q.append(y)
return -1
print(longest([1, 2, 1, 2, 3, 3, 3, 3, 4], 2), longest([5, 5, 5], 1), longest([], 2), longest([1, 2, 3], 0))
w = [4, 8, 5, 1, 2, 7, 3]
print(min_cap(w, 3), min_cap(w, 1), min_cap(w, 7), min_cap([9], 2))
print(presses(10, 1, 10, 2, 1), presses(10, 4, 4, 2, 1), presses(10, 1, 10, 2, 0))
a = [i % 2 for i in range(200_000)]
big = [1 + (i * 7919) % 10_000 for i in range(100_000)]
print(longest(a, 2), min_cap(big, 5), presses(1_000_000, 1, 1_000_000, 25_000, 1))
Output (real):
5 3 0 0
12 30 8 9
6 0 -1
200000 100010000 41
Complexity
| Problem | Approach | Time | Extra memory | Big test |
|---|---|---|---|---|
| Canteen | every start, every end | O(n²) | O(k) | 200,000 days: Time Limit Exceeded |
| Canteen | sliding window + count map | O(n) | O(k) | fast |
| Van | try every capacity | O(n · (sum − max)) | O(1) | 100,000 parcels: Time Limit Exceeded |
| Van | binary search on the answer | O(n log sum) | O(1) | fast |
| Robot | every press sequence | O(2ᵏ), k = presses | O(k) stack | 41 presses: Time Limit Exceeded |
| Robot | BFS | O(n) | O(n) | fast |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Dish at count 0 left in the map | NullPointerException ... Map.get(Object) is null |
the map's size never drops | remove at count 0 |
lo = 0 in the search on the answer |
capacity 3 for 7 trips, 0 for one parcel |
that answer can't work | lo = the heaviest parcel |
| No bounds check in BFS | ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 11 |
the robot left the rail | check 1 ≤ y ≤ n first |
| Marking visited when a node is taken out, not when it's added | right answers, but a slot can be queued many times (slower) | duplicates in the queue | set dist[y] when you add |
int mid = (lo + hi) / 2 with big values |
negative mid, wrong answer |
integer overflow | lo + (hi - lo) / 2 |
| Optimising before writing the brute force | a fast wrong answer with nothing to compare | no reference | brute force first, then stress test |
Mini project: a stress tester
Write a program that generates thousands of small random inputs, runs the brute force and the fast solution on each, and stops on the first mismatch. This is how you prove the fast version against the trusted brute force:
import java.util.*;
public class Main {
static int brute(int[] a, int k) {
int best = 0;
for (int i = 0; i < a.length; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i; j < a.length; j++) {
seen.add(a[j]);
if (seen.size() > k) break;
best = Math.max(best, j - i + 1);
}
}
return best;
}
static int fast(int[] a, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
int best = 0;
for (int l = 0, r = 0; r < a.length; r++) {
cnt.put(a[r], cnt.getOrDefault(a[r], 0) + 1);
while (cnt.size() > k) {
cnt.put(a[l], cnt.get(a[l]) - 1);
if (cnt.get(a[l]) == 0) cnt.remove(a[l]);
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}
public static void main(String[] args) {
Random rnd = new Random(89);
for (int t = 1; t <= 10_000; t++) {
int n = rnd.nextInt(12), k = rnd.nextInt(4);
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = rnd.nextInt(5);
if (brute(a, k) != fast(a, k)) {
System.out.println("MISMATCH on " + Arrays.toString(a) + " k=" + k);
return;
}
}
System.out.println("10000 random tests passed");
}
}
Output (real):
10000 random tests passed
Break the fast version on purpose (remove the remove line, or change > to >=) and watch the tester print the smallest failing input.
Practice
1. Longest substring with at most K distinct characters: the canteen on a string.
2. Capacity to ship packages within D days (LeetCode 1011): the delivery van; the code above passes it unchanged.
3. Open the Lock (LeetCode 752): four wheels, each turn moves one wheel ±1; fewest turns from 0000 to the target, avoiding dead ends.
4. Name the pattern: (a) "the minimum number of minutes until every orange in a grid is rotten", (b) "the k-th largest element in a stream", (c) "the number of ways to climb n stairs taking 1 or 2 steps", (d) "the shortest subarray with sum ≥ target, all values positive", (e) "can all courses be finished given prerequisites?".
Solutions
1. Same window, with an array of counts and a kinds counter:
import java.util.*;
public class Main {
// At most K distinct characters: the same window, on a string
static int longestK(String s, int k) {
int[] cnt = new int[128];
int kinds = 0, best = 0;
for (int l = 0, r = 0; r < s.length(); r++) {
if (cnt[s.charAt(r)]++ == 0) kinds++;
while (kinds > k)
if (--cnt[s.charAt(l++)] == 0) kinds--;
best = Math.max(best, r - l + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(longestK("eceba", 2));
System.out.println(longestK("aa", 1));
System.out.println(longestK("abc", 0));
}
}
Output (real):
3
2
0
3. BFS over the 10,000 lock states; each state has 8 neighbours (each wheel up or down):
import java.util.*;
public class Main {
// Open the lock: 4 wheels 0-9, fewest turns from "0000" to target, avoiding dead ends
static int openLock(String[] deadends, String target) {
Set<String> seen = new HashSet<>(Arrays.asList(deadends));
if (seen.contains("0000")) return -1;
ArrayDeque<String> q = new ArrayDeque<>();
q.add("0000");
seen.add("0000");
for (int steps = 0; !q.isEmpty(); steps++) {
for (int size = q.size(); size > 0; size--) {
String cur = q.poll();
if (cur.equals(target)) return steps;
char[] c = cur.toCharArray();
for (int i = 0; i < 4; i++) {
char old = c[i];
for (int delta : new int[]{1, 9}) {
c[i] = (char) ('0' + (old - '0' + delta) % 10);
String next = new String(c);
if (seen.add(next)) q.add(next);
}
c[i] = old;
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
System.out.println(openLock(new String[]{"8888"}, "0009"));
System.out.println(openLock(new String[]{"0000"}, "8888"));
}
}
Output (real):
6
1
-1
4. (a) multi-source BFS ("minimum minutes", every step costs 1); (b) a min-heap of size k ("k-th largest"); (c) DP ("number of ways"); (d) sliding window ("shortest contiguous", positives only, so shrinking never hurts); (e) topological sort ("prerequisites").
Quick quiz
At most 15 cities. Visit every city exactly once, start and end at city 0, cheapest total road cost. Which pattern? A) sliding window B) binary search on the answer C) bitmask DP over subsets D) BFS
Answer
C. n ≤ 15, so 2ⁿ fits. "Visit every city" means remembering the set of visited cities (a bitmask), and "cheapest total over choices" is DP: O(2ⁿ · n²) ≈ 7 million steps.
Interview questions
- How do you pick an approach in an interview? Read the constraints for the budget, look for cue words, say the brute force and its complexity out loud, then find what it repeats.
- When is binary search on the answer valid? When a yes/no check exists and its answers are monotonic in the value (a cliff).
- Why BFS and not DFS for "fewest moves"? BFS reaches nodes in order of distance, so the first visit is the shortest; DFS may find a long path first.
- When does a sliding window fail? When shrinking the window can make it valid again in a non-monotonic way, e.g. "subarray sum equals k" with negative numbers: use prefix sums + a hash map instead.
- What if the moves have different costs? Use Dijkstra (non-negative weights) or 0-1 BFS (costs 0 and 1).
- Why write the brute force at all? It's correct by construction, it gives test answers, and its waste tells you the pattern.
Glossary
| Term | Meaning |
|---|---|
| Pattern | A known technique for a family of problems |
| Constraints | The input limits in the statement |
| Big O | How steps grow with the input size |
| Time budget | About 10⁸ simple steps a second |
| Brute force | Try every possibility |
| Waste | Work the brute force repeats |
| TLE | Time Limit Exceeded |
| Contiguous | Next to each other, no gaps |
| Sliding window | A range [l, r] that grows right and shrinks left |
| Count map | Value → how many times it occurs |
| Monotonic | Only ever goes one way |
| Binary search on the answer | Binary search over answer values with a yes/no check |
| Greedy check | Fill each trip as much as possible |
| Integer overflow | A value too big for its type |
| Graph, node, edge | Places and the moves between them |
| BFS | Explore ring by ring; the first visit is the fewest moves |
| Queue | First in, first out |
| Bitmask DP | DP whose state includes a set stored in bits |
| Stress test | Compare brute force and fast code on many random inputs |
Summary
- The method: constraints → budget, cue words → pattern, brute force first, find the waste.
- Longest/shortest contiguous with a condition → sliding window (O(n)).
- Smallest value that works, with an easy monotonic check → binary search on the answer (O(n log range)).
- Fewest steps, each costing the same → BFS (O(nodes + edges)).
- Always keep the brute force: run it, then stress-test the fast solution against it.
- Next episode: the mock interview: two hard problems, end to end.