twoslow's blog

Two Pointer Elegant Implementation
By twoslow, 5 years ago, In English

The two Pointer algorithm is quite popular technique. Although the idea is straightforward, Its implementation is prone to bugs. Few such bugs includes:

  • Index out of range error leading to SEGSEV
  • Never ending while loops leading to SIGKILL

How to write in a way such that there is less chances of bugs?

This blog is a sister blog of Binary Search Elegant Implementation. Your thoughts and implementations are valuable to community, hence welcome.

Thanks. Have a great time ahead!

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 5   Vote: I like it +43 Vote: I do not like it 
for (int l = 0, r = 0; l < n; remove(l++)) {
    while(!ok())
        add(r++);

    if(r > n + 1)
        break;

    // do something with segment [l, r), that is ok()
}
→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it 
int a = 1, b = 1;
while (a <= n && b <= m) {
if (something1) {
 a++;
 // calc ans...
} else if (something2) {
 b++;
 // calc ans...
} else {
// may be
 a++;
 b++;
}
}
while (a <= n) {
 a++;
 if (something1) {
 // calc ans...
 }
}
while (b <= m) {
 b++;
 if (something2) {
 // calc ans...
}
}
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Copy tourist's code.

→ Reply