🧠 Two Sum II – Input Array Is Sorted (Python)

Hi All,

Today I solved another interesting problem from LeetCode: Two Sum II – Input Array Is Sorted.

---

📌 Problem Statement

Given a sorted array of integers numbers and a target value, return the indices of two numbers such that they add up to the target.

Conditions:

• Array is 1-indexed (index starts from 1)
• Array is already sorted (non-decreasing)
• Exactly one solution exists
• Cannot use the same element twice
• Must use constant extra space

---

💡 Approach

🔹 Key Idea:

Since the array is sorted, we can use the Two Pointer Technique instead of a hash map.

---

🔹 Steps:

1. Initialize two pointers:
   • left = 0
   • right = len(numbers) - 1
2. Calculate sum:
   • If sum == target → return indices
   • If sum < target → move left pointer
   • If sum > target → move right pointer

---

💻 Python Code

class Solution:
    def twoSum(self, 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]  # 1-indexed
            elif current_sum < target:
                left += 1
            else:
                right -= 1

---

🔍 Example Walkthrough

Input:

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

Steps:

• left = 0 (2), right = 3 (15) → sum = 17 → too big → move right
• left = 0 (2), right = 2 (11) → sum = 13 → too big → move right
• left = 0 (2), right = 1 (7) → sum = 9 → found

Output:

[1, 2]

---

🖥️ Sample Outputs

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Input: numbers = [-1,0], target = -1
Output: [1,2]

---

🧠 Explanation

• Since the array is sorted, we can efficiently search using two pointers
• If sum is too small → move left pointer
• If sum is too large → move right pointer
• This avoids extra space and reduces complexity

---

⚡ Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) ✅ (constant space)

---

✅ Conclusion

This problem helped me understand:

• Two Pointer Technique
• Optimizing solutions using sorted arrays
• Writing space-efficient code

🚀 This is a very important pattern for coding interviews!

---