### Remove Duplicates from Sorted Array - Leet Code Solution

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

July 16, 2019

Counting sort runs on relatively smaller set of input.
Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put *X* directly into its position in sorted array.

Selection sort takes two additional array.

- One for result, the sorted array
- other for temporary storage, where size equals to the maximum number on input array.

Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.

- First iterate on input array, and calculate each number occurence in the 2nd additional array (lets call it C).
- After the iteration, The array-C’s index will denote the input number, and the value contains how many times the number comes in original array. In the image above, see part-a.
- Run one more iteration on array-c. And, accumulate the sum. See above image, part-b
- Now iterate equal to length of original array (from last index to 0):
- For the number in original array, use it as index in array-C, which will give you its position in sorted array
- Put this number in sorted array at position told by array-c
- Decrement this value from array-c by 1

- At the end, we will get sorted array.

See the code here:

```
public class CountSort {
private int[] arr;
public CountSort(int[] arr) {
this.arr = arr;
}
/**
* Count sort, max value-k
* @param k, the max value in array
*/
public int[] doSort(int k) {
int[] c = new int[k+1];
//count number of occurence
for (int i=0; i<this.arr.length; i++) {
c[this.arr[i]] ++;
}
//accumulate
for (int i=1; i<c.length; i++) {
c[i] += c[i-1];
}
int[] result = new int[this.arr.length];
//put the number to its designated place
for (int i=this.arr.length-1; i>=0; i--) {
result[c[this.arr[i]]-1] = this.arr[i];
c[this.arr[i]] --;
}
return result;
}
}
```

- It is not a comparison sort.
- It is a stable sort.
- This uses 2 additional arrays.
- It is used for relatively smaller set of numbers.
- The maximum number in array should be order of size of array. Example: this algorithm is good for sorting age of people.
- Performance is very good. its time complexity is
*O(n + k) ~= O(n)*

The algorithm runs on time complexity of *O(n + k) ~= O(n)* in worst/average case.

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

Problem Statement Given a Binary tree, print out nodes in level order traversal…

Introduction You are given an array of integers with size N, and a number K…

Problem Statement Given an array nums of n integers and an integer target, are…

Problem Statement You are given a string text of words that are placed among…

Problem Statement Determine whether an integer is a palindrome. An integer is a…

Introduction Java log4j has many ways to initialize and append the desired…

Introduction You have a running kubernetes setup, and have a webservice (exposed…

Introduction I have my main website, which I run on Lets say: . Now, there is my…

Understanding Simple Message Workflow First, lets understand a simple workflow…

Exponential Backoff in Rabbitmq Please make sure to read first, why we need the…

Introduction This post has the complete code to send email through smtp server…