algoadvance

Leetcode 1920. Build Array from Permutation

Problem Statement

Given a zero-based permutation nums (0-indexed), build an array of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it. A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Example 1:

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

Example 2:

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

Constraints:

Clarifying Questions

  1. Q: Can the input array be empty? A: No, the constraints specify that 1 <= nums.length.

  2. Q: Will all elements in the input array be unique and within the specified range? A: Yes, based on the constraints all elements are distinct and within the range [0, nums.length - 1].

  3. Q: Is there any need to handle invalid input cases? A: No, it is guaranteed based on constraints that the input will always be valid.

Strategy

  1. Create a new array ans of the same length as nums.
  2. Iterate over the elements of nums.
  3. For each element at index i, set ans[i] to nums[nums[i]].
  4. Return the array ans.

The steps above ensure that the answer array is constructed as required by the problem statement.

Code

public class Solution {
    public int[] buildArray(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
}

Time Complexity

Given the size of the input array nums is n, the solution:

Therefore, the time complexity is O(n). The space complexity is also O(n) because of the additional array ans of the same length as nums.

This approach ensures that the operation is efficient and meets the problem’s requirements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI