Conquering 'Two Sum II': A Guide To Sorted Array Solutions

Introduction: The Two Sum Legacy and the Rise of 'Two Sum II'

Hey everyone! Let's dive into the fascinating world of LeetCode problems, specifically the "Two Sum" series. We all know the original "Two Sum" problem, where we search for two numbers in an array that add up to a specific target. But have you met its sorted cousin, "Two Sum II - Input array is sorted" (LeetCode 167)? This problem, while sharing a similar name, introduces a crucial technique: the Two-Pointer Approach. Understanding "Two Sum II" is vital. It's not just another LeetCode question; it's a foundational stepping stone for mastering array manipulation and algorithmic thinking, especially when dealing with sorted data. This approach is a game-changer when working with sorted arrays, offering a far more efficient solution than the hash map method often used for the original "Two Sum". Why is this problem so important? Because it unlocks a powerful pattern and lays the groundwork for tackling more complex problems, like 3Sum and 4Sum, which build upon this core concept. So, let's roll up our sleeves and explore how to conquer "Two Sum II"!

Unpacking the Problem: 'Two Sum II' Explained

Let's break down the core of "Two Sum II." Unlike the original "Two Sum," the input array here is sorted in ascending order. This key detail allows us to employ the elegant and efficient Two-Pointer Technique. The problem asks us to find two numbers in the sorted array that add up to a given target value. The solution must return the indices of these two numbers (not zero-based), where index1 must be less than index2. The challenge lies in optimizing our search to find these indices swiftly and efficiently. The constraint of a sorted array is the secret ingredient that lets us implement the Two-Pointer method.

Imagine you have a neatly arranged line of numbers, from smallest to largest. The Two-Pointer technique involves placing two pointers at the opposite ends of this line: one at the beginning (smallest number) and one at the end (largest number). You then compare the sum of the numbers at these pointer positions with the target value. If the sum is less than the target, you move the left pointer one step to the right (towards larger numbers). If the sum is greater than the target, you move the right pointer one step to the left (towards smaller numbers). If the sum matches the target, you've found your pair! The beauty of this approach lies in its efficiency, allowing us to find the solution in linear time, O(n). This is a significant improvement over the potentially quadratic time complexity of brute-force methods. Let's delve into how this works in more detail.

The Two-Pointer Magic: How It Works

Alright, let's get into the nitty-gritty of the Two-Pointer Technique for "Two Sum II". The key to this approach lies in the sorted nature of the input array. It's the secret sauce that makes the Two-Pointer Technique so effective. Here's a step-by-step breakdown:

1. Initialization: We start by initializing two pointers: left at the beginning of the array (index 0) and right at the end of the array (index length - 1).
2. Sum Calculation: We calculate the sum of the numbers at the left and right pointers: currentSum = numbers[left] + numbers[right].
3. Comparison: We compare currentSum with the target:
   • If currentSum equals target: We found our pair! Return the indices left + 1 and right + 1 (remember, the problem asks for 1-based indexing).
   • If currentSum is less than target: We need a larger sum. Move the left pointer one step to the right (left++). This is because the array is sorted, so moving to the right guarantees a larger number.
   • If currentSum is greater than target: We need a smaller sum. Move the right pointer one step to the left (right--). Moving left guarantees a smaller number.
4. Iteration: Repeat steps 2 and 3 until the left pointer crosses the right pointer (left < right). If the pointers cross, it means no such pair exists in the array.

The genius of this method lies in its ability to systematically eliminate possibilities with each comparison. By leveraging the sorted order, we can make informed decisions about which direction to move our pointers, quickly honing in on the target sum or confirming that no such pair exists. This systematic elimination is what makes the Two-Pointer Technique so efficient, achieving a time complexity of O(n) – a significant improvement over brute-force methods, which can have a time complexity of O(n^2).

Code Example and Walkthrough

Let's bring this to life with a practical example using Python. This will help solidify your understanding and show you how to implement the Two-Pointer Technique effectively.

def twoSum(numbers, target):
    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
    return None # Or raise an exception if no solution is guaranteed to exist

# Example usage
numbers = [2, 7, 11, 15]
target = 9
result = twoSum(numbers, target)
print(result)  # Output: [1, 2]

numbers = [2,3,4]
target = 6
result = twoSum(numbers, target)
print(result) # Output: [1,3]```

### Explanation of the Code:

