Hey there coder. Are you ready to discuss the question , "Partition An Array"? Leggo.

You need to first read the problem statement.

**Important Links : Problem Link, Solution Video**

Now we are ready to discuss the question.

Partition An Array

It's not what you achieve, it's what you overcome. That's what defines your career.

Partition An Array

Hey there coder. Are you ready to discuss the question , "Partition An Array"? Leggo.

You need to first read the problem statement.

**Important Links : Problem Link, Solution Video**

Now we are ready to discuss the question.

Problem Discussion :

- You are given an array(arr) of integers and a pivot.
- You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side.
- You have to achieve this in linear time.

We understand this problem through an example when the given array is [7, 9, 4, 8, 3, 6, 2, 1] and the pivot is given as 5.

So we want all the elements less than or equal to the pivot i.e. 5 to appear on the left side and the greater elements on the right side.

Approach :

Now we discuss its algorithm.

In figure 1, you can see that we divided the space into 3 sections: unknown elements (u), greater elements (>) and less than equal to elements(<=). We also use 2 pointers i and j which are initially at the first element of the array.

Now we define these 3 areas for iteration purposes. The less than equal elements are in the area 0 to j-1, the greater elements are in the j to i-1 area and the unknown elements are in the i to end area as shown by Figure 2.

As you can see in the figure, at the moment when i is at the first element, i to the end covers the entire array. Hence, all the elements that are unknown right now are depicted by drawing a line across those elements.

Since j and i are at the same element then there is no area from j to i-1. So right now we don't have any element greater than the pivot.

Now for the main algorithm, we analyse arr[i]. If arr[i]>pivot then i is increased by 1 which means the unknown area is decreased by one and the area for greater elements is increased.

Else if arr[i]<=pivot, then we swap the elements at i and j and increment both i and j by one.Why do you think it is done?

This decreases the unknown area by one element, less than or equal to area increases and the size of the greater than area remains the same but the area gets shifted forward.

Why do we do all this? Our main aim is to totally finish the unknown area so that all the elements get partitioned into the appropriate sides.

Now that we have understood the algorithm and its working we try to write the code for the same.

import java.io.*;
import java.util.*;
public class Main {
public static void partition(int[] arr, int pivot){
int i=0;
int j=0;
while(i< arr.length){
if(arr[i]>pivot)
{
i++;
}
else if(arr[i]<=pivot)
{
swap(arr,i,j);
i++;
j++;
}
}
}
// used for swapping ith and jth elements of array
public static void swap(int[] arr, int i, int j) {
System.out.println("Swapping " + arr[i] + " and " + arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
int pivot = scn.nextInt();
partition(arr,pivot);
print(arr);
}
}

java; true";

Analysis

Now that we have discussed the algorithm, let's analyze it too.

We start the analysis from the first element 7 where i=0. Since 7>pivot i.e. 5, so as we have mentioned in the algorithm already we increment i by 1, hence i=1. Now the unknown area decreases by one element and the greater than area includes j to i-1 i.e. 0 to 0 . Hence 7 is included in the greater than area.

You might not have understood it through the first element. Let's iterate it for the second element now.

We now analyze 9 where i=1. Since 9>pivot therefore i is incremented by 1 so i=2. Now the unknown area again decreases by one element and the greater than area includes j to i-1 indices i.e. 0 to 1 as shown in figure 5.

Now for i=2, we analyze the third element 4. Since 4<=pivot therefore elements at i and j are swapped.Also i and j are incremented by 1. So i=2 stores 7 now and j=0 stores 4 on swapping. Thereafter , i++=3 and j++=1.

Hence the unknown area again decreases by one element and the less than equal area is for j to i-1 i.e. 1 to 2 . The greater than area gets shifted forward as shown in figure 6.

Let's see the figure for the fourth element now that you have got a hang of it.

Try to draw these figures for the rest of the elements.You should get a final figure that looks something like Figure 8.

At the end we see in figure 8 that all the elements less than equal to pivot are at the left side and the elements greater than the pivot are at the right side. Here the loop comes to an end when i goes to an index beyond the array and all the unknown elements are now known.

We highly suggest you watch the video "Partition An Array" for a better understanding of this iteration.

Time Complexity :

**O (n)**

This time complexity is linear because a recursion call is made and "while loop" is used.

SPACE COMPLEXITY :

** O (1)**

As no extra space is required, therefore space complexity is constant.

We hope that this question was clear to you. This question can definitely appear confusing at first but after practicing it a couple of times it would get crystal clear in your mind.

Do check out its solution video too.