### Leetcode - Rearrange Spaces Between Words

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

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 You are given a string text of words that are placed among…

Its a tree based data structure which is a complete binary tree(all nodes have…

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

Max Priority Queue is a data structure which manage a list of keys(values). And…

Problem Statement Maximum Length of Subarray With Positive Product. Given an…

Here are some tips while preparing for your coding interviews. 1. Do study or…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

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