Solve 12 coding interview problems
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Below are multiple independent coding problems.
---
## Problem 1: Reduce an integer to 0 with \(\pm 2^i\)
You are given a positive integer \(n\). In one operation you may replace \(n\) with \(n + 2^i\) or \(n - 2^i\) for any integer \(i \ge 0\).
**Task:** Return the minimum number of operations needed to make \(n = 0\).
**Constraints (typical):** \(1 \le n \le 10^{18}\).
---
## Problem 2: Shortest subarray with at least \(k\) distinct integers
You are given an integer array `arr` of length \(n\) and an integer \(k\).
A subarray is **good** if it contains **at least \(k\)** distinct values.
**Task:** Return the length of the shortest good subarray. If no such subarray exists, return `-1`.
**Constraints (typical):** \(1 \le n \le 2\times 10^5\).
---
## Problem 3: Apply the first valid discount to the right
You are given an array `prices`.
For each index `i`, define the discount as the first index `j > i` such that `prices[j] <= prices[i]`.
- If such `j` exists: `final[i] = prices[i] - prices[j]`
- Otherwise: `final[i] = prices[i]` (sold at full price)
**Task:** Output:
1. The **sum** of all final prices.
2. The list of **0-based indices** that are sold at full price, in increasing order.
**Constraints (typical):** \(1 \le n \le 2\times 10^5\).
---
## Problem 4: Max-score jump game with special prime jumps
You are given an integer array `arr` of length \(n\). You start at index `0` and must end at index `n-1`.
From index `i`, you may jump to:
- `i + 1`, or
- `i + p` where `p` is a **prime number** and `p % 10 == 3` (e.g., 3, 13, 23, 43, ...), and `i + p < n`.
Your score is the sum of `arr` values on all visited indices (including start and end).
**Task:** Return the maximum achievable score when reaching `n-1`. If `n-1` is unreachable, return `-1`.
**Constraints (typical):** \(1 \le n \le 2\times 10^5\), `arr[i]` may be negative.
---
## Problem 5: Count ancestor endpoints whose path can be permuted into a palindrome
You are given a rooted tree with nodes `0..n-1` (root is node `0`). Each node has a lowercase letter.
Input is provided as:
- `treeNodes = n`
- `nodes`: a char array of length `n`, where `nodes[i]` is the character on node `i`
- `nodeFrom`, `nodeTo`: arrays of length `n-1` describing directed parent→child edges (`nodeFrom[i] -> nodeTo[i]`), forming a tree
- `queries`: array of start nodes
For each query start node `u`:
- Consider all endpoints `v` on the path from `u` up to the root `0` (i.e., `v` can be `u`, its parent, ..., `0`).
- Let the multiset of characters on the path `u -> ... -> v` (inclusive) be collected.
- This path is counted if its characters can be **rearranged** into a palindrome (i.e., at most one character has an odd frequency).
**Task:** For each query `u`, return how many such endpoints `v` exist.
**Constraints (typical):** \(n, q \le 2\times 10^5\).
---
## Problem 6: Maximize pipeline throughput under a scaling budget
You have \(n\) services connected in a pipeline. The pipeline throughput is:
\[
T = \min_i throughput[i]
\]
You may scale service `i` any number of times. Each scaling:
- increases `throughput[i]` by `1`
- costs `scale_cost[i]`
Given integer `budget`, **total scaling cost** must be \(\le budget\).
**Task:** Return the maximum achievable pipeline throughput `T`.
**Constraints (typical):** \(n \le 2\times 10^5\), values up to \(10^{18}\).
---
## Problem 7: Elevator-then-stairs with energy-dependent stair time
You must go from floor `0` to floor `N`.
You may take the elevator first from floor `0` to floor `x` (choose `x` once, `0 <= x <= N`).
- For each elevator floor ascended: gain `e1` energy and spend `t1` time.
- After elevator: your energy is `E = x * e1`.
Then you must climb the remaining `N - x` floors using stairs. For each stair floor:
- At the **start** of the floor, if current energy is `E`, the time spent is `ceil(c / E)`.
- Then you spend `e2` energy: `E := E - e2`.
- Energy may never become negative; if `E < 0` at any step, that choice of `x` is invalid.
**Task:** Choose `x` to minimize total time. If no `x` is feasible, return `-1`.
**Constraints (typical):** \(1 \le N \le 10^6\), parameters are positive integers.
---
## Problem 8: Assign tasks to two people with exactly \(k\) tasks for person A
You have `n` tasks. If task `i` is done by:
- person A: reward `reward1[i]`
- person B: reward `reward2[i]`
Each task must be assigned to exactly one person. Person A must do **exactly `k` tasks**.
**Task:** Return the maximum possible total reward.
**Constraints (typical):** \(n \le 2000\), \(0 \le k \le n\).
---
## Problem 9: Score from each start index with energy thresholds
You are given:
- `layers[0..n-1]`: energy cost to attempt/pass level `j`
- `energyReq[0..n-1]`: minimum remaining energy needed *after paying the cost* to pass level `j`
- initial energy `K`
Starting from index `i`:
- Set `E = K`.
- For `j = i..n-1`:
1. Pay the level cost: `E := E - layers[j]`. If `E < 0`, stop.
2. If `E >= energyReq[j]`, you pass and gain 1 point; otherwise stop (cannot proceed further).
**Task:** Return an array `score` of length `n` where `score[i]` is the number of points you can earn starting at level `i`.
**Note:** An \(O(n^2)\) solution will time out; design a faster approach.
---
## Problem 10: Buy the maximum number of consecutive items per query
You are given `prices[0..n-1]` (positive integers). Each query provides:
- `pos` (1-based starting index)
- `amount` (budget)
From index `start = pos - 1`, you can buy items consecutively to the right while the running sum does not exceed `amount`.
**Task:** For each query, return the maximum number of items you can buy.
**Constraints (typical):** \(n, q \le 2\times 10^5\).
---
## Problem 11: Minimum edge reversals so every node can reach the chosen root
You are given `n` nodes and `n-1` directed edges `edges[i] = [a, b]` meaning `a -> b`. Ignoring direction, the graph is a tree.
For each node `r` considered as the root, you may reverse any subset of edges.
**Task:** Compute `res[r]` = the minimum number of edge reversals required so that **every node has a directed path to `r`** (equivalently, all edges point toward `r` along the tree). Return `res` for all `r`.
**Constraints (typical):** \(n \le 2\times 10^5\).
---
## Problem 12: For each \(w\), do values \(1..w\) occupy a contiguous block?
You are given a permutation `perm[0..n-1]` containing each integer from `1` to `n` exactly once.
For each window size \(w = 1..n\), define `ans[w] = 1` if the positions of the numbers `{1,2,...,w}` in `perm` form a contiguous subarray (in any order). Otherwise, `ans[w] = 0`.
Equivalently, let `pos[x]` be the index where value `x` appears. Then `ans[w] = 1` iff:
\[
\max_{1\le x\le w} pos[x] - \min_{1\le x\le w} pos[x] + 1 = w.
\]
**Task:** Return `ans[1..n]`.
**Constraints (typical):** \(n \le 2\times 10^5\).
Overview: This multi-problem set evaluates broad algorithmic problem-solving skills, including bitwise reasoning, sliding-window and frequency analysis, stack/monotonic patterns, graph/DP reasoning with constrained jumps, and tree-path parity techniques.
Part 1: Reduce an Integer to 0 with +/- Powers of Two
You are given a non-negative integer n. In one operation, you may replace n with n + 2^i or n - 2^i for any integer i >= 0. Return the minimum number of operations needed to make n equal to 0.
Constraints
- 0 <= n <= 10^18
Examples
Input: (0,)
Expected Output: 0
Explanation: Already at 0, so no operations are needed.
Input: (1,)
Expected Output: 1
Explanation: Use -1 once.
Hints
- If n is even, think about factoring out a power of 2.
- If n is odd, your first move must make it even: compare n - 1 and n + 1.
Part 2: Shortest Subarray with At Least k Distinct Integers
Given an integer array arr and an integer k, find the length of the shortest contiguous subarray that contains at least k distinct values. If no such subarray exists, return -1.
Constraints
- 0 <= len(arr) <= 2 * 10^5
- 1 <= k <= 2 * 10^5
Examples
Input: ([], 1)
Expected Output: -1
Explanation: There is no subarray at all.
Input: ([1], 1)
Expected Output: 1
Explanation: The single element subarray already has 1 distinct value.
Hints
- A sliding window can track how many distinct values are inside the current range.
- Once a window has at least k distinct numbers, try shrinking it from the left.
Part 3: Apply the First Valid Discount to the Right
For each price at index i, find the first index j > i such that prices[j] <= prices[i]. If such j exists, the final price is prices[i] - prices[j]; otherwise, the item is sold at full price. Return both the sum of all final prices and the list of 0-based indices sold at full price.
Constraints
- 0 <= len(prices) <= 2 * 10^5
- 1 <= prices[i] <= 10^9
Examples
Input: ([],)
Expected Output: (0, [])
Explanation: No items means total 0 and no full-price indices.
Input: ([8, 4, 6, 2, 3],)
Expected Output: (15, [3, 4])
Explanation: Final prices are [4, 2, 4, 2, 3].
Hints
- The phrase first smaller-or-equal value to the right suggests a monotonic stack.
- When a new price resolves discounts for earlier items, update the total immediately.
Part 4: Max-Score Jump Game with Special Prime Jumps
You are given an integer array arr. Start at index 0 and reach index n - 1. From index i, you may jump to i + 1, or to i + p where p is a prime number ending in digit 3 and i + p < n. Your score is the sum of arr values at all visited indices, including the start and end. Return the maximum achievable score. In this version, n is small enough for dynamic programming over all valid jump lengths.
Constraints
- 0 <= len(arr) <= 5000
- -10^9 <= arr[i] <= 10^9
Examples
Input: ([],)
Expected Output: -1
Explanation: There is no start or end index.
Input: ([7],)
Expected Output: 7
Explanation: Start and end are the same index.
Approach
We compute the best score to land on each index with a 1‑D DP.
Setup. Handle the two base cases first: an empty array returns -1 (a sentinel — there's no path), and a single element returns arr[0] (start and end coincide).
Which jump lengths are legal. A jump of length p is allowed only when p is prime and its last digit is 3. We find every such p < n once up front:
- Run a sieve of Eratosthenes over 0..n-1.
- Keep the primes with p % 10 == 3, in ascending order, as special_primes (e.g. 3, 13, 23, 43, …).
DP recurrence. dp[i] is the maximum total score over any valid path from index 0 to index i, including arr[i]. Since you reach index i either by a +1 step from i-1 or by a special‑prime jump from i-p:
The code seeds best_prev = dp[i-1], then scans special_primes; because they're sorted, it breaks as soon as p > i (no further prime can reach index i). dp[0] = arr[0], and the answer is dp[n-1].
Why it's correct. Every path to i makes a last move from some predecessor i-1 or i-p; the recurrence takes the max over exactly those predecessors, and each dp[j] is already optimal (indices processed left to right). Negative arr values are handled naturally — we maximize, so a costly detour is taken only when it beats the +1 chain (see the test where jumping 0→3 over -100 scores 15).
Time complexity: O(n · π₃(n)) where π₃(n) is the number of primes < n ending in digit 3 — i.e. the DP does an inner scan over those primes per index. By prime density that is about O(n² / log n) in the worst case; the sieve adds O(n log log n), which is dominated.
Space complexity: O(n): the sieve is O(n), the `dp` array is O(n), and `special_primes` holds O(n / log n) entries — all linear or sublinear in n.
Hints
- Precompute all allowed jump lengths less than n with a sieve.
- Let dp[i] be the best score for reaching index i.
Part 5: Count Ancestor Endpoints Whose Path Can Be Rearranged into a Palindrome
You are given a rooted tree with root 0. Each node has a lowercase letter. For each query node u, count how many ancestor endpoints v on the path from u up to 0 make the path u -> ... -> v have character counts that can be rearranged into a palindrome.
Constraints
- 1 <= treeNodes <= 2 * 10^5
- 1 <= len(queries) <= 2 * 10^5
- nodes[i] is a lowercase English letter
Examples
Input: (5, ['a', 'b', 'a', 'c', 'b'], [0, 0, 1, 1], [1, 2, 3, 4], [4, 3, 2, 0])
Expected Output: [3, 1, 2, 1]
Explanation: For node 4, all three ancestor endpoints 4, 1, and 0 are valid.
Input: (4, ['a', 'b', 'a', 'b'], [0, 1, 2], [1, 2, 3], [3, 2])
Expected Output: [3, 2]
Explanation: On the chain, node 3 has three valid ancestor endpoints.
Approach
Idea: XOR parity masks + DFS frequency map. A path's characters can be rearranged into a palindrome iff at most one letter occurs an odd number of times. So we track, for each node, a 26‑bit mask where bit c is the parity of how many times letter c appears on the path from the root down to that node. bits[u] = 1 << (nodes[u]-'a').
For two nodes u and an ancestor's prefix p, the parity of the segment between them is current ^ p. The segment is palindrome‑rearrangeable iff current ^ p has 0 or exactly 1 bit set.
The DFS. children is built from the edges, then an explicit stack does an iterative DFS with two states per node:
- state 0 (enter u): compute current = mask ^ bits[u] (parity for root→u). The answer for u is the number of stored prefixes p of its ancestors (including a virtual root‑parent seeded as freq[0]=1) with current ^ p having ≤1 bit set. That's freq[current] (zero odd bits → full palindrome) plus, for each of 26 letters b, freq[current ^ (1<<b)] (exactly that one letter odd). We then add current to freq and push a state‑1 marker plus all children.
- state 1 (leave u): decrement/remove current from freq so only the current root‑to‑node path's prefixes remain visible — this is the key that restricts matches to genuine ancestors.
answers[u] is filled for every node; the final line maps each query node to its precomputed answer.
Correctness: freq holds exactly the prefix masks of the live ancestor chain at any moment, so each enter‑step counts precisely the ancestor endpoints forming a palindrome‑rearrangeable path with u.
Time complexity: O(26 * n + q)
Space complexity: O(n)
Hints
- A multiset can be rearranged into a palindrome iff at most one character has odd frequency.
- Track parity with a 26-bit mask and count ancestor-prefix masks along the current DFS path.
Part 6: Maximize Pipeline Throughput Under a Scaling Budget
A pipeline has n services, and the overall throughput is the minimum value in the throughput array. You may increase throughput[i] by 1 any number of times, and each unit increase costs scale_cost[i]. Given a total budget, return the maximum achievable pipeline throughput.
Constraints
- 1 <= len(throughput) <= 2 * 10^5
- 1 <= throughput[i], scale_cost[i], budget <= 10^18
Examples
Input: ([4, 2, 7], [3, 1, 2], 5)
Expected Output: 4
Input: ([1, 1, 1], [2, 2, 2], 6)
Expected Output: 2
Approach
Binary search on the answer. The pipeline throughput equals the minimum of the array, so we want the largest target value T such that raising every service up to T (only services below T need work) costs no more than budget.
Why binary search works: feasibility is monotonic — if target T is affordable, any T' < T is also affordable (it needs ≤ as much spending). So the affordable targets form a contiguous range [min, answer], and we binary-search its right edge.
Search bounds:
- low = min(throughput) — always feasible (cost 0, nothing is below it).
- high = max(throughput) + budget // min(scale_cost) + 1 — a provably-infeasible upper bound. min(scale_cost) is the cheapest per-unit price anywhere, so even lifting a single service from the current maximum can't exceed budget // min(scale_cost) extra units; +1 makes high strictly unreachable.
Feasibility check can(target): sum (target - t) * c over every service with t < target, short-circuiting to False the moment the running total exceeds budget. This is the exact minimum cost to make target the new floor (you never touch services already ≥ target).
The loop uses the low + 1 < high invariant where low stays feasible and high stays infeasible; mid is tested and replaces the matching side until they're adjacent, leaving low as the maximum feasible target. Python's arbitrary-precision ints handle the 10^18 magnitudes safely.
Time complexity: O(n log M)
Space complexity: O(1)
Hints
- If you can achieve throughput T, then every smaller target is also achievable.
- Binary search the answer and write a function that computes the cost of reaching a target minimum.
Part 7: Elevator-Then-Stairs with Energy-Dependent Stair Time
You must go from floor 0 to floor N. First, choose a single elevator ride from floor 0 to floor x. Each elevator floor gives e1 energy and costs t1 time. Then climb the remaining floors by stairs. For each stair floor, if your current energy is E, the time spent is ceil(c / E), then your energy decreases by e2. Choose x to minimize total time. In this version, N is small enough to try every split.
Constraints
- 0 <= N <= 4000
- 1 <= e1, t1, e2, c <= 10^9
Examples
Input: (0, 5, 2, 3, 10)
Expected Output: 0
Explanation: No movement is required.
Input: (3, 5, 2, 2, 10)
Expected Output: 5
Explanation: Best choice is x = 2, giving total time 4 + 1 = 5.
Hints
- Try every possible elevator stop x from 0 to N.
- A choice is feasible only if the starting elevator energy is enough to pay for all remaining stair floors.
Part 8: Assign Tasks to Two People with Exactly k Tasks for Person A
There are n tasks. If task i is assigned to person A, you earn reward1[i]. If assigned to person B, you earn reward2[i]. Every task must be assigned to exactly one person, and person A must receive exactly k tasks. Return the maximum total reward.
Constraints
- 1 <= len(reward1) == len(reward2) <= 2000
- 0 <= k <= n
- 0 <= reward1[i], reward2[i] <= 10^9
Examples
Input: ([8, 7, 15], [5, 10, 5], 2)
Expected Output: 33
Explanation: Choose tasks 0 and 2 for person A.
Input: ([3, 1, 2], [4, 5, 6], 0)
Expected Output: 15
Explanation: All tasks go to person B.
Hints
- Start by assigning every task to person B.
- Switching task i from B to A changes the total by reward1[i] - reward2[i].
Part 9: Score from Each Start Index with Energy Thresholds
You are given arrays layers and energyReq, and an initial energy K. Starting from index i, you process levels from i to the end. For each level j, first subtract layers[j] from energy. If energy becomes negative, you stop. Otherwise, if the remaining energy is at least energyReq[j], you gain 1 point and continue; if not, you stop. Return score[i] for every start index i.
Constraints
- 0 <= len(layers) == len(energyReq) <= 2 * 10^5
- 0 <= layers[i], energyReq[i], K <= 10^18
Examples
Input: ([], [], 10)
Expected Output: []
Explanation: No levels means no scores.
Input: ([2, 1, 3], [1, 2, 0], 4)
Expected Output: [1, 2, 1]
Explanation: Starting at index 1 lets you pass levels 1 and 2.
Approach
Reframing the stop rule. Start at i with energy K. After processing levels i..j, the energy is K - (layers[i] + ... + layers[j]). You stop at level j if energy went negative (< 0) or if it can no longer meet the requirement (< energyReq[j]). Because energyReq[j] >= 0, both cases collapse into a single test: stop at j iff
K - sum(layers[i..j]) < energyReq[j].
need[j] := pref[j+1] + max(0, energyReq[j]) - K > pref[i].
So score[i] is j - i, where j is the first index >= i with need[j] > pref[i]; if no such j exists, the answer is n - i (the run reaches the end).
Segment tree for "first index above threshold". The code builds a max-segment-tree over need (padded to a power of two with -inf). For each i, first_greater(left=i, threshold=pref[i]) walks the tree:
- Prune any node fully left of i or whose subtree max is <= threshold (return n).
- At a leaf, return its index.
- Otherwise descend left first, and only go right if the left half found nothing.
This returns the smallest qualifying index, so ans[i] = (n - i) when it returns n, else j - i. Each query touches O(log n) nodes, the build is O(n), giving the bound below. The empty-array case returns [] up front.
Time complexity: O(n log n)
Space complexity: O(n)
Hints
- Rewrite the pass condition using prefix sums.
- For each i, you need the first j >= i where a precomputed threshold exceeds prefix[i].
Part 10: Buy the Maximum Number of Consecutive Items per Query
You are given positive prices and multiple queries. Each query gives a 1-based starting position pos and a budget amount. Starting from pos, buy consecutive items to the right while the running total does not exceed the budget. Return the maximum number of items that can be bought for each query.
Constraints
- 0 <= len(prices), len(queries) <= 2 * 10^5
- 1 <= prices[i], amount <= 10^18
Examples
Input: ([2, 1, 3, 2, 4], [(1, 3), (2, 6), (5, 10)])
Expected Output: [2, 3, 1]
Explanation: From position 2 with budget 6, you can buy 1 + 3 + 2.
Input: ([5], [(1, 4), (1, 5)])
Expected Output: [0, 1]
Explanation: The first budget is too small; the second buys exactly one item.
Approach
Approach: prefix sums + binary search.
Since prices are all positive, the cumulative cost of buying items grows strictly as you move right. That means the running total from any start position is monotonically increasing, which is exactly what makes binary search applicable.
Step 1 — build prefix sums. pref[i] holds the sum of the first i prices (pref[0] = 0). So the cost of buying items in the half-open range [start, j) is pref[j] - pref[start].
Step 2 — answer each query. For a query (pos, amount):
- Convert to 0-based: start = pos - 1.
- We want the largest j such that pref[j] - pref[start] <= amount, i.e. pref[j] <= pref[start] + amount. Call that bound target.
- Because pref is sorted (strictly increasing, as prices are positive), bisect_right(pref, target) - 1 returns the rightmost index right with pref[right] <= target.
- The count of items bought is right - start (number of prefix steps taken from start to right).
Why it's correct: right >= start always, because pref[start] <= target so start itself satisfies the bound; thus the answer is never negative. The monotonicity of pref guarantees binary search finds the exact cutoff where the running total would first exceed the budget.
Using a prefix sum lets each query be answered in O(log n) instead of scanning, which matters given up to 2*10^5 queries.
Time complexity: O(n + q log n)
Space complexity: O(n)
Hints
- Because prices are positive, prefix sums are strictly increasing.
- For each query, use binary search on the prefix sum array.
Part 11: Minimum Edge Reversals so Every Node Can Reach the Chosen Root
You are given n nodes and n - 1 directed edges that form a tree if directions are ignored. For every possible root r, compute the minimum number of edge reversals needed so that every node has a directed path to r.
Constraints
- 1 <= n <= 2 * 10^5
- len(edges) == n - 1
Examples
Input: (1, [])
Expected Output: [0]
Explanation: A single node needs no reversals.
Input: (3, [[0, 1], [2, 1]])
Expected Output: [1, 0, 1]
Explanation: Root 1 already has all edges effectively pointing toward it.
Approach
This is a rerooting tree DP that answers all n roots in one linear sweep instead of running a per-root BFS.
Edge encoding. The n-1 directed edges form a tree if directions are ignored. For each original edge a→b we add two undirected half-edges: adj[a] gets (b, 1) and adj[b] gets (a, 0). The weight is the reversal cost of crossing that half-edge toward the root: traversing in the original direction (a→b, weight 1) costs a reversal because we need the edge to point the other way; traversing against it (b→a, weight 0) is free.
Pass 1 — answer for root 0. An iterative DFS from node 0 builds a parent array and a pre-order order. For every tree edge from parent u to child v with half-edge weight w, it adds w to res[0]. That sum is exactly the number of edges that must be reversed so every node can reach node 0.
Pass 2 — reroot. Walking order in pre-order, when the root shifts from u to its child v, only the single u–v edge changes orientation requirement; every other edge's cost is unchanged. So:
If w == 0 the original edge already pointed v→u (good for root u, now wrong for root v) → cost +1; if w == 1 it pointed u→v (a reversal for u, now free for v) → cost -1.
Correctness rests on the tree invariant: moving the root across one edge flips exactly that edge's contribution and leaves all others fixed. The iterative stack also avoids Python recursion limits at n = 2·10^5. The n == 0 guard returns [].
Time complexity: O(n)
Space complexity: O(n)
Hints
- First compute the answer for one root, such as 0.
- When rerooting across an edge, the answer changes by exactly 1 in one direction or the other.
Part 12: For Each w, Do Values 1..w Occupy a Contiguous Block?
You are given a permutation perm of the integers 1 through n. For every w from 1 to n, determine whether the positions of the values 1, 2, ..., w form a contiguous subarray in perm. Return an array of 0/1 answers.
Constraints
- 0 <= len(perm) <= 2 * 10^5
- perm is a permutation of 1..n
Examples
Input: ([],)
Expected Output: []
Input: ([1],)
Expected Output: [1]
Approach
Key insight. A set of distinct positions in an array is contiguous exactly when the span between its smallest and largest position equals the number of positions. For values 1..w, there are exactly w positions, so they form a contiguous block iff maxPos - minPos + 1 == w.
Steps in the code.
1. Invert the permutation. Build pos, where pos[value] is the index of that value in perm (pos[value] = i for each perm[i]). This lets us look up the position of any value in O(1).
2. Sweep w from 1 to n, maintaining a running window. As each new value w is "added," update lo = min position seen so far and hi = max position seen so far among values 1..w. Because we add values one at a time, lo and hi only ever shrink/grow — a simple comparison updates them.
3. Test contiguity in O(1). Append 1 if hi - lo + 1 == w else 0. The w values occupy w distinct positions within the range [lo, hi]; that range has exactly hi - lo + 1 slots, so equality means the slots are fully packed with no gaps — i.e. contiguous.
The empty input short-circuits to [].
Why it's correct. Since perm is a permutation, the values 1..w map to w distinct positions. The minimal range containing all of them is [lo, hi]. They are contiguous iff that range contains no other (larger) values, which happens precisely when its width equals the count, w. No sorting or rescanning is needed because lo/hi carry forward across iterations.
Time complexity: O(n)
Space complexity: O(n)
Hints
- Store the position of each value.
- As w grows from 1 to n, update only the current minimum and maximum position.