Problem Description

You are given a zero-based permutation array called nums. A zero-based permutation means the array contains all distinct integers from 0 to nums.length - 1 (inclusive).

Your task is to build a new array ans of the same length as nums, where each element at position i is constructed using the following rule:

• ans[i] = nums[nums[i]]

In other words, for each index i:

1. First, look at the value stored at nums[i]
2. Use that value as an index to access nums again
3. Store the resulting value in ans[i]

For example, if nums = [0, 2, 1, 5, 3, 4]:

• For i = 0: nums[0] = 0, so ans[0] = nums[0] = 0
• For i = 1: nums[1] = 2, so ans[1] = nums[2] = 1
• For i = 2: nums[2] = 1, so ans[2] = nums[1] = 2
• And so on...

The solution uses a simple list comprehension to iterate through each element num in nums and creates a new list where each element is nums[num]. This directly implements the required transformation ans[i] = nums[nums[i]].

Intuition

The problem asks us to perform a two-step lookup operation for each element. When we see ans[i] = nums[nums[i]], we can think of it as following a pointer chain:

• Start at index i
• Look up the value at that index to get nums[i]
• Use that value as a new index to look up again

Since we're dealing with a zero-based permutation, we know that every value in nums is a valid index (ranging from 0 to nums.length - 1). This guarantees that nums[i] will always be a valid index to access the array again, so we won't run into index out of bounds errors.

The transformation is straightforward - we're essentially using each element as an indirect reference to another element. This is like saying "don't give me the value at position i, give me the value at the position that position i points to."

The most direct approach is to simply iterate through the array and apply this double-lookup operation for each position. We can elegantly express this using a list comprehension: [nums[num] for num in nums]. Here, num represents each value in the original array, and we use it as an index to look up nums[num].

This approach works in a single pass through the array, making it both time and implementation efficient. There's no need for complex logic or additional data structures - we just follow the problem's formula directly.

Solution Approach

The solution uses a direct simulation approach to construct the required array. We iterate through each element in the input array and apply the transformation rule ans[i] = nums[nums[i]].

Implementation Steps:

1. Create a new array: We need to build a new array ans that will store our results. In Python, we can do this efficiently using a list comprehension.

2. Apply the transformation: For each element in the original array:

   • Take the element value (let's call it num)
   • Use this value as an index to access nums[num]
   • Store the result in our new array

The Code Breakdown:

return [nums[num] for num in nums]

This list comprehension does the following:

• for num in nums: Iterates through each element in the input array
• nums[num]: Uses the current element value as an index to look up another value
• [...]: Collects all these looked-up values into a new list

Example Walkthrough:

Let's trace through nums = [0, 2, 1, 5, 3, 4]:

• When num = 0: nums[0] = 0 → add 0 to result
• When num = 2: nums[2] = 1 → add 1 to result
• When num = 1: nums[1] = 2 → add 2 to result
• When num = 5: nums[5] = 4 → add 4 to result
• When num = 3: nums[3] = 5 → add 5 to result
• When num = 4: nums[4] = 3 → add 3 to result

Final result: [0, 1, 2, 4, 5, 3]

Time and Space Complexity:

• Time: O(n) where n is the length of the input array, as we visit each element once
• Space: O(n) for storing the output array (not counting the space for the output as extra space since it's required)

Example Walkthrough

Let's walk through a simple example with nums = [2, 0, 3, 1].

Step 1: Understand what we need to build

• We need to create a new array where ans[i] = nums[nums[i]]
• This means we do a double lookup: first get the value at index i, then use that value as an index

Step 2: Process each index

Let's trace through each position:

Step 3: Build the result array

Following our list comprehension [nums[num] for num in nums]:

• Iterate through values: [2, 0, 3, 1]
• For value 2: get nums[2] = 3
• For value 0: get nums[0] = 2
• For value 3: get nums[3] = 1
• For value 1: get nums[1] = 0

Final Result: ans = [3, 2, 1, 0]

Notice how we're using each element's value as an index to perform another lookup. Since this is a zero-based permutation, every value (0, 1, 2, 3) is guaranteed to be a valid index, so we'll never have an out-of-bounds error.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The list comprehension iterates through each element in nums exactly once, and for each element, it performs a constant-time array access operation nums[num]. Therefore, the total time complexity is linear with respect to the input size.

Space Complexity: O(1) if we exclude the space required for the output array (as is standard practice when analyzing space complexity for problems that require returning a new array). The algorithm uses only a constant amount of extra space for the iteration variable num in the list comprehension. If we include the output array, the space complexity would be O(n) since we're creating a new array of the same size as the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting In-Place Modification

A common mistake is trying to modify the array in-place, which leads to incorrect results because you're changing values that you still need to reference later.

Incorrect Approach:

def buildArray(self, nums: List[int]) -> List[int]:
    for i in range(len(nums)):
        nums[i] = nums[nums[i]]  # WRONG! Modifies values we still need
    return nums

Why it fails: When you update nums[0], you lose the original value that might be needed when processing later indices. For example, if nums[3] needs to reference the original nums[0], it will get the modified value instead.

Solution: Always create a new array for the result, or if you must modify in-place for space optimization, use a clever encoding technique (see advanced solution below).

2. Index Out of Bounds Concerns

While the problem guarantees a valid permutation (all values are between 0 and n-1), developers might add unnecessary bounds checking.

Overcomplicated Approach:

def buildArray(self, nums: List[int]) -> List[int]:
    result = []
    for num in nums:
        if 0 <= num < len(nums):  # Unnecessary check
            result.append(nums[num])
        else:
            result.append(0)  # Will never execute for valid input
    return result

Solution: Trust the problem constraints. The input is guaranteed to be a valid permutation, so every value will be a valid index.

3. Advanced: Space-Optimized In-Place Solution

If you need to solve this with O(1) extra space (modifying the original array), you can encode both old and new values in each position:

def buildArray(self, nums: List[int]) -> List[int]:
    n = len(nums)
  
    # First pass: encode both old and new values
    # new_value = nums[nums[i]], old_value = nums[i]
    # Store as: nums[i] = old_value + n * new_value
    for i in range(n):
        # Get the old value at nums[i] (might already be encoded)
        old_val = nums[nums[i]] % n
        nums[i] = nums[i] + n * old_val
  
    # Second pass: extract the new values
    for i in range(n):
        nums[i] = nums[i] // n
  
    return nums

This technique uses the fact that we can store two values in one integer by using division and modulo operations with the array length.