This multi-part question evaluates algorithmic problem-solving across frequency counting (equal-value pairs), simulation and in-place grid transformation (match-three gravity), matrix diagonal pattern checking, and interval/range data-structure management, emphasizing correctness under constraints and rigorous time/space complexity reasoning.
You will solve four independent coding tasks:
1) Count equal-value pairs in an array:
Given an integer array nums of length n, return the number of index pairs (i, j) with 0 ≤ i < j < n and nums[i] = nums[j]. Target time/space: O(n) time using O(n) auxiliary space. Explain the approach and complexity.
2) Simulate a match-three board with gravity:
Given an R × C grid board of uppercase letters (colors) or '.' for empty. Repeatedly, in a single round, mark every cell that belongs to any horizontal or vertical run of length ≥ 3 of the same letter (runs can overlap). Remove all marked cells (set to '.'), then apply gravity so that in each column letters fall down and '.' move up. Repeat rounds until the board is stable (no removals). Return the final grid. Constraints: 1 ≤ R, C ≤ 50. Describe the algorithm and its complexity.
3) Check an X-pattern in a square matrix:
Given an n × n integer matrix, return true iff every element on the main diagonal and the anti-diagonal is non-zero and every other element is zero; otherwise return false. Constraints: 1 ≤ n ≤ 100. Provide the check and complexity.
4) Process block placement queries on a line:
You have N empty positions labeled 1..N. Process Q operations of two types:
- Place l r: mark all positions in the inclusive interval [l, r] as occupied (placing on already-occupied cells has no additional effect).
- Query k: return the leftmost starting index s such that there exists a contiguous unoccupied segment [s, s+k-1] of length k; if no such segment exists, return -1.
Design a data structure to support up to N, Q ≤ 2×10^5 with near O((N + Q) log N) total time. Explain the data structures used and provide the algorithm.
Overview: This multi-part question evaluates algorithmic problem-solving across frequency counting (equal-value pairs), simulation and in-place grid transformation (match-three gravity), matrix diagonal pattern checking, and interval/range data-structure management, emphasizing correctness under constraints and rigorous time/space complexity reasoning.
You are given four independent coding tasks. They may be solved in any order, and partial test-case credit is awarded for each task. The tasks are roughly increasing in difficulty: the first is a warm-up array problem and the last requires a non-trivial data structure.
For each task, implement a correct, efficient solution and clearly state its time and space complexity in terms of the stated input sizes.
Constraints & Assumptions
The four tasks are scored independently; a partially-passing solution to a later task can still earn points, so attempt every task.
Inputs are well-formed (valid array, rectangular grid, square matrix, in-range query parameters) unless a task says otherwise — but you should still articulate any assumptions you make.
Per-task size limits are given inside each Part; respect them when choosing an asymptotically efficient approach.
Clarifying Questions to Ask Guidance
What are the value ranges of the array / matrix entries (do they fit in a 32-bit or 64-bit integer, and can the equal-pair count overflow)?
For the match-three board, are diagonal runs considered, or only horizontal and vertical runs?
For the match-three board, in a single round are
all
marks computed from the pre-removal board simultaneously, or sequentially as cells are removed?
For the block-placement task, are the
Place
and
Query
operations interleaved arbitrarily, and is
k
always in
[1,N]
?
What is the expected output format (return value, printed grid, boolean) for each task?
Part 1 — Count equal-value pairs in an array
Given an integer array nums of length n, return the number of index pairs (i,j) with 0≤i<j<n and nums[i] == nums[j]. Target: O(n) time using O(n) auxiliary space.
What This Part Should Cover Guidance
A single-pass hash-map approach (value → running frequency) rather than the
O(n2)
double loop.
Correct combinatorial counting via
(2c)
or the incremental "add prior count" technique.
Awareness that the answer can exceed 32-bit range when many duplicates exist (use 64-bit).
Part 2 — Simulate a match-three board with gravity
Given an R×C grid board of uppercase letters (colors) or '.' for empty, simulate rounds until the board is stable:
Mark
every cell that belongs to any horizontal or vertical run of length
≥3
of the same letter (overlapping runs are all marked).
Remove
all marked cells (set them to
'.'
).
Gravity
: in each column, existing letters fall to the bottom and
'.'
rise to the top.
Repeat until a round produces no removals. Return the final grid. Constraints: 1≤R,C≤50.
What This Part Should Cover Guidance
A two-phase round (mark-all-then-remove) that handles overlapping horizontal/vertical runs correctly.
A correct per-column gravity (compaction) step.
The fixed-point loop that repeats until stable, plus the worst-case complexity bound in terms of
R
,
C
.
Part 3 — Check an X-pattern in a square matrix
Given an n×n integer matrix, return true iff every element on the main diagonal and the anti-diagonal is non-zero and every other element is zero; otherwise return false. Constraints: 1≤n≤100.
What This Part Should Cover Guidance
Correct identification of diagonal vs. off-diagonal cells via
i=j
and
i+j=n−1
.
The two complementary checks: on-diagonal cells must be non-zero, off-diagonal cells must be zero.
A clean single
O(n2)
scan, plus correctness for the
n=1
edge case (the single cell is on both diagonals).
Part 4 — Process block-placement queries on a line
You have N empty positions labeled 1…N. Process Q operations of two types:
Place l r
: mark every position in the inclusive interval
[l,r]
as occupied (re-placing on already-occupied cells has no extra effect).
Query k
: return the
leftmost
starting index
s
such that the contiguous segment
[s,s+k−1]
is entirely
unoccupied
(length
k
); if no such segment exists, return
−1
.
Design a data structure supporting N,Q≤2×105 with near O((N+Q)logN) total time. Explain the structures used and the algorithm.
What This Part Should Cover Guidance
A segment tree (or interval set) storing
best
/
prefix
/
suffix
free-run lengths per node.
A correct merge rule that joins free runs spanning the child boundary.
Lazy propagation for the range
Place
assignment, and a
O(logN)
descent that finds the
leftmost
qualifying start index.
Complexity argument reaching
O((N+Q)logN)
.
What a Strong Answer Covers Guidance
Across all four parts, a strong submission demonstrates: choosing the asymptotically right approach for each stated size limit (not just a brute force); precise complexity statements; clean handling of edge cases (empty array, n=1 matrix, fully-occupied line, k>N); and idiomatic, bug-free code. The strongest candidates also note the few subtle pitfalls — integer overflow in Part 1, simultaneous-vs-sequential marking in Part 2, the both-diagonals cell in Part 3, and the boundary-straddling free run in Part 4.
Follow-up Questions Guidance
Part 1:
How would you instead count pairs
(i,j)
where
nums[i] == nums[j]andj−i≤D
for a given window
D
? What changes in the data structure?
Part 2:
If diagonal runs of length
≥3
also cleared, how would your marking pass change, and would the complexity bound still hold?
Part 4:
How would you additionally support an
Erase l r
operation (freeing a range) while keeping all operations
O(logN)
? What invariant does lazy propagation need to preserve?
General:
Several of these are independent subproblems. If they instead shared state (e.g. Part 4's line drove Part 2's gravity), how would you structure the code to keep each component testable?
