# Pigeonhole Sort

Pigeonhole Sort is a sorting algorithm that is used to sort a set of elements that have a small range of values. It is a simple and intuitive algorithm that is similar to counting sort in its approach.

The algorithm works by first determining the range of values that the input elements can take. Then, it creates an array of "pigeonholes" or "buckets" that correspond to each value in the range. Each element is then placed in its corresponding pigeonhole based on its value. Once all the elements have been placed in the pigeonholes, the algorithm iterates over the pigeonholes in order and puts the elements back into the original array in sorted order.

The time complexity of Pigeonhole Sort is O(n+k), where n is the number of elements to be sorted and k is the range of values. However, the algorithm requires additional space to create the array of pigeonholes, which can make it less efficient than other sorting algorithms for large input sizes or when the range of values is very large.

Pigeonhole Sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the input. It is also an in-place sorting algorithm, which means that it does not require any additional memory beyond the input array.

Here given code implementation process.

``````//C program for
//Sort array by using pigeonhole sort
#include <stdio.h>

//Find the minimum element of given array
int find_min(int arr[], int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] < result)
{
result = arr[i];
}
}
return result;
}
//Find the maximum element of given array
int find_max(int arr[], int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] > result)
{
result = arr[i];
}
}
return result;
}
// Perform the pigeonhole sort of given array
void pigeonhole_sort(int arr[], int size)
{
if (size < 1)
{
return;
}
int min = find_min(arr, size);
int max = find_max(arr, size);
int hole_range = max - min + 1;
int hole[hole_range];
//Loop controlling variables
int i = 0;
int j = 0;
//Set the initial hole value
for (i = 0; i < hole_range; ++i)
{
hole[i] = 0;
}
//Count the occurrences of array elements
for (i = 0; i < size; i++)
{
hole[arr[i] - min]++;
}
for (i = 0; i < hole_range; i++)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j++;
//reduce the existing occurrence
hole[i]--;
}
}
}
//print the array elements
void display(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
printf("  %d", arr[i]);
}
}
int main()
{
//Define the collection of integer elements
int arr[] = {
7,
2,
90,
4,
1,
3,
46,
-4,
-4,
12,
6,
3,
2
};
int size = sizeof(arr) / sizeof(arr[0]);
printf("After Sort : ");
display(arr, size);
pigeonhole_sort(arr, size);
printf("\nBefore Sort  : ");
display(arr, size);
return 0;
}``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````// Java program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
public int find_min(int[] arr, int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] < result)
{
result = arr[i];
}
}
return result;
}
//Find the maximum element of given array
public int find_max(int[] arr, int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] > result)
{
result = arr[i];
}
}
return result;
}
// Perform the pigeonhole sort of given array
public void pigeonhole_sort(int[] arr, int size)
{
if (size < 1)
{
return;
}
int min = find_min(arr, size);
int max = find_max(arr, size);
int hole_range = max - min + 1;
int[] hole = new int[hole_range];
//Loop controlling variables
int i = 0;
int j = 0;
//Set the initial hole value
for (i = 0; i < hole_range; ++i)
{
hole[i] = 0;
}
//Count the occurrences of array elements
for (i = 0; i < size; i++)
{
hole[arr[i] - min]++;
}
for (i = 0; i < hole_range; i++)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j++;
//reduce the existing occurrence
hole[i]--;
}
}
}
//print the array elements
public void display(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
System.out.print("  " + arr[i]);
}
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define the collection of integer elements
int[] arr = {
7,
2,
90,
4,
1,
3,
46,
-4,
-4,
12,
6,
3,
2
};
int size = arr.length;
System.out.print("After Sort : ");
obj.display(arr, size);
obj.pigeonhole_sort(arr, size);
System.out.print("\nBefore Sort  : ");
obj.display(arr, size);
}
}``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ program
// Sort array by using pigeonhole sort
class MySort
{
public:
//Find the minimum element of given array
int find_min(int arr[], int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] < result)
{
result = arr[i];
}
}
return result;
}
//Find the maximum element of given array
int find_max(int arr[], int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] > result)
{
result = arr[i];
}
}
return result;
}
// Perform the pigeonhole sort of given array
void pigeonhole_sort(int arr[], int size)
{
if (size < 1)
{
return;
}
int min = this->find_min(arr, size);
int max = this->find_max(arr, size);
int hole_range = max - min + 1;
int hole[hole_range];
//Loop controlling variables
int i = 0;
int j = 0;
//Set the initial hole value
for (i = 0; i < hole_range; ++i)
{
hole[i] = 0;
}
//Count the occurrences of array elements
for (i = 0; i < size; i++)
{
hole[arr[i] - min]++;
}
for (i = 0; i < hole_range; i++)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j++;
//reduce the existing occurrence
hole[i]--;
}
}
}
//print the array elements
void display(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
cout << "  " << arr[i];
}
}
};
int main()
{
MySort obj = MySort();
int arr[] = {
7 , 2 , 90 , 4 , 1 , 3 , 46 , -4 , -4 , 12 , 6 , 3 , 2
};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "After Sort : ";
obj.display(arr, size);
obj.pigeonhole_sort(arr, size);
cout << "\nBefore Sort  : ";
obj.display(arr, size);
return 0;
}``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````//Include namespace system
using System;
// C# program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
public int find_min(int[] arr, int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] < result)
{
result = arr[i];
}
}
return result;
}
//Find the maximum element of given array
public int find_max(int[] arr, int size)
{
int result = arr[0];
for (int i = 1; i < size; ++i)
{
if (arr[i] > result)
{
result = arr[i];
}
}
return result;
}
// Perform the pigeonhole sort of given array
public void pigeonhole_sort(int[] arr, int size)
{
if (size < 1)
{
return;
}
int min = find_min(arr, size);
int max = find_max(arr, size);
int hole_range = max - min + 1;
int[] hole = new int[hole_range];
//Loop controlling variables
int i = 0;
int j = 0;
//Set the initial hole value
for (i = 0; i < hole_range; ++i)
{
hole[i] = 0;
}
//Count the occurrences of array elements
for (i = 0; i < size; i++)
{
hole[arr[i] - min]++;
}
for (i = 0; i < hole_range; i++)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j++;
//reduce the existing occurrence
hole[i]--;
}
}
}
//print the array elements
public void display(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
Console.Write("  " + arr[i]);
}
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr = {
7 , 2 , 90 , 4 , 1 , 3 , 46 , -4 , -4 , 12 , 6 , 3 , 2
};
int size = arr.Length;
Console.Write("After Sort : ");
obj.display(arr, size);
obj.pigeonhole_sort(arr, size);
Console.Write("\nBefore Sort  : ");
obj.display(arr, size);
}
}``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````<?php
// Php program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
public	function find_min( \$arr, \$size)
{
\$result = \$arr[0];
for (\$i = 1; \$i < \$size; ++\$i)
{
if (\$arr[\$i] < \$result)
{
\$result = \$arr[\$i];
}
}
return \$result;
}
//Find the maximum element of given array
public	function find_max( \$arr, \$size)
{
\$result = \$arr[0];
for (\$i = 1; \$i < \$size; ++\$i)
{
if (\$arr[\$i] > \$result)
{
\$result = \$arr[\$i];
}
}
return \$result;
}
// Perform the pigeonhole sort of given array
public	function pigeonhole_sort( & \$arr, \$size)
{
if (\$size < 1)
{
return;
}
\$min = \$this->find_min(\$arr, \$size);
\$max = \$this->find_max(\$arr, \$size);
\$hole_range = \$max - \$min + 1;
//Set the initial hole value
\$hole = array_fill(0, \$hole_range, 0);
//Loop controlling variables
\$i = 0;
\$j = 0;
//Count the occurrences of array elements
for (\$i = 0; \$i < \$size; \$i++)
{
\$hole[\$arr[\$i] - \$min]++;
}
for (\$i = 0; \$i < \$hole_range; \$i++)
{
//Check that whether hole occurrence greater than zero
while (\$hole[\$i] > 0)
{
//When occurrence are more than zero
//Put element value to array
\$arr[\$j] = \$i + \$min;
// Modify the index of array element
// next element location
\$j++;
//reduce the existing occurrence
\$hole[\$i]--;
}
}
}
//print the array elements
public	function display( & \$arr, \$size)
{
\$i = 0;
for (\$i = 0; \$i < \$size; \$i++)
{
echo "  ". \$arr[\$i];
}
}
}

