Sort,

Question: http://www.lintcode.com/en/problem/maximum-gap/ Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Sort is easy but will cost O(nlogn) time. Try to solve it in linear time