Welcome to Subscribe On Youtube

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

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.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  
  

• 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;
      }
  };
  
  

• 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
  
  

• 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
  }
  
  

• 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;
  }
  
  

All Problems

All Solutions