Check an array is a permutation of 0 to n-1

A valid permutation of 0..n-1 has two properties: every value lies in
[0, n-1], and no value appears twice. With n slots and n values, those two
together force every value to appear exactly once (pigeonhole). So the job is to
detect an out-of-range value or a duplicate.

Brute force. Put the values in a set and check each is in range and the set
size is n. That is O(n) time but O(n) extra space, which the constraint rules
out. Sorting and checking nums[i] == i is O(1) extra space (with an in-place
sort) but O(n log n) time.

Optimal: cyclic placement (in-place). Value v belongs at index v. Walk
i from left to right. While nums[i] != i:

• if nums[i] is outside [0, n-1], return False;
• let v = nums[i]; if nums[v] == v, slot v is already taken by a correct
  copy, so v is a duplicate: return False;
• otherwise swap nums[i] and nums[v]. Now v sits at home for good.

If the walk finishes, every index holds its own value, so the array is a
permutation.

Why it is O(n): each swap puts one value into its home slot, and a value at
home is never moved again. So there are at most n swaps in total across all
iterations of the inner loop, even though the loop is nested.

Invariants:

• Once nums[j] == j, slot j never changes.
• After the outer loop passes index i, nums[0..i] all equal their indices.

Alternative: index marking. Encode "seen" at index v without losing the
original value, e.g. add n to nums[v] (the original is nums[v] % n after
range checking). A second hit on an already-marked slot is a duplicate. Negation
does not work directly because 0 has no negative form; the +n offset avoids
that. Both are O(n) time and O(1) extra space; cyclic placement is easier to get
right under pressure, and the marking version can restore the input afterwards.

from typing import List


def is_zero_based_permutation(nums: List[int]) -> bool:
    """Return True if nums is a permutation of [0, 1, ..., n-1].

    Uses O(1) extra space. Reorders nums in place.
    """
    n = len(nums)
    for i in range(n):
        while nums[i] != i:
            v = nums[i]
            if v < 0 or v >= n:
                return False          # out of range
            if nums[v] == v:
                return False          # v already at home: duplicate
            nums[i], nums[v] = nums[v], v
    return True


def is_zero_based_permutation_marking(nums: List[int]) -> bool:
    """Same check by index marking. Restores nums before returning."""
    n = len(nums)
    ok = True
    for x in nums:
        if x < 0 or x >= n:
            return False              # nothing marked yet, nums untouched
    for i in range(n):
        v = nums[i] % n               # original value at i
        if nums[v] >= n:              # slot v already marked
            ok = False
            break
        nums[v] += n
    for i in range(n):                # undo the marks
        if nums[i] >= n:
            nums[i] -= n
    return ok


if __name__ == "__main__":
    cases = [
        ([], True),
        ([0], True),
        ([1], False),
        ([2, 0, 1], True),
        ([3, 1, 0, 2], True),
        ([0, 0, 1], False),
        ([1, 1], False),
        ([0, 1, 3], False),
        ([-1, 0, 1], False),
        ([4, 3, 2, 1, 0], True),
        ([1, 2, 2, 0], False),
    ]
    for arr, want in cases:
        assert is_zero_based_permutation(list(arr)) == want, arr
        copy = list(arr)
        assert is_zero_based_permutation_marking(copy) == want, arr
        assert copy == arr, "marking version must restore input"
    print("all tests pass")

• Cyclic placement: O(n) time (at most n swaps plus n outer steps), O(1)
  extra space. The input is reordered (it ends sorted when the answer is True).
• Index marking: O(n) time over three passes, O(1) extra space, input restored.
  Values grow up to 2n - 1, which matters in fixed-width languages only when
  n is near the integer limit.

• [] → True (empty array is the permutation of nothing)
• [0] → True
• [1] → False (out of range)
• [2, 0, 1] → True
• [3, 1, 0, 2] → True
• [4, 3, 2, 1, 0] → True (reversed)
• [0, 0, 1] → False (duplicate 0, missing 2)
• [1, 1] → False (duplicate, missing 0)
• [1, 2, 2, 0] → False (duplicate 2, missing 3)
• [0, 1, 3] → False (3 is out of range)
• [-1, 0, 1] → False (negative)

• The input must not be modified. Then O(1) space with O(n) time is not
  generally possible. Options: the marking version that restores the array
  (still writes, but leaves it unchanged); or sum and sum-of-squares checks
  plus range checks, which are a probabilistic shortcut with overflow concerns
  and can be fooled; or accept O(n) space with a bitset (n bits, not n ints).
• Permutation of 1..n or of [lo, lo + n - 1]. Shift each value by the
  base before using it as an index; the algorithm is unchanged.
• Report what is wrong. Return the first duplicate and the missing values.
  After cyclic placement (skipping instead of returning on bad values), any
  index i with nums[i] != i is a missing value, and the value sitting there
  is a duplicate or out of range.
• Streamed input too large for memory. You cannot place in place. Use a
  bitset of size n on disk or in memory (n/8 bytes), or shard by value range
  and check each shard's count and uniqueness.
• Find the smallest missing non-negative integer. The same placement pass
  answers it: the first i with nums[i] != i (LeetCode "First Missing
  Positive" is the 1-based version).

Mid-level (L4)

• States the two conditions (in range, no duplicates) and why they suffice.
• Gives the set solution, then reaches an O(1)-space approach with hints.
• Handles empty array, out-of-range and negative values without crashing.

Senior (L5)

• Writes cyclic placement cleanly and argues the O(n) bound via "each swap
  homes one value forever".
• Spots the negation-marking bug with value 0 and fixes it with an offset.
• Calls out that the input is mutated and offers a restoring variant.

Staff (L6+)

• Discusses when mutating caller data is acceptable (API contract, aliasing,
  concurrency) and the read-only lower-bound trade-off.
• Notes overflow risk of the offset trick and of sum-based shortcuts in
  fixed-width integers.
• Generalizes to diagnostics (which values missing or duplicated) and to
  inputs that do not fit in memory.