## Arrays With Elements In The Range 1 to N

When an array has all its elements in the range of 1 to N ( where N is the length of the array ) we can use the indices to store the ordered state of the elements in the array. This ordered-state can in-turn be used to solve a variety of problems which we’ll explore soon. First, a very simple demonstration of this property.

Here is an array which has unique elements in the range of 1 to N.
Given array (A) : 5,3,1,4,2
Indices:                0,1,2,3,4

Sort in Linear Time

The first use-case of this unique property is being able to sort in O(N) time i.e. a special-case(all unique elements) of the Counting Sort. The crux of this sort is to check whether an element is at its corresponding index and swap it to its correct index if it’s not. Following is a demonstration of this logic:

Given array (A) : 5,3,1,4,2
Indices:                0,1,2,3,4

For each A[i] check if A[A[i] – 1] equals A[i] or not. If they are not equal then swap element at A[A[i] – 1] with A[i]. Basically the correct value for any index i is when A[i] contains i+1.

A[A[0] – 1] or A[5-1] orA[4] which is 2 and A[0] = 5. This means that A[A[i] – 1] is not equal to A[i] and hence not in its correct position. So we need to swap in order to put A[0] -> 5 to its correct position which is index 4 and A[0] will hold 4 after the swap. Similarly, we need to repeat this check & swap for all the elements.

What if we cancel-out the common terms and modify the check from  `A[i] != A[A[i] - 1]` to `i != A[i]-1` ?

Find The Missing Integer

A similar approach can help us find the smallest missing positive-integer in a given array. By smallest missing positive-integer, we just mean the smallest positive integer that does not exist in the given list of numbers. For example:

Given Array: `-2, 3, 0, 1, 3`
In the above case, the smallest missing positive integer is 2.

If we were to apply the usual sorting techniques and then scan the array for the smallest positive integer absent it would imply a time-complexity of O(NLog(N)) + O(N). We can definitely do better than this! At first glance, it seems that this problem does not lie within the unique property of elements being in the range of 1 to N since the numbers in the given array are well outside the range, but to solve this problem we still only need to figure out whether we have elements from 1 to N present in the given array or not.

How do we know whether the given array has elements from 1 to N? We can use the counting-sort discussed earlier to put each element in its “correct position”, i.e index 0 should hold 1, index 1 should hold 2 and so on. The smallest index that does not hold its correct element is the missing integer.

If we sort the given array using counting sort described above, we will get: `1, 0, 3, -2, 3`. And the smallest index `i` to not hold its correct value i.e. `i+1` will give us the answer to the smallest missing positive integer. In this case, that index is 1 since it does not hold 2, thus the smallest positive missing integer is 2.

Find The Duplicate Element

The third use-case of this property is to figure out the duplicate elements without using any extra space. We can iterate over the array A and mark the corresponding index of the encountered element as negative – unless it has already been marked negative! For example: if A[1] = 3 (or -3 ) then mark `A[ Abs[3] - 1]` as negative, this way whenever we encounter 3 (or -3) again in any of the A[i] we will know that the value 3 has been visited before since A[3-1] will be negative.

Given array (A) : 5,3,1,4,3
Indices:                0,1,2,3,4

When we encounter A[0] i.e. 5, we make A[5-1] i.e. A[4] negative, so the array becomes:
`5,3,1,4,-3`
Next, we encounter A[1] i.e. 3, we make A[3-1] i.e. A[2] negative, so the array becomes:
`5,3,-1,4,-3`
Next, we encounter A[2] i.e. -1, we make A[1-1] i.e. A[0] negative, so the array becomes:
`-5,3,-1,4,-3`
Next, we encounter A[3] i.e. 4, we make A[4-1] i.e. A[3] negative, so the array becomes:
`-5,3,-1,-4,-3`
Next, we encounter A[4] i.e. -3, we want to make A[3-1] i.e. A[2] negative, but in this case, A[2] is already negative thus we know that A[2] has been visited before! Which means `Abs(A[4])` i.e 3 is the duplicate element.

Here is a snippet to demonstrate the code for sorting an array in linear time as per the above approach. The exact same approach can be used to solve the other two applications i.e. Finding the Duplicate and Finding The Missing Integer.

