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

Question

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
});

Answer 1

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