Two Sum – Pair sum in sorted array
Two Integer Sum II – Medium Level Problem
You are given a sorted array of integers called numbers, arranged in non-decreasing order. Your task is to find two numbers in the array that add up to a given value called target.
You need to return the positions of these two numbers as a list, [index1, index2], using 1-based indexing (the first element of the array is at position 1). The following conditions must be met:
- The two indices, index1 and index2, must be different.
- The value at index1 should appear before the value at index2 in the array.
There is exactly one correct solution for this problem. Your solution should use constant extra space (O(1)).
Output: [9, 10, 11]
Explanation: The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].
Constraints:
- 2 <= numbers.length <= 1000
- -1000 <= numbers[i] <= 1000
- -1000 <= target <= 1000
Two Integer Sum II Solution
Recommendation for Time and Space Complexity – Your goal is to find a solution that works in O(n) time and uses O(1) extra space, where n is the length of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way?
Hint 2 :
Can you think of an algorithm by taking the advantage of array being sorted?
Hint 3 :
We can use the two-pointer algorithm. If nums[0] + nums[n-1] > target, then we know nums[n – 1] can not possibly be included in any pairs. Why? Because nums[n – 1] is the largest element in the array. Even by adding it with nums[0], which is the smallest element, we still exceed the target. You can think of the case when nums[0] + nums[n – 1] < target.
Hint 4 :
We keep two pointers, one at the start and the other at the end of the array. If the sum of the numbers at the two pointers is greater than the target, decrement the right pointer, else increment the left pointer. Repeat this process until you find a valid pair.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Binary Search Method
- Hash Map Method
- Two Pointers Method
1. Brute Force Method
Iterate through each pair of numbers in the array to check if their sum equals the target. This method has a time complexity of O(n^2).
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector twoSum(vector& numbers, int target) {
for (int i = 0; i < numbers.size(); i++) {
for (int j = i + 1; j < numbers.size(); j++) {
if (numbers[i] + numbers[j] == target) {
return { i + 1, j + 1 };
}
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
return new int[] { i + 1, j + 1 };
}
}
}
return new int[0];
}
}
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]
return []
class Solution {
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
twoSum(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] === target) {
return [i + 1, j + 1];
}
}
}
return [];
}
}
2. Binary Search Method
For each number in the array, use binary search to find the complement (target – current number). This approach works efficiently on a sorted array and has a time complexity of O(nlogn).
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector twoSum(vector& numbers, int target) {
for (int i = 0; i < numbers.size(); i++) {
int l = i + 1, r = numbers.size() - 1;
int tmp = target - numbers[i];
while (l <= r) {
int mid = l + (r - l) / 2;
if (numbers[mid] == tmp) {
return { i + 1, mid + 1 };
} else if (numbers[mid] < tmp) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
int l = i + 1, r = numbers.length - 1;
int tmp = target - numbers[i];
while (l <= r) {
int mid = l + (r - l) / 2;
if (numbers[mid] == tmp) {
return new int[] { i + 1, mid + 1 };
} else if (numbers[mid] < tmp) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return new int[0];
}
}
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
l, r = i + 1, len(numbers) - 1
tmp = target - numbers[i]
while l <= r:
mid = l + (r - l)//2
if numbers[mid] == tmp:
return [i + 1, mid + 1]
elif numbers[mid] < tmp:
l = mid + 1
else:
r = mid - 1
return []
class Solution {
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
twoSum(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
let l = i + 1, r = numbers.length - 1;
let tmp = target - numbers[i];
while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
if (numbers[mid] === tmp) {
return [i + 1, mid + 1];
} else if (numbers[mid] < tmp) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return [];
}
}
3. Hash Map Method
Use a hash map to store numbers and their indices while traversing the array. Check if the complement of the current number exists in the hash map. This method has a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& numbers, int target) {
unordered_map mp;
for (int i = 0; i < numbers.size(); i++) {
int tmp = target - numbers[i];
if (mp.count(tmp)) {
return { mp[tmp], i + 1 };
}
mp[numbers[i]] = i + 1;
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] numbers, int target) {
Map mp = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int tmp = target - numbers[i];
if (mp.containsKey(tmp)) {
return new int[] { mp.get(tmp), i + 1 };
}
mp.put(numbers[i], i + 1);
}
return new int[0];
}
}
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
mp = defaultdict(int)
for i in range(len(numbers)):
tmp = target - numbers[i]
if mp[tmp]:
return [mp[tmp], i + 1]
mp[numbers[i]] = i + 1
return []
class Solution {
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
twoSum(numbers, target) {
const mp = new Map();
for (let i = 0; i < numbers.length; i++) {
const tmp = target - numbers[i];
if (mp.has(tmp)) {
return [mp.get(tmp), i + 1];
}
mp.set(numbers[i], i + 1);
}
return [];
}
}
4. Two Pointers Method
Use two pointers—one starting at the beginning and the other at the end of the sorted array. Adjust the pointers based on the sum of the elements they point to, achieving a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
vector twoSum(vector& numbers, int target) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
int curSum = numbers[l] + numbers[r];
if (curSum > target) {
r--;
} else if (curSum < target) {
l++;
} else {
return { l + 1, r + 1 };
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int curSum = numbers[l] + numbers[r];
if (curSum > target) {
r--;
} else if (curSum < target) {
l++;
} else {
return new int[] { l + 1, r + 1 };
}
}
return new int[0];
}
}
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
curSum = numbers[l] + numbers[r]
if curSum > target:
r -= 1
elif curSum < target:
l += 1
else:
return [l + 1, r + 1]
return []
class Solution {
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
twoSum(numbers, target) {
let l = 0, r = numbers.length - 1;
while (l < r) {
const curSum = numbers[l] + numbers[r];
if (curSum > target) {
r--;
} else if (curSum < target) {
l++;
} else {
return [l + 1, r + 1];
}
}
return [];
}
}
