algoadvance

Leetcode 1920. Build Array from Permutation

Problem Statement

You are given a zero-indexed array nums of size n consisting of distinct integers from 0 to n - 1. You need to build a new array ans where ans[i] = nums[nums[i]] for each 0 <= i < n and return it.

Clarifying Questions

1. Input Constraints:
   • Is the input array guaranteed to contain all integers from 0 to n-1 without duplicates?
   • What would be the size constraints of the input array nums?
2. Output Requirements:
   • Should the output array be of the same length as the input array?
   • Is in-place modification of the input array allowed or should a new array be created?
3. Edge Cases:
   • What should be the behavior for the smallest input size (n = 1)?

Strategy

1. Understanding the Problem:
   • We need to iterate through the input array nums.
   • For every element i, we compute ans[i] such that ans[i] = nums[nums[i]].
2. Steps to Solve:
   • Initialize an empty array ans of the same length as nums.
   • Iterate through the input array nums.
   • For each index i, assign ans[i] the value of nums[nums[i]].
3. Constraints and Edge Cases:
   • Since all elements in nums are distinct and from 0 to n-1, there is no out-of-bound access.

Code

#include <vector>
using namespace std;

class Solution {
public:
    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;
    }
};

Time Complexity

• Time Complexity: O(n)
  • We iterate through the array nums exactly once, performing a constant-time operation nums[nums[i]] for each element.
• Space Complexity: O(n)
  • We use an additional array ans of the same length as the input array nums.

Explanation:

• We iterate over the input vector nums.
• For each index i, ans[i] is set to nums[nums[i]] as per the problem statement.
• Finally, we return the constructed array ans.

This approach ensures that the solution is efficient and meets the constraints of the problem effectively.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?