Count Inversions

Problem Given an array of integers, count the number of inversions present in it. An inversion is such that arr[i] > arr[j] and i<j. Sample Input [3, 4, 1] Sample Output Inversion count is 2 Approach 1 Traverse through the array, and for every index, find the number of smaller elements on its right side. This can be… Read More »

Sort elements by their frequency and index

Problem  Given an array of integers, sort them by their frequencies. If two elements have the same frequencies, sort them by their indices. Sample Input 1, 1, 2, 3, 3, 3 Sample Output 3, 3, 3, 1, 1, 2 Approach We can make our custom comparator in this approach. The comparator should: first compare the frequency of the… Read More »

Hybrid QuickSort Algorithm

Problem Implement hybrid quicksort algorithm What is a hybrid algorithm? In a hybrid technique, we combine multiple algorithms and make use of their performance to achieve a result efficiently. Approach In this article, we will combine insertion sort with quicksort algorithm. Insertion sort works well for the arrays with smaller size or when the array “is almost” sorted… Read More »

Quicksort using Dutch National Flag Algorithm

Problem Implement Quicksort using Dutch National Flag Algorithm What’s the issue with the normal QuickSort Algorithm If all elements are equal in an array, the left partition is empty after the pivot operation and the right subarray only decreases by one. Therefore, the algorithm takes O(N2) time in the worst case. How to improve on the above algorithm … Read More »

In-place vs out-of-place algorithms

In-Place algorithms This is a category of the algorithms that do not consume any extra space in order to solve a given task. They generally override the given input with the output. We can say that the auxiliary space complexity of these algorithms is O(1). These algorithms may sometimes require a very small space but that space should… Read More »

Problems solved using partitioning logic of Quicksort

Problem What are some of the problems that can be solved using partition logic of quicksort What is Partition Logic The partition logic of quicksort selects one of the elements as pivot and puts all the elements smaller than it on its left side and all elements greater than it to its right side. Problem 1: Given a… Read More »

Find minimum and maximum with minimum number of comparisons

Problem Given an array of integers, find minimum and maximum elements in it with minimum number of comparisons. Sample Input [1, 3, 2, 7] Sample Output Minimum element is 1 Maximum element is 7 Brute Force Approach We can search for the required elements by comparing each element and finally returning the result. This will make 3(n-1) comparisons… Read More »