As promised I am going to revive this blog of mine. Though I don't have anything specific in mind, I plan to just discuss some cool tricks & problems which I find challenging. While I post stuff here, I expect all the readers to contribute too - in terms of problems and/or solutions.
I am today starting with a technique I call as Rolling Indices.
Sample Problem :
You are given an array of numbers. You want to find if there are two numbers a,b in array such that a + b = S for some constant S. If you don't know the technique yet, you may like to give this problem a little thought.
Naive Brute Force Solution :
Run over three counters say i,j & check if A[i] + A[j] = S. This takes O(N^2) time & is clearly costly.
A better solution :
Sorting is cheap here compared to time we already have. But after sorting we can do a binary search. So just run over one counter say i & do a binary search for S - A[i] in array. This takes time O ( N * log N) in sorting & same in processing. Little fast ! Fast enough yet ? No !
Rolling Indices technique :
Lets sort the array. & run on two indices say i & j ( yes these would be our rolling indices ) . We want to check as before if A[i] + A[j] = S or not. If A[i] + A[j] = S then you are really done. What if its not the case ? Maybe A[i] + A[j] > S. But pause here & ask yourself is this current value of i of any use at all ? All values of i & j you are going to consider hence after would give only a higher sum of A[i] + A[j] ( Array is sorted, remember ! ) which would not match S & so its no use to consider A[i] ever. Just forget this i & increment.
What if A[i] + A[j] < S ? Simple. We have not yet considered all possibilities of i yet. Just increment j.
Analysis : We took O(N * log N ) time in sorting. Lets forget that & look at processing phase. In each step we move i or j. We can't take more then 2 * N steps before we can't do anything . So processing is O(N)
This looks like an innocent & simple technique. In fact its as costly as binary search one with sorting being the bottle neck. But this was a sample problem just to introduce to concept of rolling , I can assure you that in "real" problems this is amazingly good. In particular sorted sequences arise naturally usually ( like prefix sums of positive numbered arrays ). Anycase tougher problems take more then N * log N time anyway so soring becomes cheap. Also this is trivially easy to implement & admits very neat & short code.
If you want to try more : try solving these :
1) Find if there are 3 indices i, j, k such that A[i] + A[j] = A[k] . Try for O(N^2).
2) You are given a rectangle with each entry being 0 or 1. Find if there is a sub matrix with sum exactly S. Try for O(N^3) algorithm.
3) If you really want an advanced problem try Hungry Bear from codechef.
I welcome any readers post any problem link or code for any problem solvable by this technique.
PS:
- I realized only mid way , a post on prefix sums should ideally be there before this one . So give me some time & I should be posting on prefix sums soon.