function main()
{
\$obj = new MySort();
//Define the collection of integer elements
\$arr = array(7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2);
\$size = count(\$arr);
echo "After Sort : ";
\$obj->display(\$arr, \$size);
\$obj->pigeonhole_sort(\$arr, \$size);
echo "\nBefore Sort  : ";
\$obj->display(\$arr, \$size);
}
main();``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````// Node Js program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
find_min(arr, size)
{
var result = arr[0];
for (var i = 1; i < size; ++i)
{
if (arr[i] < result)
{
result = arr[i];
}
}
return result;
}
//Find the maximum element of given array
find_max(arr, size)
{
var result = arr[0];
for (var i = 1; i < size; ++i)
{
if (arr[i] > result)
{
result = arr[i];
}
}
return result;
}
// Perform the pigeonhole sort of given array
pigeonhole_sort(arr, size)
{
if (size < 1)
{
return;
}
var min = this.find_min(arr, size);
var max = this.find_max(arr, size);
var hole_range = max - min + 1;
//Set the initial hole value
var hole = Array(hole_range).fill(0);
//Loop controlling variables
var i = 0;
var j = 0;

//Count the occurrences of array elements
for (i = 0; i < size; i++)
{
hole[arr[i] - min]++;
}
for (i = 0; i < hole_range; i++)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j++;
//reduce the existing occurrence
hole[i]--;
}
}
}
//print the array elements
display(arr, size)
{
var i = 0;
for (i = 0; i < size; i++)
{
process.stdout.write("  " + arr[i]);
}
}
}

