Mixing
Maximal unique continuous subsequence
Maximal unique continuous subsequence
Given a sequence of integer numbers:
a[0], a[1], a[2], ..., a[n]
Subsequencea[i]...a[j] is unique if the following is true:
a[i]...a[j]
for each x, y between i and j and x != y:
a[x] != a[y]
I need to find length of maximal unique, continuous subsequence
My approaches:
I tried many heuristic approaches, but they didn't work.
Then I wrote bruteforce, it gave O(n^3) complexity, which is impossible to calc if n = 10^6
O(n^3)
n = 10^6
ans = 1
for i in [0, n]
for j in [i, n]
if unique a[i]...a[j]
ans = max(ans, j-i+1)
I think it is typical dp problem, but don't know how to proceed
dp
4 Answers
4
Create hashmap (or use boolean array if range of values is rather short).
Make two indexes - left and right, set them in the beginning.
left
right
Move right index. At every step check if t = A[right] already is in map. Stop when true.
right
t = A[right]
Move left index, removing A[left] from map until value equal to t is met.
left
A[left]
t
Repeat move steps until sequence end
The largest difference between right and left is needed maximal length
right
left
What's this meaning?
if unique a[i]...a[j]
(.i mean in coding language.)
This can be done in O(n).
You can use a hashmap or an Object in case of Javascript. Then keep a variable to track the maximum length of subsequence so far.
On each iteration just check if that value is present in hash map or not.
var map = {}
var arr = [2,3,4,5,1,3,2];
var ans = 1, currentSeqLength = 0;
for(var i=0; i<arr.length; i++){
if(arr[i] in map) currentSeqLength = 0;
else map[arr[i]] = true;
currentSeqLength++;
ans = Math.max(ans, currentSeqLength);
}
console.log(ans); // 5 i.e. Length of 2,3,4,5,1
The search in the map is O(log(n)), so together this makes O(n*log(n)).
– Dominique
Jun 29 at 13:15
In Javascript searching key in object is
O(1), Performance of key lookup in javascript object.– Ishpreet
Jun 29 at 18:29
O(1)
First of all, we could somewhat limit the operations using the following observation: if we found some unique sequence, then we don't have to check any sequence which is shorter. So we iterate j in [i+ans, n].
j in [i+ans, n]
Next, if we know that uniqueness breaks for sequence from i to j, we don't have to expand it any further - we know that no longer sequence with i as start would be unique. So on the else statement of your check we just break the inner loop.
i
j
i
else
This way the iterations count seems to be something like O(n), since the j index will never go back.
O(n)
j
upd: About the Ishpreet's answer (since I can't comment yet, I'll post it here).
This code won't work properly for sequences where the longest subsequence is not the first one. For example, consider this array: [2,3,4,3,1,5,2]. The correct answer would be 5 - the length of 4,3,1,5,2; but the answer given by the code above will be 3. The reason is that this code essentially drops all the sequence collected before the first duplicate came, which is not what we need, since we could take the part after the first duplicating number, including the second (which is not duplicating now) - like in this example.
[2,3,4,3,1,5,2]
5
4,3,1,5,2
3
Furthermore, this approach suffers from one fundamental problem. If we don't store (or otherwise check) the duplicate position, we can't know if it ever interfere with currently found subsequence, and so we don't know how much exactly we must drop (and do we need at all). It might be way before current subsequence started, shadowed by another duplicate; or it may be just here, in the previous number, forcing us to start anything from scratch.
Here's a piece of code trying to cover these cases (but it is yet to check its full correctness):
var map = {}
var arr = [2,3,4,4,5,1,6,2,8,5,9,3];
var ans = 1, currentSeqLength = 0;
for(var i=0; i<arr.length; i++){
if(arr[i] in map && map[arr[i]] >= i - currentSeqLength) {
currentSeqLength -= map[arr[i]];
} else {
currentSeqLength++;
}
map[arr[i]] = i;
ans = Math.max(ans, currentSeqLength);
}
console.log(ans); // 6 i.e. Length of 4,5,1,6,2,8
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
for each x, y between i and j and x != y: a[x] != a[y]
– oybek
Jun 29 at 11:47