Rearrange an Array to Put the Negative Elements Before the Positive Ones

1. Introduction

In this tutorial, we’ll show how to arrange a numeric array so that its negative elements come before its positive ones.

In doing so, we’ll require the solution to keep the relative order of the same-sign elements.

2. Problem Statement

Let’s say we have an array $a=[a_1, a_2, \ldots, a_n]$ . Our goal is to rearrange it into $a'=[a_1', a_2', \ldots, a_k', a_{k+1}', \ldots, a_n']$ so that all elements $a_j$ for $j \leq k$ are negative, and all that come after $a_k$ , if any, are positive.

Simultaneously, we want to keep the relative order in the negative and positive sub-arrays. So, for any $i < j$ , it should hold that $a_i' < 0$ and $a_j' > 0$ or that $sign(a_i')=sign(a_j')$ , but $a_i'$ was to the left of $a_j'$ in the original array.

For example, if $a = [10, -2, 30, -4, 1, -20, 3, -40]$ , the correct rearrangement is $a'=[-2, -4, -20, -40, 10, 30, 1, 3]$ .

Since $sign(0)=1$ , we’ll include any element equal to zero in the positive sub-array.

3. The Solution With Two Queues

We can start with two empty queues: $queue_+$ for the positive and $queue_-$ for the negative elements of $a$ . We populate them by iterating over $\boldsymbol{a}$ and placing its elements into the queues based on their signs.

After that, we append $queue_+$ to $queue_-$ to get $a'$ :

Since we iterate over the input array once and concatenate two queues whose sizes sum to $n$ , the time complexity is $\boldsymbol{O(n)}$ . The only requirement is that storing a number in a queue be a constant-time operation.

The space complexity is also linear because we need $O(n)$ space for $a$ and $O(n)$ memory for queues.

4. The Solution With Merging

If we don’t want to take $O(n)$ extra memory, we can rearrange the array using an algorithm similar to MergeSort.

First, we split the array into pairs of consecutive elements:

$[a_1, a_2] [a_3, a_4] \ldots [a_{n-1}, a_n]$

If $n$ is odd, we’ll let $[a_n]$ be the last sub-array. For simplicity, we’ll assume $n$ is even since that won’t affect the correctness of this approach but will make it easier to explain.

In the next step, we swap the elements in each sub-array if the first one is positive and the second negative. So, we ensure that the signs are:

$[-, +] [-, +] \ldots [-, +]$

Afterward, we merge and arrange consecutive pairs of previously processed sub-arrays. That way, we arrange sub-arrays with four elements:

$[-, -, +, +], [-, -, +, +], \ldots, [-, -, +, +]$

Processing larger and larger sub-arrays, we eventually get to rearrange the entire input array $a$ .

4.1. Merging Two Sub-Arrays

Let’s focus on two consecutive sub-arrays of $a$ in an iteration of the rearrangement process:

$[L_- L_+ ] [R_- R_+]$

Let $L_-$ be the left’s sub-array negative part, and let $L_+$ contain its positive elements. Similar goes for the right sub-array and its parts $R_-$ and $R_+$ .

To merge the two sub-arrays to be in line with our requirements, we need to swap $\boldsymbol{L_+}$ with $\boldsymbol{R_-}$ while preserving relative orders in both:

$[L_- R_- L_+ R_+]$

First, we reverse $\boldsymbol{L_+}$ and $\boldsymbol{R_-}$ separately. Then, we reverse them together. To see why that works, let $L_+=[a_i, a_{i+1}, \ldots, a_{j}]$ and $R_-=[a_{j+1}, a_{j+2}, \ldots, a_r]$ .

So, we start with this:

$a_i, a_{i+1}, \ldots, a_{j-1}, a_j, a_{j+1}, a_{j+2}, \ldots, a_{r-1}, a_r$

If we first reverse the sub-arrays separately, we get:

$a_j, a_{j-1}, \ldots, a_{i+1}, a_i, a_r, a_{r-1}, \ldots, a_{j+2}, a_{j+1}$

Reversing them together gives us:

$a_{j+1}, a_{j+2}, \ldots, a_r, a_i, a_{i+1}, \ldots, a_j$

which is what we want to achieve.

4.2. Iterative MergeArrange

Let $a[i, \ldots, j]$ ( $i \leq j$ ) be the sub-array containing the elements of $a$ starting with $a_i$ and ending with $a_j$ (if $j>n$ , it stops at $a_n$ ). Here’s the pseudocode of our iterative MergeSort-like approach we call MergeArrange:

We start with sub-arrays of length $\boldsymbol{\ell = 1}$ to sort the consecutive pairs. Then, we double the length iteratively until covering the entire array.

In each iteration, the left sub-arrays for merging start at indices $1 + 2k \ell$ for some integer $k = 1, 2, \ldots, \lfloor n / 2\ell \rfloor$ since two consecutive sub-arrays together contain $2\ell$ elements. The corresponding right sub-arrays start at $\ell$ elements to the right.

4.3. Example

Let’s use the example from the start:

$a = [10, -2, 30, -4, 1, -20, 3, -40]$

In the first iteration, $\ell=1$ , so we have this split:

$[10] [ -2] [30] [ -4] [1] [-20] [3] [-40]$

After merging, we get:

$[-2, 10] [-4, 30] [-20, 1] [-40, 3]$

In the second iteration, $\ell=2$ , so we merge and arrange the consecutive pairs:

$[-2, -4, 10, 30] [-20, -40, 1, 3]$

In the third iteration, $\ell=4$ , so we process the remaining two sub-arrays of length 4:

$[-2, -4, -20, -40, 10, 30, 1, 3]$

Now, we get $\ell=8$ . That means there’s only one sub-array, i.e., the entire array. Therefore, we stop since it’s in the order we want it to be.

4.4. Complexity

There are at most $O(\log n)$ iterations, each of which makes at most $3n$ swaps. So, the time complexity is $\boldsymbol{O(n \log n)}$ .

We use only a constant number of auxiliary variables for looping and swapping, so the extra space complexity is $\boldsymbol{O(1)}$ . However, the total space complexity is still $\boldsymbol{O(n)}$ since we need $O(n)$ memory to store the initial array.

So, our MergeArrange algorithm has the same complexity as MergeSort. That isn’t a surprise because it works like bottom-up MergeSort sorting its input array using $sign(a_i) \cdot i$ instead of the actual values $a_i$ .

In fact, any stable sorting algorithm using $sign(a_i) \cdot i$ to sort the $a_i$ will do the job.

5. Conclusion

In this article, we showed two ways to rearrange a numeric array so that its negative elements get before its positive ones and those equal to zero, keeping the relative order of the elements in the same sub-array.

Our first solution uses two queues and runs in $O(n)$ time and space. The algorithm we derived from MergeSort uses $O(1)$ additional memory but runs in $O(n \log n)$ time.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex