Two Sum II - Input Array is Sorted

85.4k
0

Given a sorted integer array numbers and an integer target, find two numbers such that they add up to target.

The array is sorted in non-decreasing order.

Return the indices of the two numbers as a 1-based array, meaning the first element has index 1, not 0.

Each input has exactly one solution, and the same element cannot be used twice.

Example 1

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

Output: [1, 2]

Explanation: numbers[0] + numbers[1] = 2 + 7 = 9. Since output uses 1-based indexing, the answer is [1, 2].

Example 2

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

Output: [1, 3]

Explanation: numbers[0] + numbers[2] = 2 + 4 = 6. So the answer is [1, 3].

Brute Force Approach

The simplest way is to check every possible pair of numbers.

For each element, we try pairing it with every element after it. If the sum of the two elements becomes equal to target, their indices are returned.

This approach works because every possible pair is checked. Since the problem says that exactly one solution exists, the correct pair will definitely be found.

However, this approach does not use the fact that the array is sorted. Because of that, it checks many unnecessary pairs.

Algorithm

  • The size of the array is stored in n. If n is less than 2, [-1, -1] is returned because two numbers are required to form a pair.

  • An outer loop is used to choose the first number of the pair. The index i moves from 0 to n - 1.

  • For every i, an inner loop is used to choose the second number. The index j starts from i + 1 because the same element cannot be used twice.

  • For every pair numbers[i] and numbers[j], their sum is calculated.

  • If the sum is equal to target, [i + 1, j + 1] is returned. The indices are increased by 1 because the problem asks for 1-based indexing.

  • If no pair is found after checking all pairs, [-1, -1] is returned. This case will not occur for valid inputs because the problem guarantees exactly one solution.

Dry Run

Two Sum II - Input Array is Sorted Brute Force Dry Run.png

Two Sum II - Input Array is Sorted Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the required pair by checking every possible combination.
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
// At least two elements are required to form a pair.
if (n < 2) {
return {-1, -1};
}
// Choose each element as the first number of the pair.
for (int i = 0; i < n - 1; i++) {
// Check every valid second element after the current index.
for (int j = i + 1; j < n; j++) {
// Return the pair when its sum matches the target.
if (numbers[i] + numbers[j] == target) {
return {i + 1, j + 1};
}
}
}
return {-1, -1};
}
};
int main() {
vector<int> numbers = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(numbers, target);
cout << answer[0] << " " << answer[1] << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N is the size of the array. In the worst case, every pair of elements may be checked.

Space Complexity: O(1), because no extra data structure is used.

Better Approach

Since the array is sorted, binary search can be used to find the second number.

For every index i, we fix numbers[i] as the first number. Now the second number must be target - numbers[i].

Because the array is sorted, this required value can be searched using binary search on the right side of i.

The search is done only on the right side because the same element cannot be used twice, and we need a different second index.

This approach is better than brute force because it avoids checking every possible pair manually.

Algorithm

  • The size of the array is stored in n. If n is less than 2, [-1, -1] is returned because a valid pair cannot be formed.

  • The array is traversed using index i. For every i, numbers[i] is treated as the first number of the pair.

  • The required second number is calculated as target - numbers[i], and binary search is performed from index i + 1 to n - 1 so the current element cannot be reused.

  • During binary search, if numbers[mid] is equal to required, [i + 1, mid + 1] is returned using 1-based indexing.

  • If numbers[mid] is smaller than required, the left boundary of binary search is moved forward. If numbers[mid] is greater than required, the right boundary is moved backward.

  • If no pair is found after checking all elements, [-1, -1] is returned.

Dry Run

Two Sum II - Input Array is Sorted Better Approach Dry Run.png

Two Sum II - Input Array is Sorted Better Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Searches for the required value in the given sorted range.
int binarySearch(
vector<int>& numbers,
int left,
int right,
int required
) {
// Continue while the search range is valid.
while (left <= right) {
int mid = left + (right - left) / 2;
// Return the index when the required value is found.
if (numbers[mid] == required) {
return mid;
}
// Search the right half when a larger value is required.
if (numbers[mid] < required) {
left = mid + 1;
}
// Search the left half when a smaller value is required.
else {
right = mid - 1;
}
}
return -1;
}
public:
// Finds the pair by searching for each element's complement.
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
// At least two elements are required to form a pair.
if (n < 2) {
return {-1, -1};
}
// Treat each element as the first number of the pair.
for (int i = 0; i < n - 1; i++) {
int required = target - numbers[i];
// Search only after i to avoid reusing the same element.
int index = binarySearch(
numbers,
i + 1,
n - 1,
required
);
// Return the pair when the complement is found.
if (index != -1) {
return {i + 1, index + 1};
}
}
return {-1, -1};
}
};
int main() {
vector<int> numbers = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(numbers, target);
cout << answer[0] << " " << answer[1] << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), because binary search is performed for every element.