```        int swap=0;

for(int i = 0; i < nums.length;){

if(nums[i] > 0 && nums[i] < nums.length) {

if(nums[nums[i]-1] != nums[i]){
swap = nums[i];
nums[i] = nums[nums[i] - 1];
nums[swap - 1] = swap;
}else{
i++;
}

}else{
i++;
}
}
```

If you are preparing for a technical interview in companies like Amazon, Facebook, etc and want help with preparation, please register for a coaching session with us.

## Find Kth smallest element in array

Given an array of integers which is non sorted, find kth smallest element in that array. For example: if input array is A = [3,5,1,2,6,9,7], 4th smallest element in array A is 5, because if you sort the array A, it looks like A = [1,2,3,5,6,7,9] and now you can easily see that 4th element is 5.

This problem is commonly asked in Microsoft and Amazon interviews as it has multiple layers and there are some many things that can be tested with this one problem.

## Kth smallest element : Line of thought

First of all, in any interview, try to come up with brute force solution. Brute force solution to find Kth smallest element in array of integers would be to sort the array and return A[k-1] element (K-1 as array is zero base indexed).

What is the complexity of brute force solution? It’s `O(n2)`? Well, we have sort algorithms like merge sort and heap sort which work in O(nlogn) complexity.

The problem with both searches is that they use additional space. Quick sort is another sorting algorithm. It has problem that it’s worst-case complexity will be `O(n2)`, which happens when input is completely sorted.
In our case, the input is given as unsorted already, so we can expect that quicksort will function with `O(n log n)` complexity which is its average-case complexity. Advantage of using quicksort is that there is no additional space complexity.

Optimising quick sort

Let’s see how quicksort works and see if we can optimize solution further?
Idea behind quicksort is to find the correct place for the selected pivot. Once the pivot is at the correct position, all the elements on the left side of the pivot are smaller and on the right side of the pivot are greater than the pivot. This step is partitioning.

If after partitioning, pivot is at position j, can we say that pivot is actually jth smallest element of the array? What if j is equal to k? Well problem solved, we found the kth smallest element.

If j is less than k, left subarray is less than k, we need to include more elements from right subarray, therefore kth smallest element is in right subarray somewhere. We have already found j smallest elements, all we need to find is k-j elements from right subarray.

What if j is greater than k? In this case, we have to drop some elements from left subarray, so our search space would be left subarray after partition.

Theoretically, this algorithm still has the complexity of `O(n log n)`, but practically, you do not need to sort the entire array before you find k smallest elements.

If you are preparing for a technical interview and need personal coaching along with mock interviews, book a free demo session with us

### Algorithm to find Kth smallest element in array

1. Select a pivot and partition the array with pivot at correct position j
2. If position of pivot, j, is equal to k, return A[j].
3. If j is less than k, discard array from start to j, and look for (k-j)th smallest element in right sub array, go to step 1.
4. If j is greater than k, discard array from j to end and look for kth element in left subarray, go to step 1

Let’s take an example and see if this algorithm works? A =  [4, 2, 1, 7, 5, 3, 8, 10, 9, 6 ], and we have to find fifth smallest element in array A.

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

In our example, array A will look like below after pivot has found it’s the correct position.

If pivot == k-1 (array is represented as zero base index), then A[pivot] is kth smallest element. Since pivot (3) is less than k-1 (4), look for kth smallest element on right side of the pivot.

k remains as it is as opposed to k-j mentioned in algorithm as pivot is given w.r.t entire array and not w.r.t subarray.

In second iteration, pivot = 4 (index and not element). After second execution of quick sort array A will be like

pivot(4) which is equal to k-1(5-1). 5th smallest element in array A is 5.

### Implementation

