Problem Description
Given a zero-based permutation nums (0-indexed), build an array ans 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).
Key Insights
- The problem requires creating a new array based on the indices provided in the original array.
- The transformation involves two levels of indexing, effectively mapping values to their respective indices.
- The constraints ensure that the input array is well-formed, allowing direct access without additional checks.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n) (or O(1) if optimized to use the input array itself)
Solution
To solve this problem, we will iterate through the input array nums and create a new array ans. For each index i, we will assign ans[i] the value of nums[nums[i]]. This requires a single pass through the array, resulting in a time complexity of O(n). We will use an additional array to store the results, resulting in a space complexity of O(n). However, it is possible to optimize this to O(1) space by modifying the input array directly if allowed.