Scale Engineer

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:

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

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.

Solutions

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 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 →

Next problem