this blog is an animated explanation of two pointers method
as two pointers is not really considered an algorithm this blog will only talk about famous problems and how they are handled.
this blog is not supposed to be hard it is targeted for under 1400 rating
this blog was made to summarize HCPC-2025 training for two pointers at Homs university / Syria.
overview
1. check if an array is sub sequence of another array
2. check if an array is sub array of another array
3. number of less or equal
4. merge two sorted arrays
5. number of sub arrays with sum less than or equal $$$X$$$
6. number of sub arrays with number of distinct elements less than or equal $$$X$$$
lets start:
1. check if an array is sub sequence of another array
checking that is relatively easy (easier than checking is sub array)
name the arrays $$$a$$$,$$$b$$$ we need to check if $$$a$$$ is sub sequence of $$$b$$$ keep two pointers in $$$a$$$ and $$$b$$$ pointing to the first element
keep increasing $$$b$$$'s pointer and then for each matching increase $$$a$$$'s pointer
if(a[i]==b[j]){
i++;
}
j++;
2. check if an array is sub array of another array
given arrays $$$a(n)$$$ and $$$b(m)$$$ check if $$$a$$$ is sub array of $$$b$$$
here we could use two pointers $$$l$$$ and $$$r$$$ pointing to positions in $$$b$$$
first $$$l=1,r=0$$$
increase r by 1
and while the sub array $$$b[l:r]$$$ is not a prefix of $$$a$$$ keep increasing $$$l$$$
the brute force implementation is $$$O(m*n)$$$ but $$$kmp$$$ algorithm improves this to $$$O(n+m)$$$
the idea of $$$kmp$$$ is :
instead of increasing $$$l$$$ one by one
just for each prefix of $$$a$$$ store the longest prefix that is also a suffix of that prefix
and by knowing this info we could know how much exactly to increase $$$l$$$ and we do not need to check if it is a prefix anymore
$$$kmp$$$ is out of topic for now
3. number of less or equal
given two sorted arrays $$$a(n)$$$ and $$$b(m)$$$
for each element in $$$a$$$ count how many elements in $$$b$$$ that are less than or equal it
the idea is two keep a pointer $$$i=0$$$ in $$$a$$$ and $$$j=0$$$ in b
increase $$$i$$$ and while $$$j+1 \lt =m$$$ and $$$b(j+1) \lt =a(i)$$$ increase $$$j$$$
the answer for the element $$$a(i)$$$ is $$$j$$$ now
the idea is that we do not reset $$$j$$$ at each $$$i$$$ because the arrays are sorted
this means if $$$a(i) \gt =b(j)$$$ then $$$a(i+1) \gt =b(j)$$$
time complexity $$$O(n+m)$$$
4. merge two sorted arrays
given two sorted arrays $$$a(n)$$$ and $$$b(m)$$$
keep two pointers referring to the beginning of each array $$$i=1$$$ $$$j=1$$$
if $$$i \lt =n$$$ and $$$j \lt =m$$$ then append the smallest element to the resulting array and increase the pointer pointing to it
else append the elements remaining in one of them
time complexity $$$O(n+m)$$$
5. number of sub arrays with sum less than or equal $$$X$$$
given the array $$$a(n)$$$ we use two pointers $$$l=1,r=0$$$ and keep track of the $$$sum$$$
while $$$l \lt =n$$$
we add the element $$$a(r+1)$$$ if $$$sum+a(r+1) \lt =X$$$ and $$$r+1 \lt =n$$$
now the answer for $$$l$$$ is the number of sub arrays starting at $$$l$$$ which is $$$r-l+1$$$
and then subtract $$$a(l)$$$ from the sum (if $$$l \lt =r$$$) and increase $$$l$$$
the final answer is the sum of answers at each index
6. number of sub arrays with number of distinct elements less than or equal $$$X$$$
the same idea of the previous one
but we increase $$$r$$$ only if the number of distinct elements after inserting $$$a(r+1)$$$ does not exceed X
we can use std::map for this
how to count number of sub arrays with number of distinct elements strictly greater than $$$X$$$ ?
just subtract the answer of the previous problem from $$$n(n+1)/2$$$