Space Complexity: O(1), because no extra data structure is used.

Optimal Approach

The optimal approach uses two pointers.

Since the array is sorted, the smallest number is on the left side and the largest number is on the right side.

We place one pointer at the beginning and another pointer at the end. The sum of these two values is checked.

If the sum is equal to target, the answer is found.

If the sum is smaller than target, we need a larger sum. Since the array is sorted, moving the left pointer forward increases the value on the left side.

If the sum is greater than target, we need a smaller sum. So, the right pointer is moved backward to reduce the value on the right side.

This works because the sorted order tells us exactly which pointer should move.

Algorithm

  • The size of the array is stored in n. If n is less than 2, [-1, -1] is returned because two numbers are required.

  • Two pointers are initialized. left is set to 0, and right is set to n - 1.

  • While left is less than right, the current sum is calculated as numbers[left] + numbers[right].

  • If the current sum is equal to target, [left + 1, right + 1] is returned because the problem uses 1-based indexing.

  • If the current sum is smaller than target, left is moved forward because every value before the new left would produce an equal or smaller sum with the current right.

  • If the current sum is greater than target, right is moved backward because every value after the new right would produce an equal or larger sum with the current left.

  • If the loop ends without finding a pair, [-1, -1] is returned. For valid inputs, this case will not occur because exactly one solution is guaranteed.

Dry Run

Two Sum II - Input Array is Sorted Optimal Approach Dry Run.png

Two Sum II - Input Array is Sorted Optimal Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the pair by using the sorted order of the array.
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
// At least two elements are required to form a pair.
if (n < 2) {
return {-1, -1};
}
int left = 0;
int right = n - 1;
// Continue while two different positions are available.
while (left < right) {
int sum = numbers[left] + numbers[right];
// Return immediately when the required sum is found.
if (sum == target) {
return {left + 1, right + 1};
}
// Move left forward when a larger sum is required.
if (sum < target) {
left++;
}
// Move right backward when a smaller sum is required.
else {
right--;
}
}
return {-1, -1};
}
};
int main() {
vector<int> numbers = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(numbers, target);
cout << answer[0] << " " << answer[1] << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the size of the array. Each pointer moves at most N positions across the traversal.

Space Complexity: O(1), because only two pointer variables are used.

FAQs

Q1. Why does the two-pointer method require sorted input?

Sorted order guarantees predictable sum changes. Moving left forward cannot decrease the left value, while moving right backward cannot increase the right value.

Q2. Why can the same element not be selected twice?

A valid pair requires two different positions. The conditions j > i and left < right enforce distinct indices.

Q3. Can duplicate values form the valid pair?

Yes. Separate positions containing equal values can form a valid pair. For numbers = [1, 1, 3] and target = 2, the answer equals [1, 2].

Q4. Why does pointer movement never skip the valid answer?

A sum smaller than target makes every pair using the current left value and a smaller right value too small. A sum greater than target makes every pair using the current right value and a larger left value too large.

Q5. How would unsorted input change the preferred solution?

A hash map can locate complements in O(N) average time while preserving original indices. Two pointers would require sorting and additional index tracking.

Two PointerArraysBinary Search

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Output: 10 50 Exp...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0