The strategy repeats from end to beginning, remembering when you last saw each integer. For instance. somewhere in the middle, the last time you saw 1 was at index 15, 2 at index 20, 3 at index 17. The length of the interval is the maximum indicator that you last saw something minus your current index.
To easily find the maximum index, you should use a self-balancing binary search tree (BST), since it has O(log n) insert and delete times and a constant search time for the largest index.
For example, if you need to update the index in which you last saw 1, you delete the current last seen index (15) and insert the new last seen index.
By updating the self-balancing BST with all the trailing indices allowed by each integer type, we can select the largest and say that we can end there.
The exact code depends on how the input is determined (for example, did you know that all integers, i.e. you know that there are integers from 1 to 4 in the array, then the code is simplified).
Iteration O(n) , BST - O(log n) . In general, O(n log n) .
Implementation Details
Doing this requires a bit of work.
Initialize:
- interval length for each starting index.
- an array the last time you saw a certain integer. (If you do not know what possible integers can be in the array, instead of using a regular array, use an associative array (for example,
map<> in C ++)). - a heap of type of priority queue type, where the vertex of the queue is the maximum integer in it. You should be able to easily remove things from it, so use a self-balancing binary search tree
Now inside the loop (loop index from the end of the input array to the beginning of the input array),
You can update your last seen array for this particular index.
Just check which integer you see and update the entry in the last index array in question.
Using before and after in the last array seen, update the BST (remove the old end index, add a new index)
The update interval length for this start index, based on the maximum end index required (from BST).
If you see an integer that you have not seen before, invalidate all interval lengths to run indexes on that index (or just avoid updating the interval length until all integers are visible at least once).
C ++ code execution
- Assuming all the integers 0- (k-1) are in the input array
- Disclaimer: Unverified
- 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;
source share