Tag Archives: Maximum
 Gap
 Problem

The 
Maximum
 Gap
 Problem : 
Pigeonhole 
Principle


Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)? For example, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is [1, 2, 3, 4, 5, 8, 9]. The output of the […]