DEV Community

loading...
Cover image for ⚖️ Segregate negatives and positives ⚖️

⚖️ Segregate negatives and positives ⚖️

kaiwalyakoparkar profile image Kaiwalya Koparkar ・2 min read

Question:

An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers.

Examples:

Input: -12, 11, -13, -5, 6, -7, 5, -3, -6
Output: -12 -13 -5 -7 -3 -6 11 6 5
Enter fullscreen mode Exit fullscreen mode

Note: Order of elements is not important here.

Logic:

  1. Sorting :

    • Take the input as the array
    • sort the array. ( Either inbuilt or self implemented )
    • all the negatives will be seperated from the positives
  2. 0 Reference :

    • Take the input as array
    • Declare two pointers i and j
    • i will move from arr [ 0 ]th location to arr [ arr.length - 1 ]th location. in this it will check if arr [ i ] < 0 and i is not equal to j . if yes, then it will swap arr [ i ] and arr [ j ]
    • if no, then it will simply increment j
    • when both i and j will reach the last position, the loop will stop
    • print the array
import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sortArr[] = new int[n];
        int zeroRef[] = new int[n];
        for(int i = 0; i < sortArr.length; i++){
            sortArr[i] = sc.nextInt();
            zeroRef[i] = sortArr[i];
        }

        //This is sorting solution
        Arrays.sort(sortArr);
        System.out.println("Segregation through sorting is: ");
        for(int i = 0; i < sortArr.length; i++){
            System.out.print(sortArr[i]+" ");
        }
        System.out.println();

        //This is 0 reference solution
        int j = 0;
        for(int i = 0; i < zeroRef.length; i++){
            if(zeroRef[i] < 0){
                if(i != j){
                    int temp = zeroRef[i];
                    zeroRef[i] = zeroRef[j];
                    zeroRef[j] = temp;
                }
                j++;
            }
        }

        System.out.println("Segregation through 0 reference method is: ");
        for(int i = 0; i < zeroRef.length; i++){
            System.out.print(zeroRef[i]+" ");
        }
        System.out.println();
    }
}
Enter fullscreen mode Exit fullscreen mode

Discussion (2)

pic
Editor guide
Collapse
aarone4 profile image
Aaron Reese

Use array filter to compare i to abs(i) and separate into two arrays then spread the two new arrays into a single array. Original order is preserved and cost is 2N +1

Collapse
kaiwalyakoparkar profile image
Kaiwalya Koparkar Author

Thanks for that solution. I'll definetly try that out!