ISI 2019 | PCB CS | Question: 11

Question

Consider an array of length $n$ consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only constant amount of extra space.

Answer 1

Lets the array A of size n be given as input (we assume that 0 isnt present as only positive and negative integers are considered)

Swap(x,y) swaps the value of x and y in O(1)

1. Set int i to 0
2. while(A[i] < 0) i = i+1; // this is to ensure that i is set to first positive number appearing in array
3. Set j to i

while(j<n){

if( A[j]<0) {swap(A[i],A[j]); i++;}

else j++;

}

 the loop checks if A[j] is less than 0 or not, when negative it swaps and increments the i which moves to next position and if positive i stays while j is incremented.

this runs till the end of array. the whole algo takes order of n.

Comments

Personally I liked the algorithm – those who can give such algorithms will find GATE an easy exam.

9,-1,-2,-3,-4

For this array the given algorithm won’t give optimal number of swaps right?

---

You are right, i didn’t consider such configurations. it seems my algo gives worst case for configuration as positive first then negative.

Thanks for pointing it out!

---

@Arjun sir

How exactly your algo works i mean

say A[0] is pointed by F and A[n-1] is pointed by L

now 

1. if ( *L < 0 && *F < 0 ) increment F till we see that *F > 0 and swap *F,*L
2. if ( *L > 0 && *F > 0 ) decrement L till we see that *L < 0 and swap *F,*L
3. if ( *L > 0 && *F < 0 ) decrement L and increment F
4. if ( *L < 0 && *F > 0 ) swap *F,*L now decrement L and increment F

is this what you are saying

 

i personally thought of using the similar approach to partition algo in Quick sort which gives same no of swaps and comparisons as this approach 

Answer 2

#include<stdio.h>
int main(){
int a[]={-1,5,2,-9,10,8};
int i=0,j=0,n=sizeof(a)/sizeof(int);

while(j<n) {
if(a[i]<a[j]){
int x=a[i];
a[i] = a[j];
a[j] = x;
}
j++;
if(j>=n){
i = i+1;
j=0;
}
if(i==n){
break;
}

}
for (int k = 0; k < n; ++k) {
printf("%d \t", a[k]);
}
}

Answer 3

function rearrangeArray(arr):
    left = 0
    right = length of arr - 1

    while left <= right:
        # Move left pointer to the right until a positive number is found
        while left <= right and arr[left] < 0:
            left = left + 1
        
        # Move right pointer to the left until a negative number is found
        while left <= right and arr[right] > 0:
            right = right - 1
        
        # If left is still less than right, swap the elements
        if left < right:
            swap arr[left] and arr[right]
            left = left + 1
            right = right - 1
 

Answer 4

 The key is to partition the array based on the sign of the integers—negative or positive—without relying on additional data structures or sorting methods that exceed the time and space constraints.

Algorithm Description

The approach uses a single pass through the array with two pointers: 

1. one to traverse the array and 
2. another to track the position where the next negative integer should be placed. Here’s how it works:

1. Initialize a pointer \( k \) to 0: This pointer \( k \) represents the index where the next negative integer should be placed. Initially, it starts at the beginning of the array (index 0).

2. Iterate through the array with pointer \( i \) from 0 to \( n-1 \): This pointer \( i \) scans each element of the array in sequence.

3. Check each element \( A[i] \):

• If \( A[i] < 0 \)           (i.e., the element is negative), swap \( A[i] \) with the element at \( A[k] \), and then increment \( k \) by 1. This action moves the negative integer to the front portion of the array and advances the boundary between negatives and positives.
• If \( A[i] > 0 \)           (i.e., the element is positive), do nothing and move to the next index \( i \).

Final ALGORITHM

Set k = 0.
for i = 0 to n-1 :
   if A[i] < 0 , 
   {      swap  A[i] with A[k]  
          increment  k 
    }
Return the rearranged array.

---

Time Complexity: 

The algorithm performs a single pass through the array with \( i \) from 0 to \( n-1 \), and each swap operation is \( O(1) \). Thus, the total time complexity is \( O(n) \).

Space Complexity 

Only two variables are used: \( k \) and \( i \), along with a possible temporary variable for swapping (if not using a language feature like tuple unpacking). This is a constant amount of extra space, satisfying the \( O(1) \) requirement.

Boundary Cases needed to be define for complete understanding

• Empty array (\( n = 0 \)): The loop does not execute, and the array remains empty, which is trivially correct.
• Single element (\( n = 1 \)): If the element is positive (e.g., \( [5] \)) or negative (e.g., \( [-5] \)), no swaps occur, and the array is already in the correct form.
• All positive or all negative: For \( [1, 2, 3] \), no elements are negative, so no swaps occur, and the array is unchanged (correct since there are no negatives). For \( [-1, -2, -3] \), each element is swapped with itself as \( k \) advances, leaving the array unchanged (correct since there are no positives).

Assumptions and Clarifications

The problem specifies “positive and negative integers,” implying that zeros (neither positive nor negative) are not present. If zeros were included, their placement would be ambiguous, but since the problem doesn’t address this, we assume the array contains only non-zero integers. The algorithm does not preserve the relative order of negatives or positives, which is acceptable as the problem does not require it.

Dry Run

Consider the array \( [3, -1, 4, -2, 5, -3] \):

- Initial state: \( [3, -1, 4, -2, 5, -3] \), \( k = 0 \), \( i = 0 \)
- \( i = 0 \): \( A[0] = 3 > 0 \), no swap, \( k = 0 \)
- \( i = 1 \): \( A[1] = -1 < 0 \), swap \( A[1] \) with \( A[0] \) (i.e., -1 with 3), array becomes \( [-1, 3, 4, -2, 5, -3] \), \( k = 1 \)
- \( i = 2 \): \( A[2] = 4 > 0 \), no swap, \( k = 1 \)
- \( i = 3 \): \( A[3] = -2 < 0 \), swap \( A[3] \) with \( A[1] \) (i.e., -2 with 3), array becomes \( [-1, -2, 4, 3, 5, -3] \), \( k = 2 \)
- \( i = 4 \): \( A[4] = 5 > 0 \), no swap, \( k = 2 \)
- \( i = 5 \): \( A[5] = -3 < 0 \), swap \( A[5] \) with \( A[2] \) (i.e., -3 with 4), array becomes \( [-1, -2, -3, 3, 5, 4] \), \( k = 3 \)
- Final array: \( [-1, -2, -3, 3, 5, 4] \)

The result has all negatives (\( -1, -2, -3 \)) before all positives (\( 3, 5, 4 \)), as required.

By the end of this process, all negative integers will be positioned at indices 0 through \( k-1 \), and all positive integers will be at indices \( k \) through \( n-1 \).