Two Pointer Two Sum

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.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• 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, 7], 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