C Program
#include <stdio.h>
void rearrange(int arr[], int n) {
int i = -1;
for (int j = 0; j < n; j++) {
if (arr[j] < 0) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int pos = i + 1, neg = 0;
while (pos < n && neg < pos && arr[neg] < 0) {
int temp = arr[neg];
arr[neg] = arr[pos];
arr[pos] = temp;
pos++;
neg += 2;
}
}
int main() {
int arr[] = {2, 3, -4, -1, 6, -9};
int n = sizeof(arr) / sizeof(arr[0]);
rearrange(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}C Output
-4 2 -1 3 -9 6
C++ Program
#include <iostream>
using namespace std;
void rearrange(int arr[], int n) {
int i = -1;
for (int j = 0; j < n; j++) {
if (arr[j] < 0) {
i++;
swap(arr[i], arr[j]);
}
}
int pos = i + 1, neg = 0;
while (pos < n && neg < pos && arr[neg] < 0) {
swap(arr[neg], arr[pos]);
pos++;
neg += 2;
}
}
int main() {
int arr[] = {1, 2, 3, -4, -1, 4};
int n = sizeof(arr) / sizeof(arr[0]);
rearrange(arr, n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
}C++ Output
-4 1 -1 2 3 4
JAVA Program
public class Main {
static void rearrange(int[] arr) {
int i = -1;
for (int j = 0; j < arr.length; j++) {
if (arr[j] < 0) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int pos = i + 1, neg = 0;
while (pos < arr.length && neg < pos && arr[neg] < 0) {
int temp = arr[neg];
arr[neg] = arr[pos];
arr[pos] = temp;
pos++;
neg += 2;
}
}
public static void main(String[] args) {
int[] arr = {1, -2, 3, -4, -1, 4};
rearrange(arr);
for (int num : arr) System.out.print(num + " ");
}
}JAVA Output
-2 1 -4 3 -1 4
Python Program
def rearrange(arr):
i = -1
for j in range(len(arr)):
if arr[j] < 0:
i += 1
arr[i], arr[j] = arr[j], arr[i]
pos, neg = i + 1, 0
while pos < len(arr) and neg < pos and arr[neg] < 0:
arr[neg], arr[pos] = arr[pos], arr[neg]
pos += 1
neg += 2
arr = [1, -2, 3, -4, -1, 4]
rearrange(arr)
print(arr)Python Output
[-2, 1, -4, 3, -1, 4]
Explanation
Example
Let's take arr = [2, 3, -4, -1, 6, -9]. First, we separate the negatives from positives by sending all negatives to the front and keeping all positives at the back. It is just like setting your desk so all red books are on one side and all blue books on the other. Later on, we are simply taking one positive and one negative and alternate them in place by swapping. The end result is [-4, 2, -1, 3, -9, 6] such that the negative and positive ones alternate.
Real-Life Analogy
Suppose you're creating a photo lineup and individuals in red shirts (negatives) and blue shirts (positives) need to alternate. You put them together separately first so it's less confusing to work with. Next, you arrange them in order: red, blue, red, blue… Then, the lineup is balanced and tidy without someone having to move far from their original group.
Why It Matters
Alternating between positive and negative numbers is one typical data arrangement problem in competitive programming and actual projects, particularly when there are two kinds of data elements to balance in a regular pattern. It is a stable rearrangement problem in which you are not permitted to use additional space of more than constant memory, so it is harder.
Step-by-Step Logic
We initially sort the array in a modified Dutch National Flag fashion or using the Lomuto partition scheme. This places all the negatives in front of positives. Next, beginning from index 0 (negative side) and index pos (positive side), we interchange elements such that they alternate in the final order. Both operations being in-place, we don't require an additional array.
Common Beginner Mistakes
The beginners then attempt putting positives and negatives into two different arrays and then combining them. Although simpler, it requires O(n) extra space. Alternating pairs without separating first is also another mistake and doesn't work when positives and negatives get all bunched together.
Complexity and Optimization
This algorithm runs in O(n) time because both partitioning and alternating take one pass each. Space complexity is O(1) because all we used was a few variables to hold swapping indexes. This is the most optimal approach under the constraints of the problem.
Real-World Applications
This logic shows up in problems like:
Balancing load between two types of servers, such as GPU-heavy versus CPU-heavy tasks.
Alternating signs in mathematical calculations to stabilize.
Ordered datasets for machine learning training where interweaving features enhances diversity in batches.
Interview Insights
In interviews, this issue evaluates array manipulation without additional space and two-pointer strategies. If the interviewer requests "O(1) extra space," it's a clue to apply partitioning along with swapping. You can wow them by pointing out how the first phase is similar to quicksort's partition and how the second phase is similar to merging two linked lists in place.
Learning Insights
The most important thing is learning to divide problems into sub-problems. In this case, "separate by sign" and "alternate in place" are simpler to understand separately, but when combined, they efficiently solve a more difficult problem.
SEO-Friendly Closing
Shuffling an array to alternate positive and negative numbers without additional space is a crucial skill to learn for in-place algorithms and two-pointer methods in data structure and algorithms. This technique is guaranteed to have a neat O(n) time complexity and O(1) space complexity, which makes it perfect for competitive coding, coding interviews, and optimization-driven projects. Knowing this technique will benefit in problems needing balanced alternation, in-place shuffling, and partition-based array transformations.
Social Plugin