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 »
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 »
Problem Given an array of integers, you need to find the minimum number operations required for an array containing only zeros to get converted into this array by performing only two kinds of operations: 1: Increment any value by one 2: Double all elements of the array. Sample Input [16, 16, 16] Sample Output Operations are 7 Approach… Read More »
In Python, we have a upper() method for string data values, which can convert all the lowercase letters to uppercase letters and return them. This method also has a sibling isupper() method that can check if a string contains only upper case characters or not.
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 »
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 »
Problem Implement QuickSort using Hoare’s partition scheme. Approach Hoare’s Partition Scheme works by starting two indices at opposite ends and moving them toward each other until an inversion (a smaller value on the left side and a bigger value on the right side) is discovered. When an inversion is discovered, two values are switched and the procedure is… Read More »
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 »
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 »
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 »
