-2

Let's say we have an array {7, 3, 7, 3, 1, 3, 4, 1}. What I need is an algorithm (preferably some C++ code sample) which will return length of a minimal sub-array which contains all of the array's elements.

In this case, it would be 5: {7, 3, 1, 3, 4} and this is the shortest sub-array of the original array which contains all of the array's elements, which are 1, 3, 4 and 7.

Also, one more example of the array {2, 1, 1, 3, 2, 1, 1, 3} and the algorithm should return 3 since the subarray we are looking for is {1, 3, 2} (indices 2-4 of the original array).

I found some similar question here: Find minimum length of sub-list containing all elements of a list but it does not seem answered.

The function signature should be like: int algorithm(std::vector<int> &arr){...}

anicicn
  • 183
  • 5
  • 15
  • 1
    Take a look at "Longest Common Subsequence." algorithm. Its originaly for strings, but can be adapted to your problem as well. – Martin Perry Jul 07 '19 at 12:47
  • Where exactly are you stuck? Do you have a more specific question? Are you struggling with C++? Are you unsure as to how the algorithm would work regardless of language? What have you tried? – lurker Jul 07 '19 at 12:47
  • I am struggling regarding C++ implementation. I need C++ code with the given signature. – anicicn Jul 07 '19 at 12:49
  • That is too broad. What exactly are you struggling with? Could you add the code you have and point out where you have a problem with it? – trincot Jul 07 '19 at 13:08
  • Why is it too broad? I just need an algorithm to a clearly defined problem and my solution does not matter since I did it in a wrong way, that's why I am asking for a solution. It is easier to come up with a brand new algorithm design than to rework mine. So what I need is an algorithm, a full approach. – anicicn Jul 07 '19 at 13:10
  • 1
    Possible duplicate of [find minimum-length subarray that has all numbers](https://stackoverflow.com/questions/37194842/find-minimum-length-subarray-that-has-all-numbers) – beaker Jul 07 '19 at 15:27

1 Answers1

1

Find last subarray in O(n) :

For example, for the array [1, 2, 3, 2, 2, 1, 1], get the counts of the items in a hash table/Map (or array for small range) : { 1: 3, 2: 3, 3: 1 }

To find the start index of the subarray, start from the first value in the array and check if it's count is more than 1. If it's count is more than 1, decrease it's count by one, and continue to next value until a value with count of 1. Repeat the same backwards to find the last index of the subarray :

1, 2, 3, 2, 2, 1, 1
      ^        ^

Find the rest of the subarrays in O(n) :

Now to check if that is the minimum subarray, check for subarrays before it. For that, search before the first index for the last index of the value 1 that is at the last index. If it is found, change the first index to it, and decrease the last index by one :

1, 2, 3, 2, 2, 1, 1
^           ^

Now to find the last index of the new subarray, search between the first and last index for the value 2 that is at the last index and change the last index to it : 

1, 2, 3, 2, 2, 1, 1
^        ^

Repeat until the value at the last index can't be found between the first and last index :

1, 2, 3, 2, 2, 1, 1
^     ^

Now check if the count of the new subarray is less than that of the previous subarray and update the indexes of the current minimum subarray if needed.

The search for the rest of the subarrays has to be repeated until the value at the last index can't be found before the first index.

Slai
  • 22,144
  • 5
  • 45
  • 53
  • What would be time complexity for same? Could you write pseudocode, explanation is not so clear. – Poonam Feb 15 '22 at 10:48