function main()
{
var obj = new MySort();
//Define the collection of integer elements
var arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2];
var size = arr.length;
process.stdout.write("After Sort : ");
obj.display(arr, size);
obj.pigeonhole_sort(arr, size);
process.stdout.write("\nBefore Sort  : ");
obj.display(arr, size);
}
main();``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````#  Python 3 program
#  Sort array by using pigeonhole sort
class MySort :
# Find the minimum element of given array
def find_min(self, arr, size) :
result = arr[0]
i = 1
while (i < size) :
if (arr[i] < result) :
result = arr[i]

i += 1

return result

# Find the maximum element of given array
def find_max(self, arr, size) :
result = arr[0]
i = 1
while (i < size) :
if (arr[i] > result) :
result = arr[i]

i += 1

return result

#  Perform the pigeonhole sort of given array
def pigeonhole_sort(self, arr, size) :
if (size < 1) :
return

min = self.find_min(arr, size)
max = self.find_max(arr, size)
hole_range = max - min + 1
hole = [0] * hole_range
# Loop controlling variables
i = 0
j = 0

# Count the occurrences of array elements
i = 0
while (i < size) :
hole[arr[i] - min] += 1
i += 1

i = 0
while (i < hole_range) :
# Check that whether hole occurrence greater than zero
while (hole[i] > 0) :
# When occurrence are more than zero
# Put element value to array
arr[j] = i + min
#  Modify the index of array element
#  next element location
j += 1
# reduce the existing occurrence
hole[i] -= 1

i += 1

# print the array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print("  ", arr[i], end = "")
i += 1

def main() :
obj = MySort()
# Define the collection of integer elements
arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2]
size = len(arr)
print("After Sort : ", end = "")
obj.display(arr, size)
obj.pigeonhole_sort(arr, size)
print("\nBefore Sort  : ", end = "")
obj.display(arr, size)

if __name__ == "__main__": main()``````

#### Output

``````After Sort :    7   2   90   4   1   3   46   -4   -4   12   6   3   2
Before Sort  :    -4   -4   1   2   2   3   3   4   6   7   12   46   90``````
``````#  Ruby program
#  Sort array by using pigeonhole sort
class MySort

