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

**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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> #include <vector> using namespace std; // Function to check if sub-array A[i..j] is formed by consecutive // integers. Here min and max denotes the minimum and maximum element // in the sub-array respectively bool isConsecutive(int A[], int i, int j, int min, int max) { // in order for an array to contain consecutive integers, the diff // between maximum and element element in it should be exactly j-i if (max - min != j - i) return false; // create a visited array (we can also use a set) vector<bool> visited(j - i + 1); // traverse the sub-array and checks if each element appears only once for (int k = i; k <= j; k++) { // if element is seen before, return false if (visited[A[k] - min]) return false; // mark element as seen visited[A[k] - min] = true; } // we reach here when all elements in array are distinct return true; } // Find largest sub-array formed by consecutive integers void findMaxSubArray(int A[], int n) { int len = 1; int start = 0, end = 0; // consider each sub-array formed by A[i..j] // i denotes the beginning of sub-array for (int i = 0; i < n - 1; i++) { // stores minimum and maximum element in an sub-array A[i..j] int min_val = A[i], max_val = A[i]; // j denotes the end of sub-array for (int j = i + 1; j < n; j++) { // update minimum and maximum element of the sub-array min_val = min(min_val, A[j]); max_val = max(max_val, A[j]); // check if subarray A[i..j] is formed by consecutive integers if (isConsecutive(A, i, j, min_val, max_val)) { if (len < max_val - min_val + 1) { len = max_val - min_val + 1, start = i, end = j; } } } } // print maximum length sub-array cout << "The largest sub-array is [" << start << ", " << end << "]"; } // main function int main() { int A[] = { 2, 0, 2, 1, 4, 3, 1, 0 }; int n = sizeof(A) / sizeof(A[0]); findMaxSubArray(A, n); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
import java.lang.Math; class MaxSubArray { // Function to check if sub-array A[i..j] is formed by consecutive // integers. Here min and max denotes the minimum and maximum element // in the sub-array respectively static boolean isConsecutive(int A[], int i, int j, int min, int max) { // in order for an array to contain consecutive integers, the diff // between maximum and element element in it should be exactly j-i if (max - min != j - i) { return false; } // create a visited array (we can also use a set) boolean visited[] = new boolean[j - i + 1]; // traverse the sub-array and checks if each element appears // only once for (int k = i; k <= j; k++) { // if element is seen before, return false if (visited[A[k] - min]) { return false; } // mark element as seen visited[A[k] - min] = true; } // we reach here when all elements in array are distinct return true; } // Find largest sub-array formed by consecutive integers public static void findMaxSubArray(int[] A) { int len = 1; int start = 0, end = 0; // consider each sub-array formed by A[i..j] // i denotes the beginning of sub-array for (int i = 0; i < A.length - 1; i++) { // stores minimum and maximum element in an sub-array A[i..j] int min_val = A[i], max_val = A[i]; // j denotes the end of sub-array for (int j = i + 1; j < A.length; j++) { // update minimum and maximum element of the sub-array min_val = Math.min(min_val, A[j]); max_val = Math.max(max_val, A[j]); // check if A[i..j] is formed by consecutive integers if (isConsecutive(A, i, j, min_val, max_val)) { if (len < max_val - min_val + 1) { len = max_val - min_val + 1; start = i; end = j; } } } } // print maximum length sub-array System.out.println("The largest sub-array is [" + start + ", " + end + "]"); } // main function public static void main (String[] args) { int[] A = { 2, 0, 2, 1, 4, 3, 1, 0 }; findMaxSubArray(A); } } |

`Output:`The largest sub-array is [1, 5]

The time complexity of above solution is O(n^{3}) 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. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

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

Thank you for posting so many helpful practice problems!

hey

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

We need a window size for this approach. Here we don’t have the window size to slide. We need to detect the max size of sub array possible. If the question would have been to detect sub array of consecutive numbers of length K then this approach can be useful.

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…

O(n) solution in swift – Feel free to test on Xcode 10.0

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Logic:

1. Define a dictionary that holds key:value pairs where key = array element & value = element position in array

2. Traverse through the input array

3. If element previously present in dictionary – we know that we have reached a duplicate element

So capture current startIndex and endIndex. If difference between startIndex and endIndex is greater than maximum length seen so far – update the maxStartIndex and maxEndIndex.

4. Increment startIndex to endIndex + 1. This is to start a new subArray excluding the previous array found.

5. Else if element not previously present in dictionary – simply increment the endIndex of the current SubArray under consideration.

6. Insert every new element as we traverse through the array into the dictionary along with its associated array index.

7. Finally print out the maxStartIndex & maxEndIndex to get the start and end index of the maximum subarray of consecutive numbers.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Code:

func findLargestSubArrayOfConsecutiveNumbers(inputArray: [Int]){

/* Handling edge cases like empty Array. You can handle null cases as well */

guard !inputArray.isEmpty else{

print(“Empty Array”)

return

}

/* Declare variables */

var dict = [Int: Int]()

var startIndex = 0

var endIndex = 0

var maxLength = 0

var maxStartIndex = 0

var maxEndIndex = 0

/* Traverse through the array */

for (index, value) in inputArray.enumerated(){

/* If a duplicate is found */

if let recordedIndex = dict[value]{

/* Capture the subArray if and only if it is the maximum length subArray seen so far */

if endIndex – startIndex > maxLength{

maxLength = endIndex – startIndex

maxStartIndex = startIndex

maxEndIndex = endIndex

}

/* Let go of the above sub array and start a new one */

startIndex = recordedIndex + 1

}else{

/* If duplicate not encountered – simply increment end Index */

endIndex = index

}

/* Insert every element of the array encountered into dictionary with its associated index */

dict[value] = index

}

print(“Largest SubArray of Consecutive numbers = [\(maxStartIndex), \(maxEndIndex)]”)

}

/* Call the above method */

findLargestSubArrayOfConsecutiveNumbers(inputArray: [0,0,0,1,2,5,4,1])

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 🙂

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

http://ideone.com/87Hzjc

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

uniqueintegers” ? Or is it something else?Hi Sam, thanks for sharing your concern, Your understanding is right about consecutive integers. If you sort 0,2,1,4,3 you will get 0,1,2,3,4 which are consecutive. Hope the question is clear now. Happy coding 🙂

https://ideone.com/PhXLY1

True Answer

js in O(n^2)

https://jsbin.com/yedeseyepi/edit?js,console

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

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.

Hi TechieDelight, O(n) solution by mapping numbers to their sequence lengths

https://studynotesallenyuan.wordpress.com/2018/09/24/longest-consecutive-sequence/

Edit: this is for subsequence. Question given is for contiguous subarray

This can be solved in O(n) by storing the element in a map {item -> position} and keeping track of the longest sub-array with no duplicate element. Scan through the array storing {item, position}. if the same element is found capture the current sub-array and update the start index of the next sub array . Take the longest one.

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

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.

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] + " ");

}

}