Given an integer array, find the largest subarray formed by consecutive integers. The subarray should contain all distinct values.

For example,

Input:  { 2, 0, 2, 1, 4, 3, 1, 0 }
 
Output: The largest subarray is { 0, 2, 1, 4, 3 }

Practice this problem

The problem differs from the problem of finding the longest subsequence formed by consecutive integers. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.

 
The idea is to consider every subarray and keep track of the largest subarray found so far, formed by consecutive integers. For a subarray to contain consecutive integers,

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

The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

The largest subarray is [1, 5]

Java


Download  Run Code

Output:

The largest subarray is [1, 5]

Python


Download  Run Code

Output:

The largest subarray is (1, 5)

The time complexity of the above solution O(n3) and requires O(n) extra space, where n is the size of the input.

 
Exercise: Extend the solution to consider duplicates in the subarray.