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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Dmitriy
Guest

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

Thank you for posting so many helpful practice problems!

newbie
Guest

hey
can i ask you where i can find explication of this method i ve been looking all google without finding it

Cliff Crosland
Guest

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…

Akash kandpal
Guest

A hashmap implementation can bring down the time complexity to O(n) keeping it in-place . Also an approach using merge sot can reduce the algorithm to O(nlogn) but with a space complexity of O(nlogn) . The above question was asked to me in my Facebook interview 🙂

Raj Pratim Bhattacharya
Guest
Raj Pratim Bhattacharya

O(n*n) time and Omega(n) space –
http://ideone.com/87Hzjc

Sam
Guest

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 it something else?

Tarun Mitra
Guest

Done with Sliding window. Time o(n) and space o(1). https://ideone.com/V0Iho0

Lithium
Guest

Sliding window approach with HashMap [ O(N) ] is hardly possible.
I tried it on my own with C++, the program has some issues with this ruleset:
{ 0, 2, 1, [2, 1, 3, 4] } (brackets identify here the best answer)
The problem is with minimum and maximum values.
When i = 2,
{[0, 2, 1], 2, 1, 3, 4 }
the minimum value in the range is 0.
However, at 3,
{0, 2, [1, 2], 1, 3, 4}
the first two elements are taken off a sliding window, so the minimum value must also change to 1.
But we cannot find the second minimum/maximum value in O(1) time.
It is possible to traverse the hashmap up until we find it (it might be unsafe if we have huge ‘cliffs’ in the array with big differences of the numbers).
It is possible have a basic bit array of numbers. We could find the biggest and the smallest number in the whole array and then initialize an array (still an allocation problem if we have long long ints in the array). But it works when needed. O(N).
The most reliable solution for big integers is a ‘set’ structure with O(NlogN) time.

İsmail KILIC
Guest
nope
Guest
foobar
Guest

It seems like visited array is not needed. Isn’t it?

Patrick Spears
Guest

Perhaps, the description to the problem should be to find the largest subarray of consecutive integers that can be formed by arranging the integers in order.

Oshun
Guest

Solution in O(n)

public static void largestUniqueSubArray(int[] arr) {

if (arr.length <= 0)
System.out.println("Invalid input");

HashMap<Integer, Integer> mMap = new HashMap<>();
HashMap<Integer, Integer> indices = new HashMap<>();

int largestSoFar = 1;
int currentLargest = 0;
int startIndex = 0;

for (int i = 0; i < arr.length; i++) {
if (mMap.containsValue(arr[i])) {
largestSoFar = 1;
indices.put(startIndex, i - 1); // start, end of previous subarray
startIndex = i-1;

} else {
mMap.put(i, arr[i]);
largestSoFar++;
if (i == arr.length - 1) {
indices.put(startIndex, i);
}
}

if (currentLargest < largestSoFar) {
currentLargest = largestSoFar;
}
}

int endIndex = 0;
int difference = 0;
for (Integer start : indices.keySet()) {
if (difference < Math.abs(start - indices.get(start))) {
difference = Math.abs(start - indices.get(start));
startIndex = start;
endIndex = indices.get(start);
}
}
System.out.println("The largest subarray was " + currentLargest + " from index: " + startIndex +
" to index: " + endIndex);
System.out.println("Displaying the subarray");
for (int j = startIndex; j <= endIndex; j++) {
System.out.print(arr[j] + " ");
}
}