Move all negative numbers to beginning of the array

Posted by N.K. Chauhan on Jan 05, 2022

An array A is given, A contains both positive and negative numbers in random order. The task is to rearrange the array elements so that all negative numbers appear before all positive numbers.

Example 1: Rearrange (-)ve elements to the left in : {1, -2, 3, -4, 5, -6, 7}

Input: {1, -2, 3, -4, 5, -6, 7}
Output: {-6,-2,-4,5,3,7,1}

Example 2: Rearrange (-)ve elements to the left in : {23, -12, 4, 74, -1, 9, -45}

Input: {23, -12, 4, 74, -1, 9, -45}
Output: {-45,-12,-1,74,9,4,23}


Solutions

Method 1: Dutch National Flag algorithm

In this approach we will use famous Dutch National Flag algorithm. The idea is to divide the array in two parts such that; [1 to low-1] will have (-)ve values, [low to high-1] will have mixed elements and [high to n] will have (+)ve elements.

Start with low=0, high=n-1 and traverse the array until low < high; if arr[low] < 0 increment low (low++) else swap arr[low] & arr[high] and decrement high (high--).

Complexity

The time complexity of this solution is O(n) and space complexity is O(1).

Related


Rain water trapping problem - O(n) time & O(n) space

Print all possible permutations of an Array in O(1) space

Word Break Problem (Using HashMap and DP)

Program to print Union of two sorted arrays

Merge two sorted arrays in O(1) space

Longest substring without repeating characters

Two Sum - return index of a pair of array elements with a given sum

Find a triplet in an array that sums to a given number

Count the number of inversions in an array - in O(n log n) time

Program to print Intersection of two sorted arrays

Print all Subsets (Power Set) of a given array