Count and Rearrange

Problem Statement:

Manju is given a task to find the count of a given number from the group of sorted numbers and then push the numbers to the front of the array to easily be picked up and counted.

Discussed Solution Approaches:

• The brute force approach using loop
• The optimized approach using binary search

The key takeaway from this coding problem:

• Learn about binary search
• Learn about swapping elements in an array

For example:
If the numbers are 1, 1, 2, 2, 2, 2, 6 and you are given number 2 to count and push it to the front then, the final output would look like
Output: 2, 2, 2, 2, 1, 1, 6

Can you do it in the time complexity of O(logn) with the space complexity of O(1)? considering only finding and counting the numbers

Now, for time being forget the time complexity you have been given to find out the solution, for now, think of the most basic way to find a solution to the problem.

Let’s break the problem into two subproblems:-
1. Find the count of the given number
2. Arrange the given number at the starting of all the other numbers

Let’s Code

Naive Solution:

The brute-force solution to the problem would be using linear search to count the occurrence of the number and then rearrange the number to the front of all other numbers.

Let’s look at the algorithm of this method:

start function searchElementandSwapp(array, array_size, number){
     count = 0
     initialIndex = 0
     /* Get the count of the number and the index where it was first found */
     start for (index is 0 to index is less than array_size increment index by 1)
          start if(array[index] is equal to number and count = 0)
                increment count by 1
                set initialIndex as index
          end if
          start if(array[index] is equal to number and count != 0)
                increment count by 1
          end if
     end for
     /* Now swapp the numbers */
     start for (index is 0 to index is less than array_size and array[initialIndex] is equal to number increment  by 1)
        start if(array[initialIndex] is equal to number and initialIndex is less than array_size)
             swapp array[index] and array[initialIndex]
             increment initialIndex by 1
        end if
     end for
end searchElementandSwapp

This algorithm will take O(n) time to get executed and complete the operation with space of O(1)

This algorithm will surely fail for the large size of the array and is inefficient for the larger array size, so what should we think to optimize it further?

Have you ever heard of a binary search algorithm?

This problem satisfies all the rules of where binary search can be used as the array is completely sorted and we could find the element in a time of O(logn) exactly what we want!

Binary Search Method:

Let’s discuss the algorithm for first find the element that where it occurs in the array:

start function searchElement(array, start_index, end_index, number)
       start if(end_index is less than 1)
           return -1
       end if
       mid_index = start_index + (end_index - start_index) / 2
  
       start if(array[mid_index] is equal to number)
            return mid_index
       end if
       start if(array[mid_index] is less than number)
            searchElement(array, mid_index + 1, end_index, number)
       end if
       start else
            searchElement(array, start_index, mid_index - 1, number)
       end else
end searchElement

Now, after searching we will need to count the occurrence of a given number in the array, for which we could write our algorithm as

start function countElement(array, array_size, number)
     getIndex = searchElement(array, 0, array_size - 1, number)
     /* if the element is not present */
     start if(getIndex is equal to -1)
         return 0
     end if
     
     count = 0
     leftCountIndex = getIndex
     rightCountIndex = getIndex
     initialIndex = 0 /* this will let us know the first position where the number was found to swapp it later on */
     /* count left side */
 
     start while(leftCountIndex is greater than or equal to 0 and array[leftCountIndex] is equal to number)
           increment count by 1
           set initialIndex to leftCountIndex
           decrement leftCountIndex by 1
     end while
     /* count right side */
     start while(rightCountIndex is less than the array_size and   array[rightCountIndex] is equal to number)
           increment count by 1
           incrementrightCountIndex by 1
     end while
     print count 
     return initialIndex
end countElement

Now, we have the initialIndex with you so we can easily use it to swap the numbers to the front (as shown in the naive approach swapping we will use the same way), and boom! you have solved the problem in the desired time.

Now, since you already know the algorithm behind the problem so, you can write your own functional code in your desired programming language.

Analyze:

• Time Complexity: O(logn), where n is the size of the given array this is because we are using the binary search approach.
• Space Complexity: O(1), since we are not using any extra space to store the elements.

Keep learning and keep growing and also keep exploring more!

All the very best!

For more interesting and informative articles and tips follow me on Medium and Linkedin