# Find the minimum element of given array
def find_min(arr, size)

result = arr[0]
i = 1
while (i < size)

if (arr[i] < result)

result = arr[i]
end
i += 1
end
return result
end
# Find the maximum element of given array
def find_max(arr, size)

result = arr[0]
i = 1
while (i < size)

if (arr[i] > result)

result = arr[i]
end
i += 1
end
return result
end
#  Perform the pigeonhole sort of given array
def pigeonhole_sort(arr, size)

if (size < 1)

return
end
min = self.find_min(arr, size)
max = self.find_max(arr, size)
hole_range = max - min + 1
hole = Array.new(hole_range) {0}
# Loop controlling variables
i = 0
j = 0

# Count the occurrences of array elements
i = 0
while (i < size)

hole[arr[i] - min] += 1
i += 1
end
i = 0
while (i < hole_range)

# Check that whether hole occurrence greater than zero
while (hole[i] > 0)

# When occurrence are more than zero
# Put element value to array
arr[j] = i + min
#  Modify the index of array element
#  next element location
j += 1
# reduce the existing occurrence
hole[i] -= 1
end
i += 1
end
end
# print the array elements
def display(arr, size)

i = 0
while (i < size)

print("  ", arr[i])
i += 1
end
end
end
def main()

obj = MySort.new()
# Define the collection of integer elements
arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2]
size = arr.length
print("After Sort : ")
obj.display(arr, size)
obj.pigeonhole_sort(arr, size)
print("\nBefore Sort  : ")
obj.display(arr, size)
end
main()``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````// Scala program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
def find_min(arr: Array[Int], size: Int): Int = {
var result: Int = arr(0);
var i: Int = 1;
while (i < size)
{
if (arr(i) < result)
{
result = arr(i);
}
i += 1;
}
return result;
}
//Find the maximum element of given array
def find_max(arr: Array[Int], size: Int): Int = {
var result: Int = arr(0);
var i: Int = 1;
while (i < size)
{
if (arr(i) > result)
{
result = arr(i);
}
i += 1;
}
return result;
}
// Perform the pigeonhole sort of given array
def pigeonhole_sort(arr: Array[Int], size: Int): Unit = {
if (size < 1)
{
return;
}
var min: Int = find_min(arr, size);
var max: Int = find_max(arr, size);
var hole_range: Int = max - min + 1;
var hole: Array[Int] = Array.fill[Int](hole_range)(0);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;

//Count the occurrences of array elements
i = 0;
while (i < size)
{
hole(arr(i) - min) += 1;
i += 1;
}
i = 0;
while (i < hole_range)
{
//Check that whether hole occurrence greater than zero
while (hole(i) > 0)
{
//When occurrence are more than zero
//Put element value to array
arr(j) = i + min;
// Modify the index of array element
// next element location
j += 1;
//reduce the existing occurrence
hole(i) -= 1;
}
i += 1;
}
}
//print the array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define the collection of integer elements
var arr: Array[Int] = Array(7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2);
var size: Int = arr.length;
print("After Sort : ");
obj.display(arr, size);
obj.pigeonhole_sort(arr, size);
print("\nBefore Sort  : ");
obj.display(arr, size);
}
}``````

#### Output

