# Transformed Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/transformed-array)
Canonical: https://scaleengineer.com/dsa/problems/transformed-array
**Data structures:** Array
---
## Problem
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
## Simulation with Step-by-Step Movement
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.
**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.
**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.
### Explanation
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:
```java
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;
                continue;
            }

            int destIndex = i;
            if (nums[i] > 0) {
                for (int j = 0; j < nums[i]; j++) {
                    destIndex++;
                    if (destIndex == n) {
                        destIndex = 0;
                    }
                }
            } else { // nums[i] < 0
                for (int j = 0; j < Math.abs(nums[i]); j++) {
                    destIndex--;
                    if (destIndex < 0) {
                        destIndex = n - 1;
                    }
                }
            }
            result[i] = nums[destIndex];
        }
        return result;
    }
}
```
### 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`.

## 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.
**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.
**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.
### Explanation
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:
```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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 ; } }
```

### Python

```python
class 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
```

### CPP

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