1920. Build Array from Permutation
Problem Description
The problem provides an array called nums
, which is a zero-based permutation. This means that nums
is an array where each number is unique and ranges from 0
to nums.length - 1
, with no duplicates and no numbers out of this range. The task is to create a new array ans
with the same length as nums
. The value at each index i
in the new array, ans[i]
, should be determined by finding the value at index nums[i]
within nums
. More clearly, for every index i
from 0
to nums.length - 1
, ans[i]
is equal to nums[nums[i]]
. Overall, the objective is to re-map the array based on the current values pointing to other indices within the same array.
Intuition
To arrive at the solution, we do not need to modify the original array or use additional data structures. The problem can be solved with a straightfoward approach:
- Iterate through each element of the array
nums
. - For each index
i
, find the element at the index specified by the value ofnums[i]
, which isnums[nums[i]]
. - Append this element to our answer array
ans
.
In the language of the given solution in Python, this translates into a simple list comprehension, which is a concise and efficient way of creating a list in Python from another iterable while applying some condition or operation to each element.
The line return [nums[num] for num in nums]
is Python's way of saying, "for each element num
in the list nums
, take nums[num]
, and put it in a new list," which is exactly the new array ans
we want to return.
So the intuition behind the solution is simply following the instructions given by the problem in a direct manner, utilizing the language's features to write less code that does more.
Solution Approach
Since the Reference Solution Approach section provided is empty, I'll elaborate based on the solution code given. The implementation of the problem's solution is straightforward:
-
Algorithm: The algorithm is a simple iteration over the original array. The permutation property of the array assures us that we will not have out-of-bounds errors or duplicates.
-
Data Structures: The only data structure used is the list itself in Python (
List[int]
). There is no need for additional data structures like stacks, queues, or hash maps because we're not dealing with operations that require such complexity. -
Pattern Used: The pattern used here is direct addressing where indices of the array directly correspond to the values because of the permutation's nature.
Here's a walk-through of the implementation in the given solution:
-
We start by using the list comprehension feature in Python, which allows us to construct a new list in one line of code.
-
The expression within the list comprehension
[nums[num] for num in nums]
is the core of our solution.for num in nums
is a loop that goes through each number (as index) in thenums
array. -
For each iteration, the value
nums[num]
is calculated. Due to the nature of the permutation array (every value in the array is a valid index into the array),num
is always a valid index ofnums
, and thusnums[num]
is always a valid operation. -
Each result of
nums[num]
is collected into a new list. This constructed list is immediately returned as the final answer without the necessity of a temporary holder.
The absence of nested loops or complicated branching indicates that this operation is linear in time complexity, essentially O(n)
, where n
is the number of elements in the nums
array. Space complexity is also O(n)
due to the creation of the ans
array which holds the same number of elements as nums
.
Nothing beyond the list itself and basic iteration is used to arrive at the solution, making this a cleanly implemented answer for the given problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walkthrough the solution approach with a given example. Suppose we have an input array nums
defined as follows:
nums = [2, 0, 1]
Following the problem description, the result array ans
will be constructed where each of its elements ans[i]
must be equal to nums[nums[i]]
. Here's the step-by-step logic to get ans
:
-
Start with an empty array
ans
. -
For the first element
nums[0] = 2
, findnums[nums[0]]
, which isnums[2]
. Sincenums[2] = 1
, we add1
to theans
array, making it nowans = [1]
. -
Move to the second element
nums[1] = 0
, findnums[nums[1]]
, which isnums[0]
. Sincenums[0] = 2
, we add2
to theans
array, nowans = [1, 2]
. -
Lastly, for the third element
nums[2] = 1
, findnums[nums[2]]
, which isnums[1]
. Sincenums[1] = 0
, we add0
to theans
array, resulting inans = [1, 2, 0]
.
The final ans
array is [1, 2, 0]
, which directly corresponds to the permutation of indices defined by the original nums
array. Thus, by iterating over the indices of nums
and accessing the values in the order given by the elements of nums
, we applied the permutation to create a new array that matches the problem's requirements.
We can convert this step-by-step process into a one-liner in Python using list comprehension:
ans = [nums[num] for num in nums]
This single line of code loops through nums
, takes each element as an index (num
), and fetches the value of nums
at that index, appending it to the new list. It carries out the steps we manually processed earlier but does so in a concise and efficient way, which is why it is the optimal solution for this problem.
Solution Implementation
1from typing import List # Import the List type from the typing module for type hinting
2
3class Solution:
4 def build_array(self, nums: List[int]) -> List[int]:
5 # Creating a new list where each element is obtained by accessing the
6 # index of the current element in the original list 'nums'
7 return [nums[num] for num in nums] # List comprehension to build the new list
8
1class Solution {
2 // This method is responsible for constructing a new array based on specific rules.
3 public int[] buildArray(int[] nums) {
4 // Create an array of the same size as the input array to store the new sequence.
5 int[] resultArray = new int[nums.length];
6
7 // Iterate over the input array.
8 for (int index = 0; index < nums.length; ++index) {
9 // For each position in the result array, find the value at the index
10 // specified by the value in the input array at the current position.
11 // Assign this value to the current position in the result array.
12 resultArray[index] = nums[nums[index]];
13 }
14
15 // Return the constructed result array.
16 return resultArray;
17 }
18}
19
1#include <vector> // Include the vector header for using the vector container.
2
3// Solution class as provided in the original code snippet.
4class Solution {
5public:
6 // Function 'buildArray' takes a vector of integers as input and returns a vector of integers.
7 vector<int> buildArray(vector<int>& nums) {
8 // Create an empty vector 'result' to store the final output.
9 vector<int> result;
10
11 // Use a range-based for loop to iterate over the elements in the 'nums' input vector.
12 for (int num : nums) {
13 // Access the element of 'nums' indexed by the value of 'num', and append it to 'result'.
14 result.push_back(nums[num]);
15 }
16
17 // Return the 'result' vector.
18 return result;
19 }
20};
21
1// Function to build a new array based on the rules given by an input array.
2// Each element at index 'i' in the output array is the element at index nums[i]
3// in the input array nums.
4function buildArray(nums: number[]): number[] {
5 // Use the 'map' function to transform each value of the original array.
6 // The 'v' represents the value at the current index in the nums array.
7 return nums.map((v) => nums[v]); // For each index 'i', place nums[nums[i]] in the new array.
8}
9
Time and Space Complexity
The given Python code takes an input list nums
and returns a new list based on the values from nums
where the i-th
element in the new list is nums[nums[i]]
.
Time Complexity:
The time complexity of the code is determined by the single loop which iterates through the list nums
. Since we are going through each element exactly once to construct the new list, the time complexity is O(n)
, where n
is the number of elements in nums
.
Space Complexity:
The space complexity includes the space needed for the input and the additional space required by the program. Since the input nums
is given, we typically don't consider this in the calculation.
The code creates a new list as a result. No additional data structures were created that would depend on the size of the input. Therefore, the space complexity is O(n)
, where n
is the length of the resultant list, which is the same as the input nums
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!