DEV Community

Cover image for About the Two Pointer Technique
Kenta Takeuchi
Kenta Takeuchi

Posted on • Originally published at bmf-tech.com

About the Two Pointer Technique

#twopointertechnique #twopointerapproach

This article was originally published on bmf-tech.com.

Overview

This post summarizes the Two Pointer Technique.

In English, it is called the Two Pointer Approach or Two Pointer Technique.

What is the Two Pointer Technique?

It is an algorithm that maintains the indices of the right and left ends of a dataset (such as a sequence or string) and moves the indices based on certain conditions to search for data that meets those conditions.

It is useful when you want to search for data that meets specific conditions within a range.

Example Problem

Write a function to find how many pairs of numbers in array n are less than a specified number m.

For example, if n = [1, 3, -1, 2] and m = 4, there are four pairs that meet the criteria: (1, -1), (1, 2), (3, -1), and (-1, 2), so the function should return 4.

The code for a straightforward implementation of the function is as follows:

func findPairs(n []int, m int) int {
    rslt := 0
    for i := 0; i < len(n); i++ {
        for j := i+1; j < len(n); j++ {
            if (n[i] + n[j]) < m {
                rslt++
            }
        }
    }
    return rslt
}
Enter fullscreen mode Exit fullscreen mode

This results in a time complexity of O(N^2), so we use the Two Pointer Technique to reduce it to O(N log N).

func findPairs(n []int, m int) int {
    sort.Ints(n)
    cnt, l, r := 0, 0, len(n)-1
    for l < r {
        if n[l] + n[r] < m {
            cnt += r-l
            l++
            continue
        }
        r--
    }
    return cnt
}
Enter fullscreen mode Exit fullscreen mode

By repeating until the left and right indices overlap, you can explore all pairs that meet the conditions.

Sorting is done to make it easier to efficiently find pairs.

Although r-l might seem counterintuitive, since the code is for finding pairs, it focuses on counting pairs by indices rather than the values themselves in the array, resulting in this kind of code.

References

Top comments (0)