Two Pointer Two Sum - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10 mins
  • 🛠️ Topics: Arrays, Two-Pointer Technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the function?

    • A: The input is a sorted list of integers nums and an integer target.

  • Q: What is the expected output of the function?

    • A: The function should return a list containing the indices of the two numbers that add up to target.

  • Q: What assumptions can be made about the input?

    • A: It can be assumed that there is exactly one solution, and no element can be used twice. The input list is sorted in ascending order.

  • Q: What should the function return if the input list is empty?

    • A: Since the problem guarantees a solution, the list should not be empty, and the function is expected to return a valid pair of indices.

  • The function two_sum() should return the indices of two numbers in the sorted list nums that add up to the given target.

HAPPY CASE
Input: nums = [2, 7, 11, 15], target = 9
Expected Output: [0, 1]

UNHAPPY CASE
Input: nums = [2, 7, 11, 15], target = 18
Expected Output: [1, 2]

EDGE CASE
Input: nums = [1, 2], target = 3
Expected Output: [0, 1]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers, one starting at the beginning of the list and the other at the end, to find the two numbers that sum to the target.

1. Initialize two pointers: `left` at 0 and `right` at the last index of the list.
2. While `left` is less than `right`:
   a. Calculate the sum of the elements at the `left` and `right` pointers.
   b. If the sum equals the `target`, return the indices of the two numbers.
   c. If the sum is less than the `target`, increment the `left` pointer.
   d. If the sum is greater than the `target`, decrement the `right` pointer.
3. The function assumes that the input has exactly one solution

⚠️ Common Mistakes

  • Not handling the sorted nature of the input list.
  • Mismanaging indices while incrementing or decrementing the pointers.

I-mplement

Implement the code to solve the algorithm.

def two_sum(nums, target):
    # Initialize two pointers
    left = 0
    right = len(nums) - 1
    
    # Iterate through the list
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1