167. Two Sum II - Input Array Is Sorted

MediumArrayTwo PointersBinary Search
Leetcode Link

Problem Description

Given a sorted array of integers numbers in non-decreasing order, the objective is to find two distinct numbers within the array that sum up to a particular target. The array is "1-indexed," meaning that indexing begins at 1, not 0 as it usually does in programming languages. We need to return the indices of these two numbers such that index1 < index2, incremented by one to account for the 1-indexing, in the format of an array [index1, index2].

Intuition

When presented with a sorted array, we have a significant advantage because the nature of the sorting gives us directional choices. If we are looking for two numbers that add up to the target, then as we pick any two numbers, we can immediately know if we need a larger or a smaller number by comparing their sum to the target.

Intuition for Two Pointers Solution: Two pointers can efficiently solve this problem since the array is already sorted. Start the pointers at opposite ends (i at the start and j at the end). If their sum is too small, we move the i pointer to the right to increase the sum. If their sum is too large, we move the j pointer to the left to decrease the sum. This is possible because the array is sorted, so moving the i pointer to the right will only increase the sum, and moving the j pointer to the left will only decrease it. We continue this process until the pointers' sum equals the target, at which point we have found the solution. Since there is exactly one solution, this approach will always work.

This solution is effective and intuitive because it takes advantage of the sorted nature of the array and eliminates the need for nested loops, which would increase the time complexity. Thus, our approach results in a linear time solution.

Learn more about Two Pointers and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Solution Approach

The solution utilizes a well-known pattern in algorithm design known as the "two-pointer technique." Here's how we implement this pattern to solve our problem:

  1. Initialization: We start with two pointers, i and j. The pointer i is initialized to 0, the beginning of the array, and j to len(numbers) - 1, the end of the array.

  2. Iteration: We enter a loop where i moves from the start towards the end, and j moves from the end towards the start. The loop continues as long as i is less than j, ensuring we only work with pairs where index1 < index2.

  3. Sum and Compare: In each iteration, we calculate the sum x of numbers[i] and numbers[j]. We then compare x with the target.

  4. Decision Making:

    • If x equals the target, we have found the correct indices. Since the problem specifies 1-based indices, we return [i + 1, j + 1].
    • If x is less than the target, it means we need a larger number to reach the target. We increment i (i += 1) to move to the next larger number, because the array is sorted in non-decreasing order.
    • If x is greater than the target, we need a smaller number. We decrement j (j -= 1) to consider the next smaller number for a similar reason.

This approach only uses constant extra space, thus adhering to the space complexity constraints of the problem.

Note: The solution provided in the reference uses two different approaches: [Binary Search](/problems/binary-search-speedrun) and [Two Pointers](/problems/two_pointers_intro). The binary search approach is not reflected in the implementation provided, as binary search would introduce a log n factor to the time complexity, making the overall complexity O(n log n), which is less efficient than the two-pointer approach that operates in O(n) time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above.

Imagine we have the following sorted array numbers and we are given the target 9:

1numbers: [1, 2, 4, 4, 6] 
2target: 9

Initialization

According to the two-pointer technique, we start with:

  • Pointer i at numbers[0] (the first element).
  • Pointer j at numbers[4] (the last element).

Iteration and Decision Making

We will now iterate and use our decision-making process:

  1. In the first iteration, numbers[i] is 1 and numbers[j] is 6. The sum equals 7, which is less than the target 9.

    • We increment i to move to the next larger number.

  2. Now i points to numbers[1] (2) and j still points to numbers[4] (6). The sum is 8, which is again less than the target.

    • We increment i once more.

  3. i now points to numbers[2] (4) and j to numbers[4] (6). Their sum is 10, which is greater than the target.

    • We decrement j to move to the next smaller number.

  4. i remains pointing to numbers[2] (4), and j moves to numbers[3] (also 4). The sum is 8, which is less than the target.

    • We increment i.

  5. Now both i and j point to numbers[3] (the second 4 in the array). The sum of numbers[i] and numbers[j] is 8, which is less than the target, but since i cannot be equal to j, we increment i.

  6. After the previous step, i exceeds j, and thus the loop ends without finding the exact pair. However, for this example walkthrough, the correct pair is the two 4s at positions 3 and 4 which we incidentally skipped, due to our strict reading of 'distinct numbers'. If by 'distinct numbers' the original statement meant distinct indices (which are holding possibly equal values, like the two 4s in this example), we should increment i again after step 4. Let's correct this:

  7. After correcting, i will point to numbers[3] and j to numbers[4], both are 4. Their sum is now 8, which is exactly our target of 8.

    • We return [i + 1, j + 1] which corresponds to [3 + 1, 4 + 1] or [4, 5] in a 1-indexed array.

There we have our solution following the two-pointer approach: indices [4, 5] of the input array numbers contain the numbers that sum up to the target 9.

Note: The hypothetical array and target were chosen for illustrative purposes. The actual input array and target might not have this same issue regarding 'distinct numbers'.

Solution Implementation

