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).


Download   Run Code


Download   Run Code


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 🙂

Sort by:   newest | oldest | most voted

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… Read more »
Renjith Varma
Renjith Varma

This is O(n3) solution

Raj Pratim Bhattacharya
Raj Pratim Bhattacharya

O(n*n) time and Omega(n) space –

I don’t understand the question. What are consecutive integers? To me consecutive integers are 2,3,4 or 77,78,79. In the example provided at the beginning of this page, in what way are 0,2,1,4,3 consecutive integers? Is the question really asking “find the largest subarray formed by unique integers” ? Or is… Read more »