DEV Community

Alex
Alex

Posted on

Two pointers algorithm explained

I want to explain a simple and effective technique that you can use in an interview when dealing with Arrays, Strings, Linked Lists, etc. This will also improve your fundamental knowledge about these data structures.

Let’s start from theory. There are two common use cases of this algorithm:

  • left/right The central concept of this algorithm is to have two integer variables that will move from both sides of a string or array. Usually, people call it left and right. The left will move from the 0 index to the length — 1, and the right is the opposite.

  • slow/fast Pointers run in the same direction, e.g., from start to end, but one pointer runs faster than another. In this case, people usually call variables slow and fast.

Algorithms are elementary, and the best way to understand them is to look into some examples.

First, let’s look at a case with left and right pointers. Here is an elementary example of a problem we can solve using this algorithm. The goal is clear: we want to find a pair whose sum will equal a given number.
The brute force approach will create nested loops, but there’s a low chance of passing the interview using it.
A better approach would be to use the two pointers algorithm and find it in one loop to have O(n) complexity instead of O(n²)

const findPair = (arr, target) => {
    let left = 0;                 // Start with two pointers left from start, right, from the end
    let right = arr.length - 1;

    while (left < right) { // when pointers meet, finish loop
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [arr[left], arr[right]];  // Return the pair if we find the target sum
        } else if (sum < target) {
            left++;  // Move left pointer to the right if sum is less than target
        } else {
            right--;  // Move right pointer to the left if sum is greater than target
        }
    }

    return null;  // Return null if no such pair exists
}

const arr = [1, 2, 3, 4, 6];
const target = 6;

findPair(arr, target);  // Output: [2, 4]
Enter fullscreen mode Exit fullscreen mode

Let’s switch to an approach where pointers have different speeds. It’s a frequent problem which you can meet an interview. You need to find the middle of the given Linked List.
The brute force approach is not as bad as the previous example, but the interviewer expects a better one.
With two pointers algorithm, you will solve this problem with O(n) complexity, whereas the brute force approach will take O(2n) if you use two sequential loops.

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

const findMiddle = (head) => {
    if (!head) return null;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;           // Move slow pointer one step
        fast = fast.next.next;      // Move fast pointer two steps
    }

    return slow;  // Slow pointer will be at the middle
}

// Creating a linked list 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

findMiddle(head).value);  // Output: 3 (middle node)
Enter fullscreen mode Exit fullscreen mode

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (0)

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay