Two Pointer

May 29, 2020 DSA

Typically problems with subarrays with <= k elements with property with P.

Two pointers can be applied when for an L there exists an optimal R. and for L` there exists optimal R` and satisfies L<L` and R<= R`.

Template

initialise head = -1, tail = 0 (empty subarray if head<tail) initialise ds. while(tail<n){

1. move head as far as possible till property is satisfied
2. process current window, update ds
3.    if (head>=tail) update ds
    else head = tail
    tail++; }

Application 1

Count no. of subarrays with certain property (ans += head -tail +1) Maxlen or Minlen