167. Two Sum II - Input Array Is Sorted
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.
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:
-
Initialization: We start with two pointers,
i
andj
. The pointeri
is initialized to 0, the beginning of the array, andj
tolen(numbers) - 1
, the end of the array. -
Iteration: We enter a loop where
i
moves from the start towards the end, andj
moves from the end towards the start. The loop continues as long asi
is less thanj
, ensuring we only work with pairs whereindex1 < index2
. -
Sum and Compare: In each iteration, we calculate the sum
x
ofnumbers[i]
andnumbers[j]
. We then comparex
with thetarget
. -
Decision Making:
- If
x
equals thetarget
, 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 incrementi
(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 decrementj
(j -= 1
) to consider the next smaller number for a similar reason.
- If
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
atnumbers[0]
(the first element). - Pointer
j
atnumbers[4]
(the last element).
Iteration and Decision Making
We will now iterate and use our decision-making process:
-
In the first iteration,
numbers[i]
is 1 andnumbers[j]
is 6. The sum equals 7, which is less than the target 9.- We increment
i
to move to the next larger number.
- We increment
-
Now
i
points tonumbers[1]
(2) andj
still points tonumbers[4]
(6). The sum is 8, which is again less than the target.- We increment
i
once more.
- We increment
-
i
now points tonumbers[2]
(4) andj
tonumbers[4]
(6). Their sum is 10, which is greater than the target.- We decrement
j
to move to the next smaller number.
- We decrement
-
i
remains pointing tonumbers[2]
(4), andj
moves tonumbers[3]
(also 4). The sum is 8, which is less than the target.- We increment
i
.
- We increment
-
Now both
i
andj
point tonumbers[3]
(the second 4 in the array). The sum ofnumbers[i]
andnumbers[j]
is 8, which is less than the target, but sincei
cannot be equal toj
, we incrementi
. -
After the previous step,
i
exceedsj
, 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 incrementi
again after step 4. Let's correct this: -
After correcting,
i
will point tonumbers[3]
andj
tonumbers[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.
- We return
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
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.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe 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 div Two pointers is a common interview
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we