```package com.company;

/**
* Created by sangar on 30.9.18.
*/
public class KthSmallest {
private void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int partition(int[] a, int start, int end){
int pivot = a[start];
int i  = start+1;
int j  = end;

while(i <= j){
while(a[i] < pivot) i++;
while(a[j] > pivot) j--;

if(i < j) {
swap(a, i, j);
}
}
swap(a, start, j);
return j;
}

public int findKthSmallestElement(int a[], int start,
int end, int k){
if(start <= end){
int p = partition(a, start, end);
if(p == k-1){
return a[p];
}
if(p > k-1)
return findKthSmallestElement(a, start, p, k);
if(p < k-1)
return findKthSmallestElement(a, p+1, end, k);
}
return -1;
}
}
```

Test cases

```package test;

import com.company.KthSmallest;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 28.8.18.
*/
public class KthSmallestTest {

KthSmallest tester = new KthSmallest();
private int[] a = {4, 2, 1, 7, 5, 3, 8, 10, 9};
@Test
public void kthSmallest() {
assertEquals(7, tester.findKthSmallestElement(a,0,8,6));
}

@Test
public void firstSmallest() {
assertEquals(1, tester.findKthSmallestElement(a,0,8,1));
}

@Test
public void lastSmallest() {
assertEquals(10, tester.findKthSmallestElement(a,0,8,9));
}

@Test
public void kGreaterThanSize() {
assertEquals(-1, tester.findKthSmallestElement(a,0,8,15));
}
@Test
public void emptyArray() {
int[] a = {};
assertEquals(-1, tester.findKthSmallestElement(a,0,0,1));
}

@Test
public void nullArray() {
assertEquals(-1, tester.findKthSmallestElement(null,0,0,1));
}
}
```

Complexity of using quicksort algorithm to find the kth smallest element in the array of integers is still O(n logn).

### Kth smallest element using heaps

Before going into details of this problem, I strongly recommend reading heap fundamentals.

Imagine a case where there are a billion integers in the array and you have to find 5 smallest elements from that array. The complexity of O(n log n) is too costly for that use case. Above algorithm using quicksort does not take into consideration disparity between k and n.

We want top k elements, how about we chose those k elements randomly, call it `set A` and then go through all other n-k elements, call it `set B`, check if element from set B (n-k elements) can displace element in set A (k elements)?

What will be the condition for an element from set B to replace an element in set A? Well, if the new element is less than maximum in set A than the maximum in set A cannot be in the set of k smallest elements right?  Maximum element in set A would be replaced by the new element from set B.

Now, the problem is how to quickly find the maximum out of set A. Heap is the best data structure there. What kind of heap: min heap or max heap? Max heap as it store the maximum of the set at the root of it.

Let’s defined concrete steps to find k smallest elements using a max heap.

1. Create a max heap of size k from first k elements of array.
2. Scan all elements in array one by one.
1.  If current element is less than max on heap, add current element to heap and heapify.
2. If not, then go to next element.
3. At the end, max heap will contain k smallest elements of array and root will be kth smallest element.

Let’s take an example and see if this algorithm works? The input array is shown below and we have to find the 6th smallest element in this array.

Step 1 : Create a max heap with first 6 elements of array.

Step 2: Take the next element from set B and check if it is less than the root of max heap. In this case, yes it is. Remove the root and insert the new element into max heap.

Step 2: It continues to 10, nothing happens as the new element is greater than the root of max heap. Same for 9.  At 6, again the root of max heap is greater than 6. Remove the root and add 6 to max heap.

Array scan is finished, so just return the root of the max heap, 6 which is the sixth smallest element in given array.

### Implementation

```	public int findKthSmallestElementUsingHeap(int a[], int k){
//https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue

PriorityQueue<Integer>  maxHeap =
new PriorityQueue<>(k, Collections.reverseOrder());

if(a == null || k > a.length) return -1;
//Create max with first k elements
for(int i=0; i<k; i++){
}

/*Keep updating max heap based on a new element
If new element is less than root,
remove root and add new element
*/

for(int i=k; i<a.length; i++){
if(maxHeap.peek() > a[i]){
maxHeap.remove();
}
}
return maxHeap.peek();
}
```

Can you calculate the complexity of above algorithm? `heapify()` has complexity of log(k) with k elements on heap. In worst case, we have to do `heapify()` for all elements in array, which is n, so overall complexity of algorithm becomes O(nlogk). Also, there is additional space complexity of O(k) to store heap.
When is very small as compared to n, this algorithm again depends on the size of array.

