Transformed Array

Easy

#3002Time: O(N), where N is the length of the array. We iterate through the array once, and each calculation is a constant time operation.Space: O(N), to store the `result` array. As the problem requires creating a new array, this space is necessary.

Data structures

Array

Prompt

You are given an integer array nums that represents a circular array. Your task is to create a new array result of the same size, following these rules:

For each index i (where 0 <= i < nums.length), perform the following independent actions:

If nums[i] > 0: Start at index i and move nums[i] steps to the right in the circular array. Set result[i] to the value of the index where you land.
If nums[i] < 0: Start at index i and move abs(nums[i]) steps to the left in the circular array. Set result[i] to the value of the index where you land.
If nums[i] == 0: Set result[i] to nums[i].

Return the new array result.

Note: Since nums is circular, moving past the last element wraps around to the beginning, and moving before the first element wraps back to the end.

Example 1:

Input: nums = [3,-2,1,1]

Output: [1,1,1,3]

Explanation:

For nums[0] that is equal to 3, If we move 3 steps to right, we reach nums[3]. So result[0] should be 1.
For nums[1] that is equal to -2, If we move 2 steps to left, we reach nums[3]. So result[1] should be 1.
For nums[2] that is equal to 1, If we move 1 step to right, we reach nums[3]. So result[2] should be 1.
For nums[3] that is equal to 1, If we move 1 step to right, we reach nums[0]. So result[3] should be 3.

Example 2:

Input: nums = [-1,4,-1]

Output: [-1,-1,4]

Explanation:

For nums[0] that is equal to -1, If we move 1 step to left, we reach nums[2]. So result[0] should be -1.
For nums[1] that is equal to 4, If we move 4 steps to right, we reach nums[2]. So result[1] should be -1.
For nums[2] that is equal to -1, If we move 1 step to left, we reach nums[1]. So result[2] should be 4.

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This is a more efficient approach that avoids the step-by-step simulation. It uses the properties of modulo arithmetic to directly calculate the destination index for each element in a single operation. This eliminates the need for inner loops, significantly improving performance.

Algorithm

Initialize n = nums.length.
Create result = new int[n].
For i from 0 to n-1:
- If nums[i] == 0:
  - result[i] = 0.
- Else:
  - Calculate destIndex = ((i + nums[i]) % n + n) % n.
  - Set result[i] = nums[destIndex].
Return result.

Walkthrough

This highly efficient approach leverages mathematical properties to solve the problem in a single pass without nested loops. We create a result array and iterate through the input nums array once.

For each element nums[i] at index i:

The special case where nums[i] is 0 is handled first: result[i] is set to 0.
For all other cases, we calculate the destination index directly. The movement of k steps from index i in a circular array of size n can be expressed using the modulo operator. The destination index destIndex is (i + k) % n.
However, when k is negative, the result of the modulo operation can be negative in languages like Java. To ensure the index is always valid (i.e., in the range [0, n-1]), we use a robust formula: destIndex = ((i + nums[i]) % n + n) % n.
- (i + nums[i]) % n gives the displacement.
- + n ensures the value is non-negative.
- The final % n wraps the result back into the [0, n-1] range.
Once destIndex is calculated, we set result[i] = nums[destIndex].

This method is significantly faster as each element's transformation is a constant-time calculation.

Here is the Java implementation:

