# Segregate positive and negative numbers in Array

Given an array arr[] with length n, the task is to rearrange the array is such a way so that the output array should contain all the negative elements in the starting of the array followed by all positive integers.

arr[] = {1, -3, 2, 5, -6, -10, 5, -7}
Output:

We can solve this problem in O(n) time using two pointers, the idea is to maintain two pointers start and end at both ends of the array. Start iterating from start = 0 and end = n-1; until start < end, in each iteration if arr[i] is positive we will keep decreasing the value of end pointer until we find a negative value, replace arr[start] with arr[end].

```package com.cd.array;

import java.util.Arrays;

public class SegregatePositiveAndNegative {

private static int arr[] = {1, -3, 2, 5, -6, -10, 5, -7};

private static void segregate(int arr[], int n) {

int start = 0, end = n - 1;

outer : while (start < end) {
if (arr[start] > 0) {
while (arr[end] > 0) {
end--;
if (end < start)
break outer;
}

int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
start++;
}

}

public static void main(String[] args) {
System.out.println("Input Array:");
printArray(arr);

segregate(arr, arr.length);

System.out.println();
System.out.println("Segregated Array:");
printArray(arr);

}

private static void printArray(int arr[]) {
Arrays.stream(arr).forEach(i -> System.out.print(i + ", "));
}

}
```
Time Complexity: O(n)
Space Complexity: O(1)

Output: Output of above shown example will be something like this:

``````
Input Array:
1, -3, 2, 5, -6, -10, 5, -7,
Segregated Array:
-7, -3, -10, -6, 5, 2, 5, 1,
``````