0
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – jcubic
    Jan 22, 2022 at 18:31
  • \$\begingroup\$ 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. \$\endgroup\$
    – Joop Eggen
    Jan 22, 2022 at 23:07
  • \$\begingroup\$ (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. \$\endgroup\$
    – Joop Eggen
    Jan 22, 2022 at 23:16

1 Answer 1

1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.