Transformed Array

EASY

Description

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

Checkout 2 different approaches to solve Transformed Array. Click on different approaches to view the approach and algorithm in detail.

Direct Calculation using Modulo Arithmetic

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.

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:

class Solution {
    public int[] transformedArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                result[i] = 0;
            } else {
                // Calculate the destination index using modulo arithmetic.
                // The `+ n` and second `% n` handle potential negative results from the first modulo.
                int destIndex = ((i + nums[i]) % n + n) % n;
                result[i] = nums[destIndex];
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(N), to store the `result` array. As the problem requires creating a new array, this space is necessary.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Transformed Array. Click on different languages to view the code.

class 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 ; } }

Video Solution

Watch the video walkthrough for Transformed Array

Data Structures:

Array