``````After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90``````
``````// Swift program
// Sort array by using pigeonhole sort
class MySort
{
//Find the minimum element of given array
func find_min(_ arr: [Int], _ size: Int) -> Int
{
var result: Int = arr[0];
var i: Int = 1;
while (i < size)
{
if (arr[i] < result)
{
result = arr[i];
}
i += 1;
}
return result;
}
//Find the maximum element of given array
func find_max(_ arr: [Int], _ size: Int) -> Int
{
var result: Int = arr[0];
var i: Int = 1;
while (i < size)
{
if (arr[i] > result)
{
result = arr[i];
}
i += 1;
}
return result;
}
// Perform the pigeonhole sort of given array
func pigeonhole_sort(_ arr: inout[Int], _ size: Int)
{
if (size < 1)
{
return;
}
let min: Int = self.find_min(arr, size);
let max: Int = self.find_max(arr, size);
let hole_range: Int = max - min + 1;
var hole: [Int] = Array(repeating: 0, count: hole_range);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;

//Count the occurrences of array elements
i = 0;
while (i < size)
{
hole[arr[i] - min] += 1;
i += 1;
}
i = 0;
while (i < hole_range)
{
//Check that whether hole occurrence greater than zero
while (hole[i] > 0)
{
//When occurrence are more than zero
//Put element value to array
arr[j] = i + min;
// Modify the index of array element
// next element location
j += 1;
//reduce the existing occurrence
hole[i] -= 1;
}
i += 1;
}
}
//print the array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
}
}
func main()
{
let obj: MySort = MySort();
//Define the collection of integer elements
var arr: [Int] = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2];
let size: Int = arr.count;
print("After Sort : ", terminator: "");
obj.display(arr, size);
obj.pigeonhole_sort(&arr, size);
print("\nBefore Sort  : ", terminator: "");
obj.display(arr, size);
}
main();``````

#### Output

``````After Sort :    7   2   90   4   1   3   46   -4   -4   12   6   3   2
Before Sort  :    -4   -4   1   2   2   3   3   4   6   7   12   46   90``````

Pigeonhole Sort works in the following way:

1. Determine the range of values: Find the minimum and maximum values in the input array. The range of values is then defined as the difference between the maximum and minimum values plus one.

2. Create the pigeonholes: Create an array of pigeonholes that is large enough to hold all the input elements. The size of the array is equal to the range of values.

3. Place elements in the pigeonholes: Iterate over the input array and place each element in its corresponding pigeonhole based on its value. For example, if an element has value 5 and the minimum value is 2, then it would be placed in the third pigeonhole (since the third pigeonhole corresponds to the value 5 - 2 = 3).

4. Put elements back in sorted order: Iterate over the pigeonholes in order and put the elements back into the original array in sorted order. For each pigeonhole, iterate over the elements in the pigeonhole and place them back into the original array.

5. The array is now sorted: The original array now contains the elements sorted in ascending order.

Here's an example to help illustrate the algorithm. Suppose we have the following array of 7 elements:

[5, 2, 8, 1, 4, 5, 6]

1. Determine the range of values: The minimum value is 1 and the maximum value is 8, so the range of values is 8 - 1 + 1 = 8.

2. Create the pigeonholes: Create an array of 8 pigeonholes.

3. Place elements in the pigeonholes: Iterate over the input array and place each element in its corresponding pigeonhole based on its value.

• 1 goes in pigeonhole 0 (since 1 - 1 = 0)
• 2 goes in pigeonhole 1 (since 2 - 1 = 1)
• 4 goes in pigeonhole 3 (since 4 - 1 = 3)
• 5 goes in pigeonhole 4 (since 5 - 1 = 4)
• 5 goes in pigeonhole 4 (since 5 - 1 = 4)
• 6 goes in pigeonhole 5 (since 6 - 1 = 5)
• 8 goes in pigeonhole 7 (since 8 - 1 = 7)

The pigeonholes now contain the following elements:

[1, 1, 0, 1, 2, 1, 0, 1]

4. Put elements back in sorted order: Iterate over the pigeonholes in order and put the elements back into the original array in sorted order.

• Pigeonhole 0 contains no elements
• Pigeonhole 1 contains 1 element, which is placed in the first position of the output array: [1]
• Pigeonhole 2 contains no elements
• Pigeonhole 3 contains 1 element, which is placed in the second position of the output array: [1, 2]
• Pigeonhole 4 contains 2 elements, which are placed in the third and fourth positions of the output array: [1, 2, 5, 5]
• Pigeonhole 5 contains 1 element, which is placed in the fifth position of the output array: [1, 2, 5, 5, 6]
• Pigeonhole 6 contains no elements
• Pigeonhole 7 contains 1 element, which is placed in the sixth position of the output array: [1, 2, 5, 5, 6, 8]

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.