What is Order Statistics?

The i^th order statistics is defined as the value that comes in the i^th position of the N element sequence when the sequence is sorted in increasing order.

In simple terms, the order statistics is the i^th smallest element in the given array. Below are a few examples to understand the order statistics:

• Minimum = Order statistics 1
• 2nd minimum = Order statistics 2
• Median = Order statistics floor((N+1)/2)
• 2nd Maximum = Order Statistics N-1
• Maximum = Order statistics N

Easy Practice Problems in Array Order Statistics:

• Program to find largest element in an array
• Find the largest three elements in an array
• Program for Mean and median of an unsorted array
• Find Second largest element in an array
• Find the smallest and second smallest elements in an array
• Maximum and minimum of an array using minimum number of comparisons
• Find the largest pair sum in an unsorted array
• Find all elements in array which have at-least two greater elements
• Count Strictly Increasing Subarrays
• Minimum product of k integers in an array of positive Integers
• K’th Smallest/Largest Element using STL

Medium Practice Problems in Array Order Statistics:

• K’th Smallest/Largest Element in Unsorted Array
• K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time
• K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time
• Find the smallest missing number
• K’th largest element in a stream
• Next Greater Element
• Maximum sum such that no two elements are adjacent
• K-th Largest Sum Contiguous Subarray
• K maximum sums of non-overlapping contiguous sub-arrays
• Find k pairs with smallest sums in two arrays
• Find k numbers with most occurrences in the given array
• Longest Monotonically Increasing Subsequence Size (N log N)

Hard Practice Problems in Array Order Statistics:

• Kth smallest element in a row-wise and column-wise sorted 2D array
• Median of Stream of Running Integers using STL
• k smallest elements in same order using O(1) extra space
• Maximum of all subarrays of size k
• Find the smallest positive number missing from an unsorted array | Set 1
• Find the maximum repeating number in O(n) time and O(1) extra space
• Minimum number of elements to add to make median equals x
• k-th smallest absolute difference of two elements in an array
• Smallest greater elements in whole array
• K maximum sums of overlapping contiguous sub-arrays

Quick Links :

• ‘Practice Problems’ on Arrays
• ‘Quizzes’ on Arrays
• ‘Video Tutorials’ on Arrays