1.  **Initialization:** The `left` pointer starts at index 0, and the `right` pointer starts at the last index of the `numbers` array.
2.  **`while` Loop:** The `while` loop continues as long as `left` is less than `right`. This ensures that we explore all possible pairs without revisiting any.
3.  **Sum Calculation:** Inside the loop, `current_sum` is calculated by adding the values at the `left` and `right` pointers.
4.  **Target Check:**
    *   If `current_sum` equals `target`, we found the pair! We return a list containing the indices, incremented by 1 (as per the problem's 1-based indexing requirement).
    *   If `current_sum` is less than `target`, we increment `left` to increase the sum.
    *   If `current_sum` is greater than `target`, we decrement `right` to decrease the sum.
5.  **No Solution:** If the loop completes without finding a solution, it means no pair adds up to the target, so the function returns `None` (or you could raise an exception, depending on the problem's requirements).

### How the Example Works:

For `numbers = [2, 7, 11, 15]` and `target = 9`:

*   `left = 0`, `right = 3`. `current_sum` (2 + 15) = 17. Since 17 > 9, `right` becomes 2.
*   `left = 0`, `right = 2`. `current_sum` (2 + 11) = 13. Since 13 > 9, `right` becomes 1.
*   `left = 0`, `right = 1`. `current_sum` (2 + 7) = 9. Since 9 == 9, we return `[1, 2]`.

This simple example effectively demonstrates the efficiency of the Two-Pointer Technique, which finds the solution in a linear fashion, requiring only a few iterations to find the correct indices. This contrasts sharply with a brute-force approach, which could involve nested loops and a much higher number of operations.

***

## Time and Space Complexity: The Beauty of Efficiency

Let's analyze the **Time and Space Complexity** of the Two-Pointer Technique as applied to "Two Sum II." Understanding the efficiency of an algorithm is critical for assessing its suitability for various use cases and data sizes.

*   **Time Complexity:** The Two-Pointer Technique achieves a time complexity of *O(n)*. This means the algorithm's runtime grows linearly with the size of the input array (n). The algorithm only iterates through the array once, with each pointer moving towards the center. In the worst-case scenario, the pointers might traverse the entire array, but that's still directly proportional to the size of the array, resulting in the O(n) time complexity.
*   **Space Complexity:** The space complexity is *O(1)*, which means it uses constant extra space. The algorithm only uses a few extra variables (`left`, `right`, `currentSum`) regardless of the input array's size. The memory usage does not scale with the size of the input, making it a very space-efficient solution.

The efficiency of O(n) time and O(1) space makes the Two-Pointer Technique a highly desirable approach for "Two Sum II." This contrasts with a hash map-based approach (often used for the original "Two Sum"), which has a time complexity of O(n) but a space complexity of O(n) because it requires storing the array elements in a hash map. The Two-Pointer technique's superior space efficiency is a significant advantage, particularly when memory is a concern or when dealing with very large datasets. This makes the Two-Pointer approach a top choice for optimizing performance when tackling the "Two Sum II" problem.

***

## 'Two Sum II' vs. The Original 'Two Sum': A Comparative Look

Let's pit "Two Sum II" against the original "Two Sum" problem. While they share the same core goal – finding two numbers that sum to a target – their approaches and performance differ significantly. This comparison highlights the advantages of the Two-Pointer Technique and the importance of choosing the right algorithm for the job.

*   **Input Data:** The key difference lies in the input. "Two Sum II" requires a *sorted* array, whereas the original "Two Sum" deals with an *unsorted* array.
*   **Technique:**
    *   **"Two Sum II":** Employs the Two-Pointer Technique, which capitalizes on the sorted input to achieve O(n) time and O(1) space complexity.
    *   **Original "Two Sum":** Typically uses a hash map-based approach. This offers O(n) time complexity but with O(n) space complexity because it requires storing array elements in a hash map.
*   **Time Complexity:** Both approaches achieve O(n) time complexity in the best and average cases. However, the Two-Pointer technique in "Two Sum II" avoids the overhead associated with hash map operations.
*   **Space Complexity:**
    *   **"Two Sum II":** O(1) - constant space, as it uses only a few variables.
    *   **Original "Two Sum":** O(n) - uses a hash map to store array elements.
*   **Efficiency:** The Two-Pointer Technique is generally more space-efficient, making it ideal when memory usage is a constraint. The hash map approach is often faster in practice due to the constant time lookups provided by hash maps.

In essence, the choice between these two approaches depends on the specific scenario. If the input array is sorted, the Two-Pointer Technique is the clear winner due to its superior space efficiency. If the array is unsorted, the hash map approach is the standard solution. This comparative analysis demonstrates the versatility of algorithmic techniques and the importance of adapting your approach to fit the problem's specific characteristics.

***

## Conclusion: Mastering 'Two Sum II' and Beyond

Congratulations! You've successfully navigated the intricacies of "Two Sum II" and the Two-Pointer Technique. We've covered the problem's core, how the Two-Pointer Technique works, the code implementation, and its efficiency. The sorted input is the key, letting us create an efficient, linear-time solution. The Two-Pointer approach is more than just a technique; it's a building block for more complex problems like 3Sum and 4Sum. By mastering "Two Sum II," you've expanded your algorithmic toolkit and improved your ability to approach array-based challenges. Keep practicing, and you'll continue to grow your problem-solving skills!

**External Link:**

For further practice and exploration, check out the [LeetCode](https://leetcode.com/) platform, where you can find "Two Sum II" and numerous other coding challenges to sharpen your skills.