We want k smallest elements, if we pick first k elements from a min heap, will it solve the problem? I think so. Create a min heap of n elements in place from the given array, and then pick first k elements.
Creation of heap has complexity of O(n), do more reading on it. All we need to do is delete k times from this heap, each time there will be `heapify()`. It will have complexity of O(log n) for n element heap. So, overall complexity would be O(n + klogn).

Depending on what you want to optimize, select correct method to find kth smallest element in array.

Please share if there is something wrong or missing. If you are interested in taking coaching sessions from our experienced teachers, please reach out to us at [email protected]

# Quick sort Algorithm

Quicksort like merge sort is a sorting algorithm under divide and conquer paradigm of algorithms like merge sort. The basic idea of the algorithm is to divide inputs around a pivot and then sort two smaller parts recursively and finally get original input sorted.

### Selection of pivot

The entire idea of quicksort revolves around a pivot. Pivot is an element in input around which input is arranged in such a way that all elements on the left side are smaller and all elements on the right side are greater than the pivot. The question is how to find or select pivot and put it into the correct position.

To make things simpler to start with, let’s assume that the first element of the input is pivot element.

To put this pivot at the correct position in input, start with the next element of pivot in input space and find the first element which is greater than pivot. Let that be ith position.

At the same time, start from end of the array and find first element which is smaller than pivot. Let it be jth position.

If i and j have not crossed each other i.e i < j, then swap element at ith and jth positions, and continue moving right on input to find element greater than pivot and moving left to find element smaller than pivot.
Once i and j cross each other, swap pivot with element at jth position.  After this step, pivot will be at its correct position and array will be divided into two parts. All elements on left side will be less than pivot and all elements on right side will be greater than pivot.

### Quick sort partition example

This is too much to process, I know! Let’s take an example and see how it does it work? We have an array as follows

Let’s select first element as pivot, pivot = 3.

Start from the next element of the pivot, move towards the right of the array, till we see the first element which is greater than pivot i.e. 3.

From end of the array, move towards left till you find an element that is less than the pivot.

Now, there are two indices, i and j, where A[i] > pivot and A[j] < pivot. See that i and j not yet crossed each other. Hence, we swap A[i] with A[j]. Array at the bottom of pic, shows resultant array after swap.

Again, start with i+1 and follow the same rule: Stop when you find an element greater than the pivot. In this case, 10 is greater than 3, hence we stop.

Similarly, move left from the end again, until we find an element which is less than the pivot. In this case, we end up at index = 2 which is element 1.

Since `i > j`, then means paths have been crossed. At this time, instead of swapping element at i and j index, swap element at j index with pivot.

After swapping pivot with jth index, we have array divided into two parts, pivot as a boundary. All elements on the left side of the pivot are smaller (they may not be sorted) and all elements on the right side of the pivot are greater than pivot (again may not be sorted).

We, apply this same partition process to left and right arrays again, till the base condition is hit. In this case, the base condition would be if there is only one element in the array to be partitioned.

### Quick sort algorithm

quickSort([], start, end)
1. If array has more than one elements i.e (start < end):
1.1 Find correct place for pivot.
pivot = partition(arr, low, high)
1.2. Apply same function recursively to left of pivot index
quickSort(arr, start, pivot -1 )
and to the right of pivot index
quickSort(arr, pivot + 1, end)

### Quick sort implementation

```package AlgorithmsAndMe;

public class QuickSort {

private void swap(int [] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

private int partition(int [] a, int start, int end){
int pivot = a[start];
int i  = start;
int j  = end;

while(i < j){
while(i <= end && a[i] <= pivot) i++;
while(j >= start && a[j] > pivot) j--;

if(i < j) {
swap(a, i, j);
}
}

swap(a, start, j);
return j;
}

public void quickSort(int [] a, int start, int end){
if(start < end){
int p = partition(a, start, end);
quickSort(a,start, p-1);
quickSort(a, p+1, end);
}
}
}

```

There is another implementation that is based on the Lomuto partition scheme, in this scheme, we make the last element as pivot. The implementation is compact but complexity is a bit higher than the original partition methods in terms of the number of swaps.

