1920. Build Array from Permutation

EasyView on LeetCode

Array Simulation

Time: O(n)

Space: O(1)

Problem Overview

The input is a permutation of indices 0..n-1.

Intuition

The input is a permutation of indices 0..n-1. The answer at position i is the value found by following the permutation once: nums[nums[i]]. This is a direct array lookup — no sorting or modification of the source array required.

Algorithm

1Create a new array ans of length n.
2For each index i from 0 to n-1, set ans[i] = nums[nums[i]].
3Return ans without mutating nums (unless the problem allows in-place tricks).

Example Walkthrough

Input: nums = [0,2,1,5,3,4]

1.ans[0] = nums[nums[0]] = nums[0] = 0.
2.ans[1] = nums[nums[1]] = nums[2] = 1.
3.ans[2] = nums[nums[2]] = nums[1] = 2.
4.Continue similarly for remaining indices.

Output: [0,1,2,4,5,3]

Common Pitfalls

•Use a new output array — overwriting nums while reading breaks double lookups.
•Indices are 0-based; nums[i] is always a valid index because input is a permutation.
•O(n) time and O(n) space is optimal for this definition.

1920.cs

// Approach: Encode new and old values into same cell using modular arithmetic; decode in second pass.
// Time: O(n) Space: O(1)

public class Solution
{
    public int[] BuildArray(int[] nums)
    {
        int n = nums.Length;

        for (int i = 0; i < n; i++)
        {
            int val = nums[i];              // original value
            int nextVal = nums[val] % n;    // get nums[nums[i]], safely
            nums[i] = val + n * nextVal;    // encode both values
        }

        for (int i = 0; i < n; i++)
            nums[i] /= n;  // retrieve the final answer

        return nums;
    }
}

Was this solution helpful?