Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
An `n × m` grid has `k` train tracks; track `i` covers row `r`, columns `c1..c2` inclusive. Count cells with **no** track. The grid is huge (`n, m ≤ 10⁹`) so you can't touch every cell — group track segments by row in a hash map, **merge overlapping intervals** within each row, sum the merged lengths to get covered cells, then return `n·m − covered`. Use `long` for `n·m` (up to 10¹⁸).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid enumerating a 10⁹×10⁹ grid and instead reduce the problem to per-row interval merging, plus whether you handle the inclusive count and 64-bit multiplication.
Where candidates slip
Allocating or scanning an n×m grid (memory/time blowup), forgetting to merge overlapping segments (double counting covered cells), the `b − a` vs `b − a + 1` off-by-one, or overflowing `n·m` with 32-bit math.
How to stand out
State up front that the grid size forbids enumeration, that only k segments matter, and that overlaps within a row must be merged so covered cells are counted once; then call out the long cast on n·m.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Group by row, merge overlaps, subtract the union from n·m.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Mark Every Covered Cell
1Hint 1Explore hintHide hint
The naive idea: a boolean grid, mark every track cell, count the unmarked ones.
2Hint 2Explore hintHide hint
How big is that grid when n and m are 10⁹? Estimate the memory and time.
3Hint 3Explore hintHide hint
Even a per-row set of covered columns blows up when m is 10⁹ and segments are wide.
A · Core idea
The literal approach: allocate an n × m grid of booleans, set true for every cell under a track, then count the false cells.
Why it's hopeless here. With n = m = 10⁹, the grid has 10¹⁸ cells — far beyond any machine's memory, and scanning it is 10¹⁸ operations. Even a sparser variant that stores a set of covered (row, column) pairs explodes when a single track spans up to 10⁹ columns.
What it teaches. It pins down the definition — covered cells are the union of track cells, free cells are the rest — and makes the constraint scream that we must work with segments, not cells. That realization is the whole point of mentioning it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, m = 4, tracks = [[2,2,3],[3,1,4],[4,4,4]]Array state
mark row 3
columns 1–4 all covered
9C · Code with teaching comments
Reference implementation previewpublic long gridlandMetro(int n, int m, int k, int[][] track) { // Conceptual only — infeasible for large n, m. boolean[][] covered = new boolean[n][m]; for (int[] t : track) { int r = t[0] - 1;Explore the full codeHide the full code
D · Why it works and complexityO(n·m) or O(k·m) timeO(n·m) spaceOpen the invariant and proofExplore the proofHide the proof
The grid dimensions (10⁹) versus the track count (≤ 1000) are a deliberate mismatch: the problem is telling you to process the 1000 segments, never the 10¹⁸ cells.
ComplexityO(n·m) or O(k·m) time, O(n·m) space — An n×m boolean grid is up to 10¹⁸ cells — impossible to allocate or scan; even marking each covered column is O(total covered) which can be ~k·m.
E · Edge cases and pitfalls5n = m = 10⁹, k = 0 — Cannot allocate the grid at all — must special-case to n·m.Explore edge casesHide edge cases
Edge cases handled
n = m = 10⁹, k = 0Cannot allocate the grid at all — must special-case to n·m.single wide track [1,1,10⁹]Marking each of 10⁹ columns is already too slow.
Pitfalls
- Allocating an n×m grid — out of memory for large inputs.
- Scanning every cell — 10¹⁸ operations.
- Assuming the grid is small because the example is.
Approach 2 of 2 · Optimal
Group by Row + Merge Intervals (Optimal)
1Hint 1Explore hintHide hint
Tracks in different rows are independent. Bucket the segments by row in a hash map.
2Hint 2Explore hintHide hint
Within a row, overlapping segments share cells — sort by start column and merge so each cell is counted once.
3Hint 3Explore hintHide hint
Sum merged lengths (end − start + 1) for total covered, then return n·m − covered with 64-bit math.
A · Core idea
Work only with the k ≤ 1000 segments. Three steps:
1. Bucket by row. Put each segment [c1, c2] into a hash map keyed by its row. Segments in different rows can never overlap, so each row is solved independently. This also means we only ever store rows that actually contain track — at most k of them.
2. Merge overlapping intervals per row. Sort a row's segments by start column. Walk them keeping a current interval [start, end]; if the next segment starts at ≤ end, it overlaps (or touches) the current one, so extend end = max(end, segEnd). Otherwise the current interval is finalized — add its length and start a new one. This collapses overlaps so shared cells are counted exactly once.
3. Sum and subtract. Each finalized interval [start, end] covers end − start + 1 cells (inclusive). Summing across all rows gives covered. The answer is n·m − covered.
The 64-bit detail. n·m reaches 10¹⁸, which overflows a 32-bit int. In Java compute (long) n * m — casting before the multiply, or the int×int product overflows before the cast can help. Python integers are unbounded, so the port is naturally safe.
Why merging matters. If two segments in a row overlap and you sum their raw lengths, the shared cells are counted twice, inflating covered and shrinking the answer. Merging into the union length is what keeps it correct.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, m = 4, tracks = [[2,2,3],[3,1,4],[4,4,4]]Array state
segments [1,2],[2,3]
2 ≤ 2 → extend end to 3
9C · Code with teaching comments
D · Why it works and complexityO(k log k) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
The constraint mismatch (10⁹ grid vs ≤ 1000 tracks) is the algorithm's signpost: stop thinking in cells, think in segments. 'Total minus the union of ranges' with per-key interval merging is a reusable shape — it solves room-booking conflicts, covered-length problems, and calendar free-time queries.
ComplexityO(k log k) time, O(k) space — Bucketing is O(k); sorting all segments costs O(k log k) total; merging is linear in k. Space is O(k) for the buckets — independent of n and m.
E · Edge cases and pitfalls5k = 0 — No buckets → covered = 0 → answer = n·m.Explore edge casesHide edge cases
Edge cases handled
k = 0No buckets → covered = 0 → answer = n·m.tracks = [[1,1,2],[1,2,3]]Overlap at column 2 → merged [1,3] covers 3, not 4.
Pitfalls
- Skipping the merge — overlapping segments double count covered cells.
- Using `b − a` instead of `b − a + 1` — undercounts each interval by one.
- Computing n*m as int before casting — overflows; use (long) n * m.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long gridlandMetro(int n, int m, int k, int[][] track) { Map<Integer, List<int[]>> rows = new HashMap<>(); for (int[] t : track) { rows.computeIfAbsent(t[0], z -> new ArrayList<>()) .add(new int[]{t[1], t[2]});Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Materializing the grid
With n, m up to 10⁹, an n×m structure needs up to 10¹⁸ entries — impossible. Process only the k segments.
Explore the code comparisonHide the code comparison
Materializing the grid
With n, m up to 10⁹, an n×m structure needs up to 10¹⁸ entries — impossible. Process only the k segments.
Don't write this
boolean[][] covered = new boolean[n][m];Write this instead
Map<Integer, List<int[]>> rows = new HashMap<>();
// bucket segments by row, then merge2Forgetting to merge overlaps
Two overlapping segments in a row share cells; summing their raw lengths counts those cells twice and shrinks the answer.
Explore the code comparisonHide the code comparison
Forgetting to merge overlaps
Two overlapping segments in a row share cells; summing their raw lengths counts those cells twice and shrinks the answer.
Don't write this
covered += sum(c2 - c1 + 1 for c1, c2 in segs)Write this instead
segs.sort()
cur_start, cur_end = segs[0]
for s_start, s_end in segs[1:]:
if s_start <= cur_end:
cur_end = max(cur_end, s_end)
else:
covered += cur_end - cur_start + 1
cur_start, cur_end = s_start, s_end
covered += cur_end - cur_start + 1332-bit overflow on n·m
n·m reaches 10¹⁸; an int product wraps around. Cast to long before multiplying.
Explore the code comparisonHide the code comparison
32-bit overflow on n·m
n·m reaches 10¹⁸; an int product wraps around. Cast to long before multiplying.
Don't write this
return n * m - covered;Write this instead
return (long) n * m - covered;Revise
Carry the pattern into the interview
Pattern to remember
Group intervals by key, merge overlaps, subtract from total
Code pattern to memorize
rows = group segments by row -> list of [c1, c2]
covered = 0
for each row's segments:
sort by c1
merge overlapping/touching, sum (end - start + 1)
covered += merged length
answer = (long) n * m - coveredRules to remember
- 1Never iterate the grid:
nandmcan each be 10⁹, son·mis up to 10¹⁸ — only touch thek ≤ 1000track segments. - 2Group segments by row first; tracks in different rows can't overlap, so merging is per-row.
- 3Sort each row's segments by start column, then merge: extend the current interval while the next start
≤current end. - 4A merged interval
[a, b]coversb − a + 1cells (inclusive count) — the classic off-by-one to get right. - 5Compute
n·mas a long ((long) n * min Java); multiplying two ints first overflows before the cast.
Use this pattern when
- Total space minus a union of ranges/segments
- Coordinates are far too large to enumerate; only the segments are bounded
- Overlapping ranges must be counted once (union length)
- Segments partition naturally by a key (row, day, channel)
Choose another pattern when
- Grid is small enough to mark cells directly → a boolean grid is simpler
- Ranges never overlap → just sum lengths, no merge needed
- You need the uncovered cells themselves, not the count → different output shape
- Segments span multiple rows as rectangles → 2D sweep / interval tree, not per-row merge
Interview takeaway
When the board is astronomically large but the marked regions are few, ignore the board and work with the regions: bucket intervals by row, merge each bucket's overlaps into a union length, and subtract from `n·m`. Watch the inclusive `+1` and the 64-bit product.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternUnion-of-intervals minus total. When the universe is too large to enumerate but the marked regions are few, bucket the regions by key, merge overlaps into a union length, and subtract from the total. Mind the inclusive +1 and 64-bit product.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Merge IntervalsComing soonThe core sub-routine here — collapse overlapping intervals into their union.
- Array ManipulationRange updates on a huge line solved with a difference array instead of merging.
- Meeting Rooms IIComing soonInterval overlaps again, but counting maximum simultaneous overlaps.