Leetcode 1920: Build Array from Permutation

Input: The input consists of an array nums, which is a zero-based permutation of distinct integers from 0 to nums.length - 1.

Example: nums = [2, 0, 1, 4, 3]

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] < nums.length

• The elements in nums are distinct.

Output: Return the array ans, where each element is nums[nums[i]].

Example: [1, 2, 0, 3, 4]

Constraints:

Goal: For each index i in the array nums, compute nums[nums[i]] and store it in the result array ans.

Steps:

• Iterate over the array nums.

• For each index i, compute ans[i] = nums[nums[i]].

• Return the resulting array ans.

Goal: Ensure that the algorithm handles arrays with lengths up to 1000.

Steps:

• The array length is at least 1.

• The elements are distinct and fall within the range 0 to nums.length - 1.

Assumptions:

• The input array is a valid zero-based permutation of integers.

• The length of the array will not exceed 1000.

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

• Explanation: In the array nums = [2, 0, 1, 4, 3], the new array ans is computed as follows: ans[0] = nums[nums[0]] = nums[2] = 1, ans[1] = nums[nums[1]] = nums[0] = 2, ans[2] = nums[nums[2]] = nums[1] = 0, ans[3] = nums[nums[3]] = nums[4] = 3, ans[4] = nums[nums[4]] = nums[3] = 4. Thus, the final ans is [1, 2, 0, 3, 4].

Approach: We can simply iterate over the input array nums and use the given formula to compute the result for each index i.

Observations:

• The problem asks us to compute the value nums[nums[i]] for each index i.

• Since the array elements are distinct and within a specific range, we don't need additional data structures.

• This approach is straightforward and requires just one iteration through the array.

Steps:

• Initialize an empty result array ans of the same length as nums.

• Loop through the indices of nums and set ans[i] = nums[nums[i]].

• Return the result array ans.

Empty Inputs:

• The input will never be empty as per problem constraints.

Large Inputs:

• Ensure the solution efficiently handles inputs with the maximum size, i.e., nums.length = 1000.

Special Values:

• For the smallest array length (nums.length = 1), the result will be [nums[nums[0]]], which is just nums[0].

Constraints:

• The input array will always contain distinct integers from 0 to nums.length - 1.

vector<int> buildArray(vector<int>& nums) {
    int n=nums.size();
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        ans[i]=nums[nums[i]];
    }
    return ans;
}

1 : Function Definition

vector<int> buildArray(vector<int>& nums) {

Defines the function 'buildArray' which takes a vector of integers 'nums' and returns a new vector where each element is replaced by another element indexed by its own value.

2 : Variable Initialization

    int n=nums.size();

Initializes the variable 'n' to store the size of the input vector 'nums'.

3 : Variable Initialization

    vector<int> ans(n);

Initializes a vector 'ans' of size 'n' to store the result.

4 : Loop Start

    for(int i=0;i<n;i++){

Begins a loop that iterates over each index of the input vector 'nums'.

5 : Array Assignment

        ans[i]=nums[nums[i]];

For each index 'i', assigns the value at 'nums[nums[i]]' to 'ans[i]', effectively building the new array by accessing the element indexed by 'nums[i]'.

6 : Return Statement

    return ans;

Returns the newly constructed vector 'ans' that contains the elements at the indices specified by 'nums'.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The solution iterates over the array exactly once, which results in a time complexity of O(n), where n is the length of the input array.

Best Case: O(n)

Worst Case: O(n)

Description: We use an additional array of size n to store the result, so the space complexity is O(n).

Leetcode 1920: Build Array from Permutation

Explore →