Longest subarray whose elements form a continuous sequence

Question

Given an unsorted array of positive integers, find the length of the longest subarray whose elements when sorted are continuous. Can you think of an O(n) solution?

Example:

{10, 5, 3, 1, 4, 2, 8, 7}, answer is 5.

{4, 5, 1, 5, 7, 6, 8, 4, 1}, answer is 5.

For the first example, the subarray {5, 3, 1, 4, 2} when sorted can form a continuous sequence 1,2,3,4,5, which are the longest.

For the second example, the subarray {5, 7, 6, 8, 4} is the result subarray.

I can think of a method which for each subarray, check if (maximum - minimum + 1) equals the length of that subarray, if true, then it is a continuous subarray. Take the longest of all. But it is O(n^2) and can not deal with duplicates.

Can someone gives a better method?

Answer 1

Algorithm to solve original problem in O(n) without duplicates. Maybe, it helps someone to develop O(n) solution that deals with duplicates.

Input: [a1, a2, a3, ...]

Map original array as pair where 1st element is a value, and 2nd is index of array.

Array: [[a1, i1], [a2, i2], [a3, i3], ...]

Sort this array of pairs with some O(n) algorithm (e.g Counting Sort) for integer sorting by value. We get some another array:

Array: [[a3, i3], [a2, i2], [a1, i1], ...]

where a3, a2, a1, ... are in sorted order.

Run loop through sorted array of pairs

In linear time we can detect consecutive groups of numbers a3, a2, a1. Consecutive group definition is next value = prev value + 1. During that scan keep current group size (n), minimum value of index (min), and current sum of indices (actualSum).

On each step inside consecutive group we can estimate sum of indices, because they create arithmetic progression with first element min, step 1, and size of group seen so far n. This sum estimate can be done in O(1) time using formula for arithmetic progression:

estimate sum = (a1 + an) * n / 2;

estimate sum = (min + min + (n - 1)) * n / 2;

estimate sum = min * n + n * (n - 1) / 2;

If on some loop step inside consecutive group estimate sum equals to actual sum, then seen so far consecutive group satisfy the conditions. Save n as current maximum result, or choose maximum between current maximum and n.

If on value elements we stop seeing consecutive group, then reset all values and do the same.

Code example: https://gist.github.com/mishadoff/5371821