Here we find 2 ranges for which all the integers in these ranges are present in the array.

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. Have to do it in linear time. May use extra memory. But Hashing is not the correct solution.
eg. arr = {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15}

Here we find 2 ranges for which all the integers in these ranges are present in the array.
namely: [2,8] and [10,12]
out of these [2,8] is the longer one. So we need to output that.


Basic Solution

First sort the array.
Have 3 integers - start, end and len. Initialize to 0. Have another variable "first" to point to the first element in the current set.

Loop the sorted array from start to end. Assign "first" to first element. Keep looping as long as the next element is contiguous. As soon as continuity breaks, subtract current number with "first". If it is more than "len", store "first" and current number in "start" and "end" respectively. Store the length calculated in "len". Continue this process.

You'll finally have the largest range in "start" and "end".

But Constraints is O(N)???