Two Sum II – Input Array Is Sorted

My Thinking and Approach

---

Introduction

In this problem, I was given a sorted array of integers and asked to find two numbers such that their sum equals a given target.

Since the array is already sorted, this helps in finding a more optimal solution.

---

Problem Statement

• Given a sorted array of integers numbers
• Given an integer target
• Return indices of two numbers such that:

numbers[index1] + numbers[index2] = target

• Conditions:

  • Array is 1-indexed
  • 1 ≤ index1 < index2 ≤ numbers.length
  • Only one valid solution exists
  • Cannot use the same element twice
  • Use only constant extra space

---

My Initial Thought

At first, I considered:

• Using two loops
• Checking all possible pairs

But this approach takes more time and is not efficient.

---

Key Observation

Since the array is sorted:

• Small values are on the left
• Large values are on the right

So, I can use two pointers:

• One starting from the beginning
• One starting from the end

---

Optimized Approach

I decided to:

• Use two pointers
• Adjust them based on the sum

Logic:

• If sum is equal to target → return indices
• If sum is less than target → move left pointer forward
• If sum is greater than target → move right pointer backward

---

My Approach (Step-by-Step)

1. Initialize two pointers:

• left = 0

• right = length - 1

  1. While left < right:

• Calculate sum = numbers[left] + numbers[right]

• If sum equals target
  → return [left + 1, right + 1]

• If sum < target
  → move left pointer forward

• If sum > target
  → move right pointer backward

---

Code (Python)

Below is the implementation clearly separated inside a code block:

def twoSum(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

---

Example Walkthrough

Input:

numbers = [2, 7, 11, 15], target = 9

Steps:

• left = 0, right = 3 → sum = 17 → move right
• left = 0, right = 2 → sum = 13 → move right
• left = 0, right = 1 → sum = 9 → found

Output:

[1, 2]

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

---

Key Takeaways

• Sorted array helps in optimization
• Two pointer technique is efficient
• No extra space is required

---

Conclusion

This problem helped me understand how to use the two pointer technique effectively.

Instead of using extra space, I used the sorted property of the array to achieve an optimal solution.

---