1class Solution {2    public int[] transformedArray(int[] nums) {3        int n = nums.length;4        int[] result = new int[n];5 6        for (int i = 0; i < n; i++) {7            if (nums[i] == 0) {8                result[i] = 0;9            } else {10                // Calculate the destination index using modulo arithmetic.11                // The `+ n` and second `% n` handle potential negative results from the first modulo.12                int destIndex = ((i + nums[i]) % n + n) % n;13                result[i] = nums[destIndex];14            }15        }16        return result;17    }18}

Complexity

Time

O(N), where N is the length of the array. We iterate through the array once, and each calculation is a constant time operation.

Space

O(N), to store the `result` array. As the problem requires creating a new array, this space is necessary.

Trade-offs

Pros

Highly efficient with a linear time complexity.
The runtime does not depend on the magnitude of the values in nums, only on the array's length.
Concise and elegant solution.

Cons

Requires understanding of modulo arithmetic, especially how to handle negative numbers, which might be less intuitive for some.

This approach directly simulates the process described in the problem. For each element in the input array, it calculates the destination index by moving one step at a time, either to the right or to the left, wrapping around the array boundaries as needed.

Algorithm

Initialize n = nums.length.
Create result = new int[n].
For i from 0 to n-1:
- Let steps = nums[i].
- If steps == 0:
  - result[i] = 0.
  - Continue to the next iteration.
- Initialize destIndex = i.
- If steps > 0:
  - For j from 0 to steps-1:
    - destIndex++.
    - If destIndex == n, destIndex = 0.
- If steps < 0:
  - For j from 0 to abs(steps)-1:
    - destIndex--.
    - If destIndex < 0, destIndex = n - 1.
- result[i] = nums[destIndex].
Return result.

Walkthrough

This approach involves creating a new result array of the same size as the input nums array. We then iterate through each element of nums from index i = 0 to n-1.

If the current element nums[i] is 0, we simply assign result[i] = 0.
If nums[i] is positive, we simulate moving nums[i] steps to the right. We start a loop that runs nums[i] times. In each iteration, we increment a destIndex (initialized to i) and wrap it around to 0 if it reaches n.
If nums[i] is negative, we simulate moving abs(nums[i]) steps to the left. We loop abs(nums[i]) times, decrementing destIndex and wrapping it around to n-1 if it becomes negative.

After the simulation loop determines the final destIndex, we retrieve the value from the original array, nums[destIndex], and assign it to result[i]. This process is repeated for all elements.

Here is the Java implementation:

1class Solution {2    public int[] transformedArray(int[] nums) {3        int n = nums.length;4        int[] result = new int[n];5 6        for (int i = 0; i < n; i++) {7            if (nums[i] == 0) {8                result[i] = 0;9                continue;10            }11 12            int destIndex = i;13            if (nums[i] > 0) {14                for (int j = 0; j < nums[i]; j++) {15                    destIndex++;16                    if (destIndex == n) {17                        destIndex = 0;18                    }19                }20            } else { // nums[i] < 021                for (int j = 0; j < Math.abs(nums[i]); j++) {22                    destIndex--;23                    if (destIndex < 0) {24                        destIndex = n - 1;25                    }26                }27            }28            result[i] = nums[destIndex];29        }30        return result;31    }32}

Complexity

Time

O(N * K), where N is the length of the array and K is the maximum absolute value of an element in the array. The outer loop runs N times, and the inner loop can run up to K times.

Space

O(N), to store the `result` array. As the problem requires creating a new array, this space is necessary.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem's description.
Intuitive for beginners.

Cons

Inefficient for large values in nums, as it involves nested loops. The number of operations depends on the magnitude of the numbers in the input array.

Solutions

Solution

1class Solution { public int [] constructTransformedArray ( int [] nums ) { int n = nums . length ; int [] ans = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = nums [ i ] != 0 ? nums [( i + nums [ i ] % n + n ) % n ] : 0 ; } return ans ; } }

1class Solution : def constructTransformedArray ( self , nums : List [ int ]) -> List [ int ]: ans = [] n = len ( nums ) for i , x in enumerate ( nums ): ans . append ( nums [( i + x + n ) % n ] if x else 0 ) return ans

1class Solution { public: vector < int > constructTransformedArray ( vector < int >& nums ) { int n = nums . size (); vector < int > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = nums [ i ] ? nums [( i + nums [ i ] % n + n ) % n ] : 0 ; } return ans ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem