Algorithm tricks 1

Trick 1

Considering the following code (*)

int len = 1;
for(int i = 1; i <= n; i++) {
    num[a[i]-1] = 0;
    num[a[i]]++;
    num[a[i]+1] = 0;
    len = max(len, num[a[i]]);
}
cout << len;

“len” variable computed in this case is the length of the longest consecutive subsequence of array a that contains same values

The same approach is applied when we want to find out the length of the longest consecutive subsequence SUB, so that max(SUB) – min(SUB) <= K, by assuming all the values between x and x-K have the same property.

In(*) we: 
set num[a[i]]++;
upper bound and lower bound: num[a[i]-1] = num[a[i]+1] = 0
query result: len = max(len, num[a[i]]);

Similarly we have:
num[a[i]]++, num[a[i]-1]++, num[a[i]-K]++… 
upper bound and lower bound: num[a[i]+1] = num[a[i]-K-1] = 0
query result: len = max(len, num[a[i]], … , num[a[i]-K])

Trick 2

At each specific position i of an 1-dimension array, we can use dynamic programming to query the number of elements that have arbitrary value to the left and to the right of the array, with complexity O(nlogn) using map:

map<int, int> l, r;

for(int i = 1; i <= n; i++)
r[a[i]]++;

for(int i = 1; <= n; i++) {
    r[a[i]]--; // eliminate current element

// TO-DO
// now r[x] is the number of elements: a[0..i-1] = x
// and l[x] is the number of elements: a[i+1..n] = x

l[a[i]]++; // end of loop, i becomes left index
}

Happy coding

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s