How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Check if each prefix forms 1..k permutation

Q: Check if each prefix forms 1..k permutation

This question evaluates algorithmic thinking and understanding of permutations and prefix invariants, measuring the ability to recognize when the first k elements of a permutation can form the set {1..k}.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given an integer array `arr` of length `n` that is a permutation of the numbers `1..n` (each number appears exactly once), but in arbitrary order. For each `k` from `1` to `n`, consider the prefix subarray `arr[0..k-1]` (the first `k` elements). Determine whether these `k` elements can be rearranged to become exactly `[1, 2, ..., k]`. Return a binary array `res` of length `n` where: - `res[k-1] = 1` if `arr[0..k-1]` can be rearranged into `[1..k]` - `res[k-1] = 0` otherwise ### Example Input: `arr = [5, 3, 1, 2, 4]` Prefixes: - `k=1`: `[5]` cannot be `[1]` → `0` - `k=2`: `[5,3]` cannot be `[1,2]` → `0` - ... (If instead using the intended example semantics that output is all ones, clarify whether the window is a *sliding window* of size `k` over the array, or specifically the *prefix* of length `k`.) ### Constraints - `1 <= n <= 2e5` (or similar) - `arr` is a permutation of `1..n` Implement an efficient algorithm (better than checking/sorting each prefix independently).

Quick Answer: This question evaluates algorithmic thinking and understanding of permutations and prefix invariants, measuring the ability to recognize when the first k elements of a permutation can form the set {1..k}.

You are given an integer array `arr` of length `n` that is a permutation of the numbers `1..n` (each number appears exactly once), in arbitrary order. For each `k` from `1` to `n`, consider the prefix `arr[0..k-1]` (the first `k` elements). Determine whether those `k` elements can be rearranged into exactly `[1, 2, ..., k]`. Return a binary array `res` of length `n` where `res[k-1] = 1` if `arr[0..k-1]` is a permutation of `[1..k]`, and `0` otherwise. **Key idea:** Because `arr` is a permutation of `1..n`, the first `k` elements are always `k` distinct values drawn from `1..n`. They are exactly `{1, 2, ..., k}` if and only if their maximum equals `k`. So maintain a running maximum as you scan left to right; emit `1` whenever `running_max == k`, else `0`. This is O(n) time and O(1) extra space (besides the output). **Example:** `arr = [5, 3, 1, 2, 4]` → `res = [0, 0, 0, 0, 1]`. Only the full prefix of length 5 is a permutation of `[1..5]`; the running max only equals the prefix length at the very end.

Constraints

1 <= n <= 2 * 10^5
arr is a permutation of the integers 1..n (each appears exactly once)

Examples

Input: ([5, 3, 1, 2, 4],)

Expected Output: [0, 0, 0, 0, 1]

Explanation: Running max after each step: 5,5,5,5,5; prefix lengths 1,2,3,4,5. Only k=5 has running_max==k, so only the full array is a permutation of [1..5].

Input: ([1, 2, 3, 4, 5],)

Expected Output: [1, 1, 1, 1, 1]

Explanation: Already sorted; the running max equals the prefix length at every step, so every prefix is a permutation of [1..k].

Input: ([1],)

Expected Output: [1]

Explanation: Single element [1] is the permutation of [1].

Input: ([2, 1],)

Expected Output: [0, 1]

Explanation: k=1: max=2 != 1 → 0. k=2: max=2 == 2 → 1 ({2,1} = {1,2}).

Input: ([1, 3, 2, 5, 4],)

Expected Output: [1, 0, 1, 0, 1]

Explanation: Running max: 1,3,3,5,5 vs k=1,2,3,4,5. Equal at k=1 (=>1), k=3 (=>1), k=5 (=>1); not at k=2 or k=4.

Input: ([3, 1, 2, 4],)

Expected Output: [0, 0, 1, 1]

Explanation: Running max: 3,3,3,4 vs k=1,2,3,4. First prefix that is exactly {1..k} appears at k=3 ({3,1,2}={1,2,3}), then k=4.

Hints

Sorting each prefix is O(n^2 log n) overall — too slow. Look for an O(n) invariant you can maintain while scanning once.
The first k elements are always k distinct values from 1..n. What single statistic of those values tells you whether they are exactly {1..k}?
If the maximum of the first k elements equals k, then k distinct values all <= k must be precisely 1..k. Track a running maximum and compare it to the current prefix length.

Quick Overview

This question evaluates algorithmic thinking and understanding of permutations and prefix invariants, measuring the ability to recognize when the first k elements of a permutation can form the set {1..k}.