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}.

Check if each prefix forms 1..k permutation

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].

Hints

  1. Sorting each prefix is O(n^2 log n) overall — too slow. Look for an O(n) invariant you can maintain while scanning once.
  2. 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}?
  3. 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.

Loading coding console...