Rotate Non Negative Elements - Solution & Explanation

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.