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,