# How to optimize of "Find the largest subarray formed by consecutive integers"

recently solving a data structure question and counter below question

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

2 set of examples as below

input = [2, 0, 2, 1, 4, 3, 0, 0]; // Output: The largest subarray is [ 0, 2, 1, 4, 3 ]

input= [2, 0, 2, 0, 4, 3, 0, 0]; // Output: The largest subarray is [2, 0, 4, 3]

below is my implementation but its seems me too naïve and complex , someone suggest me how to optimize it

const largestSubArray = (arr) => {
// first check whether array have any suplicate value
const hasDuplicate = arr.some((a, i, arr) => arr.indexOf(a) !== i);
// console.log({hasDuplicate});
if (!hasDuplicate) {
return arr;
} else {
const indexedArray = [];
for (let i = 0; i < arr.length; i++) {
let curr = arr[i];
for (let j = i + 1; j < arr.length; j++) {
let next = arr[j];
// if having duplicate value then set the index of both element in indexedArray
if (next === curr) {
indexedArray.push([i, j]);
break;
}
// if reach end of array and found no duplicate value
if (j === arr.length - 1) {
indexedArray.push([i, j]);
}
}
}
// console.log({indexedArray});
// create new array which hold difference between duplicate value index position
let op = [];
for (const [i, j] of indexedArray) {
const diff = j - i;
op.push(diff);
}
// find maximum differnce value
const maxx = Math.max(...op);
const mIndex = op.indexOf(maxx);
// retrive maximum diffrence array from indexedArray
const [min, max] = indexedArray[mIndex];
const output = arr.slice(min, max);
// recursively call for next found array for the same
return largestSubArray(output);
}
};

const inputArray1 = [2, 0, 2, 1, 4, 3, 0, 0];

const result1 = largestSubArray(inputArray1);

const inputArray2 = [2, 0, 2, 0, 4, 3, 0, 0];

const result2 = largestSubArray(inputArray2);

console.log({
result1,
result2
});

• I see two different problems here. "subarray formed by consecutive integers" is not the same as "largest subarray of distinct numbers", your examples are not consecutive integers. That is a sequence of numbers where each number is different by one like 1,2,3 or 6,7,8,9. Jan 22, 2022 at 18:31
• The second example [2, 0, 4, 3] leads to a definition a subarray whose values are unique/distinct; consecutive is a bit strong as 1 is missing, and no order. Jan 22, 2022 at 23:07
• (tl;dr) For [2, 0, 2, 0, 4, 3, 0, 0] you'll get candidates [2, 0], [0, 2], [2, 0, 4, 3], [4, 3, 0], [0], so with rewinding. Should be rather simple. Jan 22, 2022 at 23:16

You are doing slightly too much.

The logic: a subarray whose values are unique/distinct; consecutive is a bit strong as intermediate numbers may be missing, and there is no order. Basically a set is the right data structure.

For [2, 0, 2, 0, 4, 3, 0, 0] you'll get candidates:

[2, 0], encountering 2
[0, 2], encountering 0
[2, 0, 4, 3], encountering 0
[4, 3, 0], encountering 0
[0].


So, yes you need to maintain the maximum of all candidates. And the current running candidate is complete when a duplicate is encountered. Then a new candidate is started from the running candidate after its duplicate.

I have used java (in simple form), but it should be readable.

    int[] input1 = {2, 0, 2, 1, 4, 3, 0, 0};
int[] output1 = largestDistinctSubarray(input1);
// Output: The largest subarray is [ 0, 2, 1, 4, 3 ]
System.out.printf("%s -> %s%n", Arrays.toString(input1), Arrays.toString(output1));

int[] input2 = {2, 0, 2, 0, 4, 3, 0, 0};
int[] output2 = largestDistinctSubarray(input2);
// Output: The largest subarray is [2, 0, 4, 3]
System.out.printf("%s -> %s%n", Arrays.toString(input2), Arrays.toString(output2));


The algorithm maintains:

• a maxSubLength with its startIndexMax;
• a startIndex and subLength for the current running candidate part; only when a duplicate is encountered, or the end of the loop is reached, you have a new, possibly maximal, candidate. This means a max check inside the loop on duplicate and after the loop.

To look in the loop whether nums[i] is a duplicate, the sub-array has an additional data structure. I use a map to store the the index of a number. This allows fast duplicate detection, and having the index of the original duplicated number.

Finding a duplicate you need to remove for a new sub-array candidate all number upto and including the duplicated number.

int[] largestDistinctSubarray(int... nums) {
int maxSubLength = 0;
int startIndexMax = 0;
int startIndex = 0;
int subLength = 0;
Map<Integer, Integer> subNumToIndex = new HashMap<>(); // Set or LinkedHashMap.
for (int i = 0; i < nums.length && nums.length - startIndex > maxSubLength; ++i) {
int num = nums[i];
if (!subNumToIndex.containsKey(num)) { // Could be combined with subNumToIndex.get.
subNumToIndex.put(num, i);
++subLength;
} else {
// Update max:
if (maxSubLength < subLength) {
maxSubLength = subLength;
startIndexMax = startIndex;
}
// Update running sub-array:
// Reuse the current sub-array after the duplicated number.
int nextStartIndex = subNumToIndex.get(num) + 1;
for (int j = startIndex; j < nextStartIndex - 1; ++j) {
subNumToIndex.remove(nums[j]);
}
subNumToIndex.put(num, i);
startIndex = nextStartIndex;
subLength = i + 1 - startIndex;
}
}
// Update max:
if (maxSubLength < subLength) {
maxSubLength = subLength;
startIndexMax = startIndex;
}
return Arrays.copyOfRange(nums, startIndexMax, startIndexMax + maxSubLength);
}


As you see this code does not side-track to keep extranous data; the Map is the only data structure and serves a functional purpose: speeding things, not needing extra search loops.

Part of the intelligence of the algorithm is based on reusing part of the candidate sub-array (after the duplicated number).

There is a small optimisation, early loop termination when no better solution may be found.

A result of simple code. Your code is probably just 5 lines longer, but my code follows an algorithm (a running sub-array with rewinding).