LeetCode 3379 - Transformed Array

The problem asks us to transform a given integer array nums into a new array result following specific movement rules. Each element in nums determines how many steps to move in a circular manner, either to the right (if positive) or left (if negative).

leetcodeeasyarraysimulation

LeetCode Problem 3379

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

The problem asks us to transform a given integer array nums into a new array result following specific movement rules. Each element in nums determines how many steps to move in a circular manner, either to the right (if positive) or left (if negative). Zero values remain unchanged. The circular array property means that moving past the last index wraps around to the start, and moving before the first index wraps around to the end. The input array length is guaranteed to be between 1 and 100, and each element's absolute value does not exceed 100.

The expected output is an array of the same size where each element is replaced by the value found after performing the circular movement determined by the original element. Important edge cases include small arrays, elements that wrap around multiple times due to large positive or negative values, and arrays with zeros which should remain unchanged.

Approaches

The brute-force approach is straightforward: iterate through each element of nums, calculate the target index by adding or subtracting the number of steps, and apply modulo arithmetic to handle circular wrapping. This approach is correct because it directly simulates the problem rules. Since the constraints are small (nums.length <= 100), a simple O(n) solution suffices, as each computation for the new index is O(1). There is no need for additional optimization because the brute-force solution already meets time requirements for the input size.

The key insight for this problem is recognizing that modulo arithmetic elegantly handles circular movement. Instead of manually looping steps to the right or left, (i + steps) % n for right movement and (i - steps + n) % n for left movement gives the correct target index efficiently. Using this approach avoids unnecessary iteration and simplifies the logic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Iterates each element and computes target index using modulo for circular behavior
Optimal O(n) O(n) Direct modulo calculation; no extra optimizations required due to small input size

Algorithm Walkthrough

  1. Determine the length n of the input array nums.
  2. Initialize a new array result of the same length.
  3. Iterate through each index i of nums.
  4. If nums[i] is zero, assign result[i] = 0.
  5. If nums[i] is positive, calculate the target index as (i + nums[i]) % n and assign result[i] = nums[target].
  6. If nums[i] is negative, calculate the target index as (i + nums[i] + n) % n to correctly wrap around leftward and assign result[i] = nums[target].
  7. After processing all indices, return the result array.

The algorithm works because modulo arithmetic preserves circular behavior. Adding n for negative movement ensures the modulo result is non-negative. Each element is treated independently, so no intermediate states interfere with calculations.

Python Solution

from typing import List

class Solution:
    def constructTransformedArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        
        for i in range(n):
            if nums[i] == 0:
                result[i] = 0
            elif nums[i] > 0:
                target_index = (i + nums[i]) % n
                result[i] = nums[target_index]
            else:
                target_index = (i + nums[i] + n) % n
                result[i] = nums[target_index]
        
        return result

In this Python implementation, we initialize result to the same length as nums. We handle zero, positive, and negative cases separately. The modulo arithmetic ensures proper circular wrapping without additional conditional checks.

Go Solution

func constructTransformedArray(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    
    for i, val := range nums {
        if val == 0 {
            result[i] = 0
        } else if val > 0 {
            target := (i + val) % n
            result[i] = nums[target]
        } else {
            target := (i + val + n) % n
            result[i] = nums[target]
        }
    }
    
    return result
}

The Go version mirrors the Python solution. We use make to initialize the result slice. Looping through the array, we apply the same modulo arithmetic to handle circular movement. Go requires handling slices and indexing carefully, but otherwise the logic is identical.

Worked Examples

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

i nums[i] Steps Target Index Calculation result[i]
0 3 right 3 (0 + 3) % 4 = 3 nums[3] = 1
1 -2 left 2 (1 - 2 + 4) % 4 = 3 nums[3] = 1
2 1 right 1 (2 + 1) % 4 = 3 nums[3] = 1
3 1 right 1 (3 + 1) % 4 = 0 nums[0] = 3

Result: [1, 1, 1, 3]

Example 2: nums = [-1, 4, -1]

i nums[i] Steps Target Index Calculation result[i]
0 -1 left 1 (0 - 1 + 3) % 3 = 2 nums[2] = -1
1 4 right 4 (1 + 4) % 3 = 2 nums[2] = -1
2 -1 left 1 (2 - 1 + 3) % 3 = 1 nums[1] = 4

Result: [-1, -1, 4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is processed exactly once, and index computation is O(1)
Space O(n) We create a new array result of the same size as nums

Since n <= 100, this solution is extremely efficient.

Test Cases

# Provided examples
assert Solution().constructTransformedArray([3,-2,1,1]) == [1,1,1,3]  # Example 1
assert Solution().constructTransformedArray([-1,4,-1]) == [-1,-1,4]  # Example 2

# Edge cases
assert Solution().constructTransformedArray([0,0,0]) == [0,0,0]  # All zeros
assert Solution().constructTransformedArray([1]) == [1]  # Single element
assert Solution().constructTransformedArray([-100,100]) == [100,-100]  # Max steps

# Mixed positive and negative
assert Solution().constructTransformedArray([2,-1,3,-2,0]) == [3,2,0,3,0]
Test Why
[3,-2,1,1] Verifies typical positive and negative moves
[-1,4,-1] Circular wrapping for small array
[0,0,0] Checks handling of zeros
[1] Single-element array edge case
[-100,100] Maximum step values to ensure wrapping correctness
[2,-1,3,-2,0] Mixed positive, negative, and zero values

Edge Cases

The first edge case is an array with a single element. This tests whether the modulo arithmetic handles self-wrapping correctly, which it does since (0 + 0) % 1 = 0.

The second edge case involves zeros in the array. These should remain unchanged. The implementation explicitly checks for nums[i] == 0 before applying movement, preventing incorrect overwrites.

The third edge case is very large positive or negative numbers relative to the array length. Since the movement uses modulo n, it ensures that any number of steps correctly wraps around the circular array, handling large values without extra iterations or errors.