minimum interval of an array of unique elements

Question

How can i find the minimum interval of an integer array in which all the unique elements of that array are present . For example my array is : 1 1 1 2 3 1 1 4 3 3 3 2 1 2 2 4 1 minimum interval is from index 3 to index 7. I'm looking for an algorithm of O(nlogn) or less (n<=100000)

Answer 1

The strategy is iterate from the end to the start, remembering when you last saw each integer. Eg. somewhere in the middle, you last saw 1 at index 15, 2 at index 20, 3 at index 17. The interval length is the maximum index you last saw something minus your current index.

To find the maximum index easily, you should use a self-balancing binary search tree (BST), because it has O(log n) insert and removal time, and constant lookup time for the largest index.

For example, if you have to update the index you last saw a 1, you remove the current last seen index (the 15), and insert the new last seen index.

By updating the self balancing BST with all the end indices allowed by each integer type, we can pick the largest, and say that we can end there.

The exact code depends on how the input is defined (eg. whether you know what all the integers are, ie. you know there exists all integers between 1 and 4 in array, then the code is simplified).

Iteration is O(n), the BST is O(log n). Overall is O(n log n).

---

Implementation Details

Implementation of this takes a little bit of work.

Initialize:

• the interval length for each starting index.
• an array for when you last saw a certain integer. (If you don't know what possible integers might be in the array, instead of using a normal array, use an associative array (eg. map<> in C++)).
• a priority queue-like type heap, where the top of the queue is the maximum integer in it. You need to be able to easily remove stuff from it, so use a self-balancing binary search tree

Now inside the loop (looping index from end of input array to start of input array),

• You can update your last seen array for this particular index.

  Just check what integer you see, and update the entry in the index last seen array.

• Using before and after in the last seen array, update the BST (remove old end index, add new index)

• Update interval length for this starting index, based on largest end index required (from BST).

• If you see an integer you haven't seen before, invalidate all interval lengths for starting indices above this index (or just avoid updating interval length until all integers have been seen at least once).

---

C++ code implementation

• Assuming all integers 0-(k-1) are found in input array
• Disclaimer: untested
• ignores #include and main function

Code:

int n=10,k=3;
int input[n]=?;
unsigned int interval[n];
for (int i=0;i<n;i++) interval[i]=-1; // initialize interval to very large number
int lastseen[k];
for (int i=0;i<k;i++) lastseen[i]=-1; // initialize lastseen
multiset<int> pq;

for (int i=n-1;i>=0;i--) {
  if (lastseen[input[i]] != -1) // if lastseen[] already has index
    pq.erase(pq.find(lastseen[input[i]])); // erase single copy
  lastseen[input[i]]=i; // update last seen
  pq.insert(i); // put last seen index into BST
  if (pq.size()==k) { // if all integers seen (nothing missing)
    // get (maximum of endindex requirements) - current index
    interval[i] = (*pq.rbegin())-i+1;
  }
}
// find best answer
unsigned int minlength=-1;
int startindex;
for (int i=0;i<n;i++) {
  if (minlength>interval[i]) { // better answer?
    minlength=interval[i];
    startindex=i;
  }
}
// Your answer is [startindex,startindex+minlength)