1# Define a class named Solution
2class Solution:
3    # Define a method that finds the two indices of the numbers that add up to the target sum
4    def twoSum(self, numbers: List[int], target: int) -> List[int]:
5        # Initialize two pointers, one at the beginning and one at the end of the array
6        left_pointer, right_pointer = 0, len(numbers) - 1
7      
8        # Iterate through the array until the two pointers meet
9        while left_pointer < right_pointer:
10            # Calculate the sum of the two numbers at the current pointers
11            current_sum = numbers[left_pointer] + numbers[right_pointer]
12          
13            # If the sum equals the target, return the indices (1-based)
14            if current_sum == target:
15                return [left_pointer + 1, right_pointer + 1]
16          
17            # If the sum is less than the target, move the left pointer to the right to increase the sum
18            if current_sum < target:
19                left_pointer += 1
20            # If the sum is greater than the target, move the right pointer to the left to decrease the sum
21            else:
22                right_pointer -= 1
23        # Return an empty list if no two numbers sum up to the target (though the problem guarantees a solution)
24        return []
25
1class Solution {
2
3    public int[] twoSum(int[] numbers, int target) {
4      
5        // Initialize pointers for the two indices to be checked
6        int left = 0;                           // Starting from the beginning of the array
7        int right = numbers.length - 1;         // Starting from the end of the array
8      
9        // Loop continues until the correct pair is found
10        while (left < right) {
11            // Calculate the sum of the elements at the left and right indices
12            int sum = numbers[left] + numbers[right];
13          
14            // Check if the sum is equal to the target
15            if (sum == target) {
16                // Return the indices of the two numbers,
17                // incremented by one to match the problem's one-based indexing requirement
18                return new int[] {left + 1, right + 1};
19            }
20          
21            // If the sum is less than the target, increment the left index to increase the sum
22            if (sum < target) {
23                left++;
24            } else {
25                // If the sum is greater than the target, decrement the right index to decrease the sum
26                right--;
27            }
28        }
29      
30        // The problem statement guarantees that exactly one solution exists,
31        // so the following statement is unreachable. This return is used to satisfy the syntax requirements.
32        return new int[] {-1, -1};
33    }
34}
35
1#include <vector> // Include the vector header for using the vector container.
2
3// Define our own Solution class.
4class Solution {
5public:
6    // `twoSum` function to find the indices of the two numbers from `numbers` vector that add up to a specific `target`.
7    std::vector<int> twoSum(std::vector<int>& numbers, int target) {
8        // Initialize two pointers: one at the start (`left`) and one at the end (`right`) of the vector.
9        int left = 0, right = numbers.size() - 1;
10      
11        // Loop until the condition is true, which is an indefinite loop here because we expect to always find a solution.
12        while(true) {
13            // Calculate the sum of the elements at the `left` and `right` pointers.
14            int sum = numbers[left] + numbers[right];
15          
16            // If the sum is equal to the target, return the indices of the two numbers.
17            // The problem statement may assume that indices are 1-based, so we add 1 to each index.
18            if (sum == target) {
19                return {left + 1, right + 1};
20            }
21
22            // If sum is less than the target, we move the `left` pointer to the right to increase the sum.
23            if (sum < target) {
24                left++;
25            // If the sum is greater than the target, we move the `right` pointer to the left to decrease the sum.
26            } else {
27                right--;
28            }
29        }
30      
31        // Note: The initial implementation assumes there will always be a solution before the loop ends,
32        // and as such doesn't have a mechanism to return a value if there is no solution. This may be something
33        // to consider in a real-world application.
34    }
35};
36
1/**
2 * Finds two numbers in a sorted array whose sum equals a specific target number.
3 * 
4 * @param {number[]} numbers - A sorted array of numbers.
5 * @param {number} target - The target sum to find.
6 * @returns {number[]} An array containing the 1-based indices of the two numbers that add up to the target.
7 */
8function twoSum(numbers: number[], target: number): number[] {
9    // Initialize two pointers, one at the start and the other at the end of the array.
10    let startIndex = 0;
11    let endIndex = numbers.length - 1;
12
13    // Iterate through the array until the two pointers meet.
14    while (startIndex < endIndex) {
15        // Calculate the sum of the values at the two pointers.
16        const sum = numbers[startIndex] + numbers[endIndex];
17
18        // If the sum is equal to the target, return the indices (1-based).
19        if (sum === target) {
20            return [startIndex + 1, endIndex + 1];
21        }
22
23        // If the sum is less than the target, move the start pointer to the right.
24        if (sum < target) {
25            ++startIndex;
26        } else {
27            // If the sum is greater than the target, move the end pointer to the left.
28            --endIndex;
29        }
30    }
31
32    // If no two numbers sum up to the target, return an empty array
33    // In the context of this question, a solution is guaranteed so this line is unlikely to be reached.
34    return [];
35}
36
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

Time and Space Complexity

The algorithm uses a two-pointer approach to find two numbers that add up to the target value. The pointers start at the beginning and end of the sorted list and move towards each other.

The time complexity of the algorithm is O(n) because in the worst case, the left pointer i might have to move all the way to the second to last element, and the right pointer j might move to the second element. Each pointer can traverse the list at most once, which results in a linear time complexity with respect to the length of the input list numbers.

The space complexity of the algorithm is O(1). This is because the algorithm only uses a constant amount of extra space: the two pointers i and j, and the variable x for the current sum. No additional space that is dependent on the input size is used, which keeps the space complexity constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