DSA | Day 25 of Google Interview Preparation Journey | Challenge 27: Two Sum II — Input Array Is Sorted

Today’s challenge revolved around solving the Two Sum II — Input Array Is Sorted problem (LeetCode #167). This problem is a great exercise in understanding the two-pointer technique and leveraging sorted arrays for efficient solutions.

Problem Statement

You are given a sorted array of integers numbers and an integer target. Return the indices (1-based) of the two numbers such that they add up to target. Assume there is exactly one solution, and you may not use the same element twice.

Approach Highlights

Brute Force Approach

The brute force approach involves checking all pairs of numbers to find the one that sums up to the target.

Algorithm:

1. Use two nested loops to iterate over the array.
2. For each pair (i, j), check if numbers[i] + numbers[j] == target.
3. If found, return the indices (i + 1, j + 1).

Code:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

Time Complexity: O(n²)
Space Complexity: O(1)

Optimized Approach: Two-Pointer Technique

Since the array is sorted, we can use the two-pointer technique to solve the problem efficiently.

Algorithm:

1. Initialize two pointers: left at the start and right at the end of the array.
2. While left < right:

• Calculate the sum of numbers[left] + numbers[right].
• If the sum equals target, return [left + 1, right + 1].
• If the sum is less than target, move the left pointer to the right.
• If the sum is greater than target, move the right pointer to the left.

Code:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, 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

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

Example Walkthrough

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

Steps:

1. Start with left = 0 and right = 3.
2. Calculate numbers[left] + numbers[right] = 2 + 15 = 17 (too high, move right left).
3. New right = 2, calculate 2 + 11 = 13 (still too high, move right left).
4. New right = 1, calculate 2 + 7 = 9 (match found).

Output: [1, 2]

Key Takeaways

• Leveraging the sorted property of arrays allows for efficient solutions using the two-pointer technique.
• Always consider edge cases, such as small arrays or duplicate values.

Real-World Applications

• Finance: Finding pairs of transactions that sum to a specific amount.
• Data Analysis: Identifying complementary data points in sorted datasets.

Resources

• GitHub Repository
• LeetCode Submission