```#include<stdlib.h>
#include<stdio.h>

void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int a[], int low, int high)
{
// set pivot as highest element
int x  = a[high];

//Current low points to previous of low of this part of array.
int i = low - 1;

for (int j = low; j <= high-1; j++)
{
/*Move in the array till current node data is
less than the pivot */
if (a[j] <= x){
//set the current low appropriately
i++;
swap(&a[i], &a[j]);
}
}
//Now swap the next node of current low with pivot

swap(&a[i+1], &a[high]);

printf("\n Pivot : %d\n", a[i+1]);
for(int j=0; j<=high; j++){

printf("%d ", a[j]);
}
//return current low as partitioning point.
return i+1;
}

/* A recursive implementation of quicksort for linked list */
void quickSortUtil(int a[], int low, int high)
{
if (low < high)
{
int p = partition(a,low, high);
quickSortUtil(a,low, p-1);
quickSortUtil(a, p+1, high);
}
}

/* Driver program to run above code */
int main(){

int a[] = {5,4,2,7,9,1,6,10,8};

int size = sizeof(a)/sizeof(a[0]);
quickSortUtil(a, 0, size-1);

for(int i=0; i<size; i++){
printf("%d ", a[i]);
}
return 0;
}
```

### Complexity analysis of quick sort algorithm

If pivot splits the original array into two equal parts (which is the intention), the complexity of quicksort is O(nlogn). However, worst-case complexity of quick sort happens when the input array is already sorted in increasing or decreasing order. In this case, array is partitioned into two subarrays, one with size 1 and other with size n-1. Similarly, subarray with n-1 elements, it again is divided into two subarrays of size 1 and n-2. In order to completely sort the array, it will split for n-1 times, and each time it requires to traverse n element to find the correct position of pivot. Hence overall complexity of quick sort comes out as O(n2).

There is a very interesting question, which tests your understanding of system basics. Question is what is the space complexity of this algorithm? There is no apparent memory is used. However, recursive implementation internally puts stack frames on the stack for partitioned indices and function call return addresses and so on. In the worst case, there can be n stack frames, hence worst-case complexity of quicksort will be O(n).

How can we reduce that? If the partition with fewest elements is (recursively) sorted first, it requires at most O(log n) space. Then the other partition is sorted using tail recursion or iteration, which doesn’t add to the call stack. This idea, was described by R. Sedgewick, and keeps the stack depth bounded by O(log n) and hence space complexity will be O(log n).

## Quick sort with tail recursion

```Quicksort(A, p, r)
{
while (p < r)
{
q = Partition(A, p, r)
Quicksort(A, p, q)
p = q+1
}
}
```

Selection of Pivot
If an array is completely sorted, then the worst-case behavior of quicksort is O(n2), so there comes another problem. How can we select pivot so that two subarrays are almost equal size? There are many solutions proposed.
1. Taking median of the array as a pivot. So how to select the median of an unsorted array. We look into this problem separately, but yes it guarantees two halves of the same size.
2. Selecting pivot randomly. This requires heuristics algorithms to select pivot.

Please leave your comment in case you find something wrong or you have some improved version.

# Count sort : Sorting in linear time

Are there any sorting algorithm which has worst case complexity of O(n)? There are a few like count sort and decision tree algorithms. In this post we would discuss about count sort and couple of problems where this counting sort algorithm can be applied.

Counting sort was invented by Harold H. Seward
To apply counting sort, we need to keep in mind following assumptions:

1. There should be duplicate values in the input
2. There should be at most K different type of values in input.
3. The input data ranges in 0 to K

Count sort goes for O(n2) if K is very close to n i.e. a very few elements are duplicate and rest all are unique. So above three conditions are necessary to have this algorithm work in linear time.

Count Sort -Approach
Let’s see how does it work? There are three steps involved in the algorithm:

