Skip to main content
Talentd

Rotate Non Negative Elements - Solution & Explanation

MediumArraySimulation8 min readAsked at: Accolite
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array of integers. Only the non-negative elements should be rotated among themselves while negative values stay fixed at their original indices. The relative order of negative elements never changes; only the non-negative values move to the next available non-negative position in a cyclic manner.

Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)

Iterate through the array and, for each non-negative element, search forward to locate the next index containing another non-negative value. Swap or shift elements step by step until the rotation effect is achieved. Because each search may scan a large part of the array, this method can degrade to quadratic time in the worst case. The approach is easy to reason about but inefficient for large arrays.

Approach 2: Index Collection + Rotation (O(n) time, O(k) space)

Scan the array once and record the indices of all non-negative elements in a list. Extract their values, perform a cyclic rotation (for example, shift right by one), then write the rotated values back to the same recorded indices. Since each element is processed a constant number of times, the overall complexity stays linear. This technique works well because it separates position tracking from value manipulation.

Approach 3: In-Place Cyclic Rotation (O(n) time, O(1) space)

Instead of storing values separately, keep track of the first non-negative value and move through the collected non-negative indices, swapping values as you go. Each step moves the previous value into the next non-negative position, effectively simulating a cycle. This avoids extra memory and still processes the array in a single pass over the relevant indices. It’s a classic simulation pattern applied to an array.

Recommended for interviews: The index-collection simulation is the most straightforward explanation and runs in O(n) time. Interviewers usually expect this approach because it clearly separates identifying valid positions from performing the rotation. Starting with the brute-force idea shows understanding, but implementing the linear-time simulation demonstrates strong control over array traversal and state management.

Solution

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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(1)Useful for understanding the mechanics of rotating values without extra data structures.
Index Collection + RotationO(n)O(k)Best general solution. Simple to implement and easy to explain in interviews.
In-Place Cyclic RotationO(n)O(1)When memory usage matters and you want a fully in-place array manipulation.

Video Solution

Rotate Non-Negative Elements | LeetCode 3819 | Weekly Contest 486 • Sanyam IIT Guwahati • 547 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Rotate Non Negative Elements easy or hard?
Rotate Non Negative Elements is generally considered a medium-level problem. The logic is straightforward once you recognize that only a subset of elements should participate in the rotation. The challenge lies in correctly tracking indices and preserving the positions of negative values.
Rotate Non Negative Elements Python/Java solution
The typical Python or Java solution scans the array to collect indices of non-negative elements, rotates their values, and writes them back. Python often uses a list to store values and slice rotation, while Java uses an ArrayList or temporary array. Both implementations achieve O(n) time complexity.
How to solve Rotate Non Negative Elements in O(n)?
Traverse the array and store the indices of elements greater than or equal to zero. Extract the corresponding values, rotate them cyclically (such as shifting right by one), and place them back at the same indices. Each step touches elements only once, giving linear time complexity.
What is the best approach for Rotate Non Negative Elements?
The most practical approach is a simulation that first collects the indices of all non-negative elements, rotates their values, and writes them back. This method runs in O(n) time because the array is scanned once and each value is moved a constant number of times. It keeps negative elements fixed while rotating only the valid positions.
Is Rotate Non Negative Elements asked at Google/Amazon/Meta?
Array manipulation and simulation problems like this frequently appear in coding interviews at companies such as Amazon, Google, and Meta. The exact problem may vary, but rotating subsets of elements while keeping constraints on positions is a common interview pattern.
What data structure is used in Rotate Non Negative Elements?
The primary data structure is an array. Some implementations also use a temporary list or vector to store indices or values of non-negative elements during rotation. The algorithm mainly relies on sequential traversal and simple index manipulation.
What is the time complexity of Rotate Non Negative Elements?
The optimal solution runs in O(n) time where n is the array length. The algorithm scans the array to identify non-negative indices and performs a cyclic rotation among those positions. Space complexity is typically O(k), where k is the number of non-negative elements, although an in-place variant can reduce this to O(1).

Ready to solve this problem?

Practice Rotate Non Negative Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays