Limited Time Offer:30% off Hello Interview Premium 🎉

Main

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Practice

Learn

System Design

ML System Design

DSA

Behavioral

Salary Negotiation

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Discord

Refer a Friend

Pricing

Become a Coach

Pricing Become a Coach

Get Premium

Two Pointers

Two Sum (Sorted)

medium

DESCRIPTION (credit Leetcode.com)

Given a sorted array of integers nums, determine if there exists a pair of numbers that sum to a given target.

Example 1:

Input:


nums = [1,3,4,6,8,10,13]
target = 13

Output:


True # (3 + 10 = 13)

Example 2:

Input:


nums = nums = [1,3,4,6,8,10,13]
target = 6

Output:


False

Solution


def twoSum(nums, target):
  left, right = 0, len(nums) - 1
      
  while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum == target:
        return True

    if current_sum < target:
        left += 1
    else:
        right -= 1
      
  return False

two sum algorithm

0 / 7

Explanation

Because the input is sorted, we can solve this question in O(n) time and O(1) space using the two-pointer technique by eliminating unecessary pairs from our search.

Let's say we want to find a pair of numbers that sum to 13 in the following array:

We start by initializing two pointers at opposite ends of the array, which represent the pair of numbers we are currently considering. Note that this pair has a sum (14) that is greater than our target (13). Also note that if we laid out all possible pairs sums in our array and sorted them, this pair sits right in the middle.

Because our array is sorted, all other pairs using 13 (the element at our right pointer) also have sums greater than our target, as they all use numbers greater than 1 (the element at our left pointer).

So, we move our right pointer back, which elimininates those unecessary pairs from our search, and arrive at the next pair to consider.

Now, since our sum is less than our target, we know that all other pairs using 1 also have sums less than our target. So, we move our left pointer forward to eliminate those unnecessary pairs and arrive at the next pair to consider.

This continues until either our pointers meet (in which case we did not find a successful pair) or until we find a pair that sums to our target, like we did here.

Summary

We initialize our two pointers at opposite ends of the array, and start our search.
If the sum of the current pair is greater than our target, we move our right pointer back. If it is less than our target, we move our left pointer forward.
Each time we move a pointer, we eliminate unecessary pairs from our search.
We continue this process until either our pointers meet or until we find a pair that sums to our target.
While this question is on the easier side for many coding interviews, it's a key step in harder questions such as 3Sum and 3Sum closest, which start by sorting an unsorted array in order to use the two-pointer technique described here.

Next: Overview

Your account is free and you can post anonymously if you choose.

Sort By

Two Pointers

Two Sum (Sorted)

DESCRIPTION (credit Leetcode.com)

Solution

Explanation

Summary

Questions

Learn

Links

Legal

Contact