Find largest sub-array formed by consecutive integers

Given an array of integers, find largest sub-array formed by consecutive integers. The sub-array should contain all distinct values.

 

For example,


Input:  { 2, 0, 2, 1, 4, 3, 1, 0 }
Output: The largest sub-array is { 0, 2, 1, 4, 3 }

 


 
The idea is to consider every sub-array and keep track of largest subarray found so far which is formed by consecutive integers. In order for an sub-array to contain consecutive integers,

  • The difference between maximum and minimum element in it should be exactly equal to length of the subarray minus one.
     
  • All elements in the array should be distinct (we can check this by inserting the elements in set or using a visited array).

C++

Download   Run Code

Java

Download   Run Code



Output:

The largest sub-array is [1, 5]

 
The time complexity of above solution is O(n3) and auxiliary space used by the program is O(n).
 

Exercise: Extend the solution to consider duplicates in the sub-array.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Dmitriy
Dmitriy

I think a sliding-window approach can accomplish this in linear time.

Thank you for posting so many helpful practice problems!

Cliff Crosland
Cliff Crosland

Cool – you can get O(n^2) time here by building the set as you go along in the inner loop that iterates through j. If max – min == j – i, and if all of the values between i and j are distinct (which you can tell from the set size), then you know immediately that the subsequence consists of the consecutive integers in the range [min, max].

You can also break out of the inner loop early if you ever run into a duplicate.

Will think about Dimitriy’s O(n) hint, cool…

Renjith Varma
Renjith Varma

This is O(n3) solution

wpDiscuz