DEV Community

Tammy Vo
Tammy Vo

Posted on

2 1

Two Pointer Technique

When to use: Optimal way to solve problems related to arrays, strings and linked list in O(N) time.

Arrays/Strings: Two pointers, each starting from the beginning and the end until they both meet.
Example Problem: Two Sum II - Input Array Is Sorted

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer technique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Linked List: One pointer moving at a slow pace, while the other pointer moves at twice the speed.
Example Problem: Linked List Cycle

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)

AWS GenAI LIVE image

Real challenges. Real solutions. Real talk.

From technical discussions to philosophical debates, AWS and AWS Partners examine the impact and evolution of gen AI.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay