LeetCode 3819 - Rotate Non Negative Elements

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

The problem asks us to rotate only the non-negative elements of an integer array nums to the left by k positions in a cyclic manner, while leaving all negative elements fixed in their original positions. In other words, the negative numbers act as "anchors" in the array, and the rotation affects only the positive numbers and zeros. After rotating the non-negative numbers, they must be reinserted back into the array at their original non-negative indices, skipping all negative positions.

The input is an array of integers with a size up to 10^5 and a rotation count k up to 10^5. This suggests that the algorithm must be efficient, ideally linear in time, because a naive solution that rotates elements one by one could be too slow.

Important edge cases include arrays with only negative numbers (nothing should move), arrays with only non-negative numbers (normal rotation), and cases where k is larger than the number of non-negative elements, requiring modulo arithmetic to handle cyclic rotation properly.

Approaches

Brute Force Approach

The brute force approach would be to repeatedly perform a single left rotation k times on the list of non-negative elements. First, extract all non-negative elements into a separate list. Then, for each of the k rotations, move the first element to the end. Finally, place the rotated elements back into their original positions in the array.

This approach is correct because it explicitly simulates the left rotation. However, it is inefficient. Each rotation takes O(n_nonneg) time, and performing k rotations can lead to O(k * n_nonneg) time complexity, which is impractical when k and the array length are large.

Optimal Approach

The key observation for an optimal solution is that left rotation by k positions is equivalent to slicing and concatenating the array of non-negative elements. Specifically, for a list nonneg of length m, rotating left by k is equivalent to nonneg[k % m:] + nonneg[:k % m]. This avoids repeated shifting and ensures O(m) time for the rotation step. After the rotation, we traverse the original array once and replace non-negative positions with elements from the rotated list. This leads to an overall O(n) time complexity and O(m) extra space, where m is the number of non-negative elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * n_nonneg)	O(n_nonneg)	Repeatedly shift the non-negative elements one by one
Optimal	O(n)	O(n_nonneg)	Extract, rotate using slicing, and reinsert

Algorithm Walkthrough

Extract non-negative elements: Traverse the array nums and collect all non-negative values into a separate list nonneg. Keep track of their original indices for reinsertion. This isolates the elements that need rotation.
Compute effective rotation: Let m be the length of nonneg. The actual left rotation needed is k % m. This handles cases where k is larger than the number of non-negative elements.
Perform the rotation: Rotate the nonneg list by slicing: rotated = nonneg[k:] + nonneg[:k]. This efficiently rotates the elements without repeated shifting.
Reinsert rotated elements: Traverse nums again. For every non-negative position, replace it with the next element from the rotated list. Negative elements remain unchanged.
Return the resulting array: After reinserting all rotated elements, the array is in the desired state.

Why it works: The algorithm preserves the original positions of negative elements, rotates only the non-negative elements, and uses modulo arithmetic to handle cyclic rotations. These invariants guarantee correctness.

Python Solution

from typing import List

class Solution:
    def rotateElements(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Extract non-negative elements
        nonneg = [num for num in nums if num >= 0]
        
        if not nonneg:
            return nums  # No non-negative elements to rotate
        
        m = len(nonneg)
        k %= m  # Effective rotation
        
        # Step 2: Rotate non-negative elements
        rotated = nonneg[k:] + nonneg[:k]
        
        # Step 3: Reinsert rotated elements into original positions
        idx = 0
        result = []
        for num in nums:
            if num >= 0:
                result.append(rotated[idx])
                idx += 1
            else:
                result.append(num)
        
        return result

The implementation first extracts all non-negative numbers to handle rotation independently of negatives. It calculates the effective rotation using modulo, performs slicing-based rotation, and then carefully reinserts the rotated numbers into their original non-negative positions while leaving negative numbers untouched.

Go Solution

func rotateElements(nums []int, k int) []int {
    // Step 1: Extract non-negative elements
    nonneg := []int{}
    for _, num := range nums {
        if num >= 0 {
            nonneg = append(nonneg, num)
        }
    }

    if len(nonneg) == 0 {
        return nums // No non-negative elements to rotate
    }

    m := len(nonneg)
    k %= m // Effective rotation

    // Step 2: Rotate non-negative elements
    rotated := append(nonneg[k:], nonneg[:k]...)

    // Step 3: Reinsert rotated elements
    result := make([]int, len(nums))
    idx := 0
    for i, num := range nums {
        if num >= 0 {
            result[i] = rotated[idx]
            idx++
        } else {
            result[i] = num
        }
    }

    return result
}

In Go, slices are used to store non-negative elements and perform rotation. The reinsertion step requires creating a new result slice to avoid overwriting elements prematurely, which is a common Go-specific consideration.

Worked Examples

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

Step	Non-negative list	Rotated list	Result
Extract	[1, 3]	-	-
Effective k	-	k % 2 = 1	-
Rotate	[1, 3]	[3, 1]	-
Reinsert	-	-	[3, -2, 1, -4]

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

Step	Non-negative list	Rotated list	Result
Extract	[7]	-	-
Effective k	-	1 % 1 = 0	-
Rotate	[7]	[7]	-
Reinsert	-	-	[-3, -2, 7]

Example 3: nums = [5,4,-9,6], k = 2

Step	Non-negative list	Rotated list	Result
Extract	[5, 4, 6]	-	-
Effective k	-	2 % 3 = 2	-
Rotate	[5, 4, 6]	[6, 5, 4]	-
Reinsert	-	-	[6, 5, -9, 4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to extract, one pass to reinsert, rotation slicing is O(m), total O(n)
Space	O(m)	Extra space to store non-negative elements, m <= n

This approach is efficient because it avoids repeated shifting and only performs linear operations relative to the array size.

Test Cases

# Provided examples
assert Solution().rotateElements([1,-2,3,-4], 3) == [3,-2,1,-4]  # mix of negative and positive
assert Solution().rotateElements([-3,-2,7], 1) == [-3,-2,7]      # single non-negative
assert Solution().rotateElements([5,4,-9,6], 2) == [6,5,-9,4]    # multiple non-negatives

# Edge cases
assert Solution().rotateElements([], 10) == []                     # empty array
assert Solution().rotateElements([-1,-2,-3], 5) == [-1,-2,-3]     # all negatives
assert Solution().rotateElements([0,1,2,3], 4) == [0,1,2,3]       # rotation equal to length
assert Solution().rotateElements([0,1,2,3], 6) == [2,3,0,1]       # rotation larger than length
assert Solution().rotateElements([0], 0) == [0]                    # single element zero
assert Solution().rotateElements([-1], 0) == [-1]                  # single element negative

Test	Why
mix of negatives and positives	validates normal rotation with fixed negatives
single non-negative	validates rotation when only one element
multiple non-negatives	validates proper slice-based rotation
empty array	ensures