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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Check if each prefix forms 1..k permutation

Quick Overview

Example

Constraints

Comments (0)