Katkat
Back

Check if each prefix forms 1..k permutation

UberSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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), 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).