Skip to content

3819. Rotate Non Negative Elements

Description

You are given an integer array nums and an integer k.

Rotate only the non-negative elements of the array to the left by k positions, in a cyclic manner.

All negative elements must stay in their original positions and must not move.

After rotation, place the non-negative elements back into the array in the new order, filling only the positions that originally contained non-negative values and skipping all negative positions.

Return the resulting array.

 

Example 1:

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

Output: [3,-2,1,-4]

Explanation:​​​​​​​

  • The non-negative elements, in order, are [1, 3].
  • Left rotation with k = 3 results in:
    • [1, 3] -> [3, 1] -> [1, 3] -> [3, 1]
  • Placing them back into the non-negative indices results in [3, -2, 1, -4].

Example 2:

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

Output: [-3,-2,7]

Explanation:

  • The non-negative elements, in order, are [7].
  • Left rotation with k = 1 results in [7].
  • Placing them back into the non-negative indices results in [-3, -2, 7].

Example 3:

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

Output: [6,5,-9,4]

Explanation:

  • The non-negative elements, in order, are [5, 4, 6].
  • Left rotation with k = 2 results in [6, 5, 4].
  • Placing them back into the non-negative indices results in [6, 5, -9, 4].

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • 0 <= k <= 105

Solutions

Solution 1: Simulation

Thinking

Non-negative values rotate left by \(k\); negatives stay put. \(n \le 10^5\), and in-place interleaving is error-prone and unnecessary.

Non-negatives form their own sequence; negatives are only placeholders. Extract, rotate that sequence, then write it back into the old non-negative slots.

The new index is \(((i-k)\bmod m+m)\bmod m\) for \(m\) non-negative entries.

A second scan fills only those slots; negatives keep their original values.

We first extract all non-negative elements from the array and store them in a new array \(t\).

Then, we create an array \(d\) of the same size as \(t\) to store the rotated non-negative elements. For each element \(t[i]\) in \(t\), we place it in \(d\) at position \(((i - k) \bmod m + m) \bmod m\), where \(m\) is the number of non-negative elements.

Next, we iterate through the original array \(\textit{nums}\). For each position containing a non-negative element, we replace it with the element from the corresponding position in \(d\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(m)\), where \(m\) is the number of non-negative elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def rotateElements(self, nums: List[int], k: int) -> List[int]:
        t = [x for x in nums if x >= 0]
        m = len(t)
        d = [0] * m
        for i, x in enumerate(t):
            d[((i - k) % m + m) % m] = x
        j = 0
        for i, x in enumerate(nums):
            if x >= 0:
                nums[i] = d[j]
                j += 1
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] rotateElements(int[] nums, int k) {
        int m = 0;
        for (int x : nums) {
            if (x >= 0) {
                m++;
            }
        }
        int[] t = new int[m];
        int p = 0;
        for (int x : nums) {
            if (x >= 0) {
                t[p++] = x;
            }
        }
        int[] d = new int[m];
        for (int i = 0; i < m; i++) {
            d[((i - k) % m + m) % m] = t[i];
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                nums[i] = d[j++];
            }
        }
        return nums;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> rotateElements(vector<int>& nums, int k) {
        vector<int> t;
        for (int x : nums) {
            if (x >= 0) {
                t.push_back(x);
            }
        }
        int m = t.size();
        vector<int> d(m);
        for (int i = 0; i < m; i++) {
            d[((i - k) % m + m) % m] = t[i];
        }
        int j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= 0) {
                nums[i] = d[j++];
            }
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func rotateElements(nums []int, k int) []int {
    t := make([]int, 0)
    for _, x := range nums {
        if x >= 0 {
            t = append(t, x)
        }
    }
    m := len(t)
    d := make([]int, m)
    for i, x := range t {
        d[((i-k)%m+m)%m] = x
    }
    j := 0
    for i, x := range nums {
        if x >= 0 {
            nums[i] = d[j]
            j++
        }
    }
    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function rotateElements(nums: number[], k: number): number[] {
    const t: number[] = nums.filter(x => x >= 0);
    const m = t.length;
    const d = new Array<number>(m);
    for (let i = 0; i < m; i++) {
        d[(((i - k) % m) + m) % m] = t[i];
    }
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= 0) {
            nums[i] = d[j++];
        }
    }
    return nums;
}

Comments