4–Sum Problem | Quadruplets with a given sum
4-sum problem: Given an unsorted integer array, check if it contains four elements tuple (quadruplets) having a given sum.
Category: Sorting
Sort an array in one swap whose two elements are swapped
Given an array where all its elements are sorted except two swapped elements, sort it in linear time. Assume there are no duplicates in the array.
Quicksort algorithm using Hoare’s partitioning scheme
Implement the Quicksort algorithm using Hoare’s Partitioning scheme which is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
Count Sort – C++, Java, and Python Implementation
This post covers a variation of counting sort that can work on negative numbers and can sort numbers in any range.
Find a triplet with the given sum in an array
Given an unsorted integer array, find a triplet with a given sum in it.
Find surpasser count for each array element
Given an integer array having distinct elements, find the surpasser count for each element in it. In other words, for each array element, find the total number of elements to its right, which are greater than it.
Merge `M` sorted lists of variable length
Given M sorted lists of variable length, print them efficiently in sorted order.
Introsort Algorithm – Overview and C++ Implementation
Introsort is an efficient in-place sorting algorithm, which usually beats all other sorting algorithms in terms of performance. Due to its high performance, it is used in several standard library sort functions.
Find a triplet having the maximum product in an array
Given an integer array, find a triplet having the maximum product.
Find two numbers with maximum sum formed by array digits
Given an integer array between 0 and 9, find two numbers with maximum sum formed using all the array digits. The difference in the number of digits of the two numbers should be ± 1.
Counting Sort Algorithm – C, Java, and Python Implementation
Given a collection of n items, each of which has a non-negative integer key whose maximum value is at most k, effectively sort it using the counting sort algorithm.
Efficiently sort an array with many duplicated values
Given an array with many duplicated elements, write an algorithm to efficiently sort it in linear time, where the order of equal elements doesn’t matter.