Sort Integers By The Number Of 1 Bits LeetCode

 Problem Link:

https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/

Solution:

public int cal(int n){

        int count=0;

        while(n>0){

            n=n&(n-1);

            ++count;

        }

        return count;

    }

    

    

    public int[] sortByBits(int[] arr) {

        TreeMap<Integer,PriorityQueue<Integer>>map=new TreeMap<Integer,PriorityQueue<Integer>>();

        

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

           if(map.containsKey(cal(arr[i]))){

              PriorityQueue<Integer>pq=map.get(cal(arr[i]));

               pq.add(arr[i]);

               map.put(cal(arr[i]),pq);

              

           }

            else{

                PriorityQueue<Integer>pq=new PriorityQueue<Integer>();

                pq.add(arr[i]);

                map.put(cal(arr[i]),pq);

               

            }

        }

        //System.out.println(map);

        int arr1[]=new int[arr.length];

        int index=0;

       for(int a:map.keySet()){

           while(map.get(a).size()!=0){

               arr1[index++]=map.get(a).remove();

           }

       }

        

        return arr1;

TIME COMPLEXITY:O(arr.length*number of set bits in the element of the array) it will be less than O(N^2) and O(N*Logn) too.[LeetCode Time:15 ms faster than 40.40%]

SPACE COMPLEXITY:O(N)[Array is given.]

AUXILLARY SPACE:O(N)[Map, Priority Queue, and an additional array (size n) are used.]

MEMORY USAGE: 39.8MB less than 53.62%.

APPROACH:

Before discussing approaches, I have discussed some time complexities of different functions used

1.Array Traversal ----------------> O(arr.length)

2. Searching In Map ----------------> O(1) [Unique Id is there for every value ie key.]

3. Insertion In Map ------------------->O(l) [One particular unique key and then value.]

3. Computing Number Of Bits in number ----------------> O(number of 1's bits in number) which is less than O(logn)

4. So for time complexity 

1 iteration -------------------> O(1*1*number of set bits in number) ie O(first iteration * searching in map * )

So for iteration equal to arr. length-------------------->O(arr.length*1*number of bits in number)

So Now about the approach:

1. We will use the map concept. In which the number of bits will be key and PriorityQueue will be valued.

Now Question Arises why to use count as a key because the key is not unique. The answer is quite simple we use count as key and whatever the elements satisfy the specific count value they will be added in the priority queue which is value against that count.

Usage of priority queue is great as itself only it will sort the elements so at a later stage you don't need to sort the list as a number of times as different count values will be there.

2. For calculating count value we have to use the Brian-Kerningam method whose time complexity is equal to the number of set bits in a number.

3. For every number we will find out the count value and put them on the map. As the number of elements having that count value increases we will continuously add on that element in the priority queue.

4. Later we will traverse the map (map. size<arr.length) and use the key set function of the map.

Every time we will get priority queue as value and till the time queue is not empty we will add on the values in the new array which we will return later.  

Usage of treemap further sorts the key in ascending order and hence we satisfy the condition of solution ie sorted.

-----------------------------------------------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"