## Overview Four independent tasks, scored separately. Below, each part gives the approach, reference implementation (Python), correctness reasoning, edge cases, and complexity. The difficulty ramp is real: Parts 1 and 3 are linear scans, Part 2 is a fixed-point grid simulation, and Part 4 needs a segment tree with lazy range-assignment and a guided descent. --- ## Part 1 — Count equal-value pairs ### Approach Brute force over all pairs is $O(n^2)$. Instead, group indices by value: a value occurring $c$ times contributes $\binom{c}{2} = \frac{c(c-1)}{2}$ pairs $(i, j)$ with $i < j$. We can accumulate this in a single pass using the identity $$\binom{c}{2} = \sum_{t=0}^{c-1} t,$$ i.e. the $t$-th occurrence of a value forms exactly $t$ new pairs with its $t$ earlier occurrences. So we keep a running frequency map and, when we see a value for the $(t+1)$-th time, add the current count `t` to the answer *before* incrementing. ### Implementation ```python from collections import defaultdict def count_equal_pairs(nums): seen = defaultdict(int) ans = 0 for x in nums: ans += seen[x] # pairs with all earlier equal elements seen[x] += 1 return ans ``` Equivalently, count frequencies first and sum $c(c-1)//2$ over values — both are $O(n)$. ### Correctness Each unordered pair $(i, j)$, $i < j$, with `nums[i] == nums[j]` is counted exactly once: at the moment we process index $j$, `seen[nums[j]]` equals the number of earlier equal elements, all with index $< j$. Summed over $j$, this is the total pair count. ### Edge cases & pitfalls - **Overflow**: with $n$ identical values the answer is $\binom{n}{2} \approx n^2/2$. For $n = 2\times10^5$ that is $\sim 2\times10^{10}$, which exceeds 32-bit range — use a 64-bit integer (Python's `int` is arbitrary precision; in Java/C++ use `long`). - Empty array or all-distinct array → `0`. ### Complexity $O(n)$ time, $O(n)$ auxiliary space (the frequency map). Matches the target. --- ## Part 2 — Match-three board with gravity (LeetCode 723 "Candy Crush") ### Approach One **round** has three phases, and the key correctness point is that marking must be computed against the *current, un-mutated* board: 1. **Mark**: scan all rows for horizontal runs of $\ge 3$ equal letters and all columns for vertical runs of $\ge 3$; flag every cell in any such run. Overlapping runs are naturally handled because we OR the flags. Use a separate boolean array (or a reversible in-place marker) so a cell already flagged horizontally still gets checked vertically against its original letter. 2. **Remove**: set every flagged cell to `'.'`. 3. **Gravity**: for each column independently, let the surviving letters fall to the bottom and push `'.'` to the top. Repeat until a round flags nothing (a fixed point). ### Implementation ```python def candy_crush(board): if not board or not board[0]: return board R, C = len(board), len(board[0]) while True: to_clear = [[False] * C for _ in range(R)] found = False # Horizontal runs (>= 3) for r in range(R): run = 1 for c in range(1, C): if board[r][c] != '.' and board[r][c] == board[r][c - 1]: run += 1 else: if run >= 3: for k in range(c - run, c): to_clear[r][k] = True found = True run = 1 if run >= 3: for k in range(C - run, C): to_clear[r][k] = True found = True # Vertical runs (>= 3) for c in range(C): run = 1 for r in range(1, R): if board[r][c] != '.' and board[r][c] == board[r - 1][c]: run += 1 else: if run >= 3: for k in range(r - run, r): to_clear[k][c] = True found = True run = 1 if run >= 3: for k in range(R - run, R): to_clear[k][c] = True found = True if not found: return board # Remove for r in range(R): for c in range(C): if to_clear[r][c]: board[r][c] = '.' # Gravity per column (letters fall to bottom) for c in range(C): write = R - 1 for r in range(R - 1, -1, -1): if board[r][c] != '.': board[write][c] = board[r][c] write -= 1 for r in range(write, -1, -1): board[r][c] = '.' ``` ### Correctness - **Simultaneous marking**: computing `to_clear` fully from the pre-removal board, then deleting, guarantees overlapping vertical/horizontal runs (e.g. a cell at the intersection of a row-run and a column-run) are all cleared in the same round, matching the problem's "mark every cell in any run" semantics. - The `board[r][c] != '.'` guard prevents an empty cell from extending a run. - **Gravity** writes survivors bottom-up so their relative vertical order is preserved, then fills the top with `'.'`. - The `while` loop terminates because every productive round strictly reduces the count of non-`'.'` cells, which is bounded by $R \cdot C$. ### Edge cases - A run exactly at the right/bottom edge is handled by the post-loop `if run >= 3` check. - No runs anywhere → returns immediately, board unchanged. - A board that is a single row or single column works since horizontal and vertical scans are independent. ### Complexity Each round is $O(RC)$ (constant number of full passes). The number of rounds is $O(RC)$ in the worst case (each round may clear as few as 3 cells), so worst case $O(R^2C^2)$. With $R, C \le 50$ that is at most $\sim 6\times10^6$ cell-touches — comfortably fast. Space is $O(RC)$ for the marker array. --- ## Part 3 — X-pattern check in a square matrix (LeetCode 2319) ### Approach A cell $(i, j)$ in an $n \times n$ matrix lies on the **main diagonal** iff $i = j$ and on the **anti-diagonal** iff $i + j = n - 1$. The pattern is valid iff: - every on-diagonal cell (on either diagonal) is **non-zero**, and - every off-diagonal cell is **zero**. One $O(n^2)$ pass classifies each cell and verifies the right condition. ### Implementation ```python def check_x_matrix(grid): n = len(grid) for i in range(n): for j in range(n): on_diag = (i == j) or (i + j == n - 1) if on_diag: if grid[i][j] == 0: return False else: if grid[i][j] != 0: return False return True ``` ### Correctness The two predicates $i = j$ and $i + j = n - 1$ are exactly the membership tests for the two diagonals; their union is the "X". The loop enforces the on/off condition for every cell, so it returns `True` only when the whole matrix matches. ### Edge cases - **$n = 1$**: the single cell $(0,0)$ satisfies both $i = j$ and $i + j = n - 1 = 0$, so it is on-diagonal and must be non-zero — the code returns `True` iff `grid[0][0] != 0`, which is the intended result. - **Odd $n$**: the center cell $(m, m)$ where $m = (n-1)/2$ lies on both diagonals; it is correctly treated as on-diagonal (must be non-zero), and we never require it to be zero. ### Complexity $O(n^2)$ time, $O(1)$ extra space. --- ## Part 4 — Block-placement queries (segment tree on free runs, LeetCode 3161 "Block Placement Queries") ### Goal Support, over positions $1 \ldots N$: - `Place l r`: set $[l, r]$ occupied (idempotent). - `Query k`: leftmost $s$ with $[s, s+k-1]$ fully free, else $-1$. with $N, Q \le 2\times10^5$ at $O((N+Q)\log N)$. ### Data structure A **segment tree** over positions where each node covering range $[lo, hi]$ stores, for the cells currently free in that range: - `best` — length of the longest run of consecutive free cells inside $[lo, hi]$, - `pref` — length of the longest free run starting at `lo`, - `suf` — length of the longest free run ending at `hi`, - a lazy `assign` flag for range "set occupied" (we only ever set occupied, never free, so a single lazy value `OCCUPIED` suffices). A leaf for a free cell has `best = pref = suf = 1`; for an occupied cell all are `0`. ### Merge rule Combining left child $L$ (length $\ell$) and right child $R$ (length $r$): ``` node.best = max(L.best, R.best, L.suf + R.pref) # run straddling the boundary node.pref = L.pref + (R.pref if L.pref == ℓ else 0) # left fully free spills into right node.suf = R.suf + (L.suf if R.suf == r else 0) ``` The crucial middle term `L.suf + R.pref` stitches free cells across the child boundary, which is what lets us find runs that span subtrees. ### Place (range-assign occupied with lazy propagation) Standard lazy segment-tree range update: if a node's range is fully inside $[l, r]$, set all three stats to `0` and mark its lazy flag; otherwise push down the pending flag and recurse. Each `Place` is $O(\log N)$. ### Query (leftmost start of a free run of length $\ge k$) If the root's `best < k`, return $-1$. Otherwise descend, always preferring the **leftmost** valid placement: 1. If the **left** child contains a free run of length $\ge k$ (`left.best >= k`), recurse into the left child. 2. Else if the run can **straddle** the boundary — `left.suf + right.pref >= k` — the leftmost start sits inside the left child's suffix: $s = (\text{mid} - \text{left.suf} + 1)$ (1-indexed), and we return it directly. 3. Else recurse into the **right** child. Because we check left and the straddle before right, the first valid start found is the leftmost. Each query is $O(\log N)$. ### Implementation (sketch) ```python import sys class Node: __slots__ = ('best', 'pref', 'suf', 'assign') def __init__(self): self.best = self.pref = self.suf = 0 self.assign = False # pending "set occupied" class SegTree: def __init__(self, n): self.n = n self.t = [Node() for _ in range(4 * n)] self._build(1, 1, n) def _build(self, node, lo, hi): nd = self.t[node] if lo == hi: nd.best = nd.pref = nd.suf = 1 # all cells start free return mid = (lo + hi) // 2 self._build(2 * node, lo, mid) self._build(2 * node + 1, mid + 1, hi) self._pull(node, lo, hi) def _pull(self, node, lo, hi): mid = (lo + hi) // 2 L, R, nd = self.t[2 * node], self.t[2 * node + 1], self.t[node] llen, rlen = mid - lo + 1, hi - mid nd.best = max(L.best, R.best, L.suf + R.pref) nd.pref = L.pref + (R.pref if L.pref == llen else 0) nd.suf = R.suf + (L.suf if R.suf == rlen else 0) def _apply_occupied(self, node): nd = self.t[node] nd.best = nd.pref = nd.suf = 0 nd.assign = True def _push(self, node): if self.t[node].assign: self._apply_occupied(2 * node) self._apply_occupied(2 * node + 1) self.t[node].assign = False def place(self, node, lo, hi, l, r): if r < lo or hi < l: return if l <= lo and hi <= r: self._apply_occupied(node) return self._push(node) mid = (lo + hi) // 2 self.place(2 * node, lo, mid, l, r) self.place(2 * node + 1, mid + 1, hi, l, r) self._pull(node, lo, hi) def query(self, k): if self.t[1].best < k: return -1 node, lo, hi = 1, 1, self.n while lo != hi: self._push(node) mid = (lo + hi) // 2 L, R = self.t[2 * node], self.t[2 * node + 1] if L.best >= k: # leftmost run fits entirely in left node, hi = 2 * node, mid elif L.suf + R.pref >= k: # run straddles the boundary return mid - L.suf + 1 else: # must be in the right child node, lo = 2 * node + 1, mid + 1 return lo # single free cell, k == 1 ``` Driver: build `SegTree(N)`, then for each op call `st.place(1, 1, N, l, r)` or print `st.query(k)`. ### Correctness - The merge rule maintains the invariant that `best/pref/suf` exactly describe the free runs of each node's range; the straddle term is what makes cross-boundary runs visible. - `Place` only ever marks cells occupied, so a single lazy `assign` (no "set free") is sound and idempotent — re-placing an occupied range just re-zeros already-zero stats. - The descent returns the leftmost start because at every node it exhausts left-then-straddle before going right; the straddle start $\text{mid} - L.\text{suf} + 1$ is the earliest position whose suffix run reaches length $k$. ### Edge cases - `k > N` or no free run of length $k$ → root `best < k` → returns $-1$. - `Place` with $l > r$ shouldn't occur given well-formed input; if it can, guard it. - `k = 1` resolves at a leaf and returns that position. ### Complexity Build $O(N)$, each `Place` and `Query` $O(\log N)$, so total $O((N + Q)\log N)$ time and $O(N)$ space — meeting the target. --- ## Summary table | Part | Technique | Time | Space | |------|-----------|------|-------| | 1 | Hash-map frequency + $\binom{c}{2}$ | $O(n)$ | $O(n)$ | | 2 | Mark-all → remove → per-column gravity, looped | $O(R^2C^2)$ worst (tiny for $R,C\le50$) | $O(RC)$ | | 3 | Single $O(n^2)$ diagonal-membership scan | $O(n^2)$ | $O(1)$ | | 4 | Segment tree (best/pref/suf) + lazy range-assign + guided descent | $O((N+Q)\log N)$ | $O(N)$ | ### Notes on the follow-ups - **Part 1 windowed ($j - i \le D$)**: slide a window of size $D$; as index $j$ enters, add `count[nums[j]]` (occurrences currently in the window) to the answer, then insert; when an index leaves the left edge, decrement its count. $O(n)$ with a hash map keyed by value. - **Part 2 with diagonals**: add two more marking passes along the two diagonal directions ($i+j$ constant and $i-j$ constant); the mark-then-remove discipline and the $O(R^2C^2)$ bound are unchanged. - **Part 4 with `Erase l r`**: add a second lazy state ("set free") alongside "set occupied"; lazy values must be ordered/overwritten correctly (a newer assignment replaces an older pending one of either kind), and leaves reset to `best=pref=suf=1`. Each op stays $O(\log N)$.