• Sampling the data, counting the frequencies of each element in the input set.
• Accumulating frequencies to find out relative positions of each element.
• Third step distributes each element to its appropriate place.
• Now let’s take one example and go through the above three steps:
Input is  an array A = [1,2,3,2,2,3,3,1,1,1,1,3,2,2]. Here we can see that K=3. Now let’s perform the first step of the method, i.e. count the frequency of each element. We keep a hash and keep track of each element’s count. Since values are upper bound by K, we need at most K sized hash. We initialize this hash as zero. A is input array and n is the size of the array.

```int char count [K];

for(i=0; i<K;i++){
count[i]=0;
}

for(i=0;i<n;i++){
count[a[i]]++;
}
```

Count looks likes count =[5,5,4]. The complexity of this step is O(n). The second step involves the accumulation of frequencies where we add frequencies of previous elements to the current element.
F(j) = summation of f[i] for all i=0

```F(j) = summation of f[i] for all i<=j and i>=0

for(i=1;i<K;i++){
Count[i] +=count[i-1];
}
```

The second step runs for K times hence the complexity of O(K). The third step involves distribution. Let’s create an output array called as B of size n For every element in A we check the corresponding count in count array and place the element at that position. So, first 1 will be at position 4 (there are total 5 and array is an index from 0), the first two will be placed at 9 and the first three will be at 13. Subsequently, lower positions will be filled as we encounter them in the input array.

```for(i=0; i<n;i++){
B[--count[a[i]]] = a[i];
}
```

This step has complexity of O(n)

```#include<stdlib.h>
#include<stdio.h>

void count_sort(int a[], int n, int K){

int count [K];
int i,j;
int b[n];
for(i=0; i<=K;i++){
count[i]=0;
}

for(i=0;i<n;i++){
count[a[i]]++;
}

for(i=1;i<=K;i++){
count[i] +=count[i-1];
}
for(j=0;j<n;j++){
b[j]=0;
}

for(i=0; i<n;i++){
count[a[i]]--;
b[count[a[i]]] = a[i];
}
}
int main(){
int a[]= {0,1,1,1,0,0,0,3,3,3,4,4};
int n  =  sizeof(a)/sizeof(a[0]);

count_sort(a,n,4);
}
```
```Iter 0 :0  0  0  0  1  0  0  0  0  0  0  0  0  0
Iter 1 :0  0  0  0  1  0  0  0  0  2  0  0  0  0
Iter 2 :0  0  0  0  1  0  0  0  0  2  0  0  0  3
Iter 3 :0  0  0  0  1  0  0  0  2  2  0  0  0  3
Iter 4 :0  0  0  0  1  0  0  2  2  2  0  0  0  3
Iter 5 :0  0  0  0  1  0  0  2  2  2  0  0  3  3
Iter 6 :0  0  0  0  1  0  0  2  2  2  0  3  3  3
Iter 7 :0  0  0  1  1  0  0  2  2  2  0  3  3  3
Iter 8 :0  0  1  1  1  0  0  2  2  2  0  3  3  3
Iter 9 :0  1  1  1  1  0  0  2  2  2  0  3  3  3
Iter 10 :1  1  1  1  1  0  0  2  2  2  0  3  3  3
Iter 11 :1  1  1  1  1  0  0  2  2  2  3  3  3  3
Iter 12 :1  1  1  1  1  0  2  2  2  2  3  3  3  3
Iter 13 :1  1  1  1  1  2  2  2  2  2  3  3  3  3

Final O/P :1  1  1  1  1  2  2  2  2  2  3  3  3  3
```

Total complexity of the algorithm being O(K)+ O(n) + O(K) +O(n) = O(K+n). Please refer to the master theorem, how this is derived. Now if we see, K+n remains in order of n till the time K<n, if K goes on to n^2, the complexity of algorithm goes for polynomial time instead of linear time.

There is immediate application of this algorithm in following problem:
Let’s there is an array which contains Black, White and Red balls, we need to arrange these balls in such a way that all black balls come first, white second and Red at last. Hint: assign black 0, white 1 and Red 2 and see. 🙂

In the next post, we would discuss how extra space can be saved, how initial positions of elements can be maintained. We would go through an interesting problem to discuss the above optimization.

Why this filling from the end of the span? Because this step makes count sort stable sort. Here we have seen a sorting algorithm which can give us o/p linear time given some particular conditions met on the i/p data.