3819. Rotate Non Negative Elements

Problem Statement in English

You’re given an array of integers nums and a non-negative integer k.

You need to rotate all the non-negative elements in the array to the right by k positions, while keeping the negative elements in their original positions.

Return the modified array after performing the rotation.

Approach

It helps a lot if you just imagine that the negative elements are not there at all.

Then we can simply solve this problem as how we would rotate any array to the right by k positions.

So we perform the rotation on the non-negative elements only, and then just iterate over the original array and replace the non-negative elements with the rotated ones - in order.

And we’re done

Solution in Python

class Solution:
    def rotateElements(self, nums: List[int], k: int) -> List[int]:
        buffer = [num for num in nums if num > -1]

        if not buffer:
            return nums
        
        k %= len(buffer)

        first = buffer[:k]
        second = buffer[k:]

        merged = second + first

        p = 0

        for i in range(len(nums)):
            if nums[i] > -1:
                nums[i] = merged[p]
                p += 1

        return nums

Complexity

• Time: $O(n)$
  Since we iterate through the input list a constant number of times.

• Space: $O(n)$
  Since we are using an additional buffer to store non-negative elements.

And we are done.