Pair with given Sum
Pair with Given Sum – 2Sum Problem
Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
Return the answer with the smaller index first.
Output: [0,1]
Explanation: nums[0] + nums[1] == 7, so we return [0, 1].
Output: [0,2]
Output: [0,1]
Constraints:
- 2 <= nums.length <= 1000
- -10,000,000 <= nums[i] <= 10,000,000
- -10,000,000 <= target <= 10,000,000
Pair with Given Sum - 2Sum Solution
Recommendation – You should aim for a solution with O(n) time and O(n) space, where n is the size 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? Maybe in terms of mathematical equation?
Hint 2:
Given, We need to find indices i and j such that i != j and nums[i] + nums[j] == target. Can you rearrange the equation and try to fix any index to iterate on?
Hint 3:
Iterate through the array while checking if target – nums[i] exists in the hash map. If not, store the current element with its index in the hash map and continue. This ensures O(1) lookups.
There are mainly 4 approach to solve this problem –
- Brute Force Method
- Sorting Method
- Hash Map(Two Pass) Method
- Hash Map(One Pass) Method
1. Brute Force Method
This method check all possible pairs of numbers in the array to find the ones that add up to the target. Simple but slow for large arrays.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
}
2. Sorting Method
This method sort the array, then use two pointers (one at the start and one at the end) to find the pair that sums to the target.
- Time complexity: O(nlogn)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
vector> A;
for (int i = 0; i < nums.size(); i++) {
A.push_back({nums[i], i});
}
sort(A.begin(), A.end());
int i = 0, j = nums.size() - 1;
while (i < j) {
int cur = A[i].first + A[j].first;
if (cur == target) {
return {min(A[i].second, A[j].second),
max(A[i].second, A[j].second)};
} else if (cur < target) {
i++;
} else {
j--;
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[][] A = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
A[i][0] = nums[i];
A[i][1] = i;
}
Arrays.sort(A, Comparator.comparingInt(a -> a[0]));
int i = 0, j = nums.length - 1;
while (i < j) {
int cur = A[i][0] + A[j][0];
if (cur == target) {
return new int[]{Math.min(A[i][1], A[j][1]),
Math.max(A[i][1], A[j][1])};
} else if (cur < target) {
i++;
} else {
j--;
}
}
return new int[0];
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
A = []
for i, num in enumerate(nums):
A.append([num, i])
A.sort()
i, j = 0, len(nums) - 1
while i < j:
cur = A[i][0] + A[j][0]
if cur == target:
return [min(A[i][1], A[j][1]),
max(A[i][1], A[j][1])]
elif cur < target:
i += 1
else:
j -= 1
return []
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
let A = [];
for (let i = 0; i < nums.length; i++) {
A.push([nums[i], i]);
}
A.sort((a, b) => a[0] - b[0]);
let i = 0, j = nums.length - 1;
while (i < j) {
let cur = A[i][0] + A[j][0];
if (cur === target) {
return [Math.min(A[i][1], A[j][1]),
Math.max(A[i][1], A[j][1])];
} else if (cur < target) {
i++;
} else {
j--;
}
}
return [];
}
}
3. Hash Map(Two Pass) Method
This method first, store all numbers and their indices in a hash map. Then, iterate again to find if the complement (target – current number) exists in the map.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map indices; // val -> index
for (int i = 0; i < nums.size(); i++) {
indices[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if (indices.count(diff) && indices[diff] != i) {
return {i, indices[diff]};
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map indices = new HashMap<>(); // val -> index
for (int i = 0; i < nums.length; i++) {
indices.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (indices.containsKey(diff) && indices.get(diff) != i) {
return new int[]{i, indices.get(diff)};
}
}
return new int[0];
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
indices = {} # val -> index
for i, n in enumerate(nums):
indices[n] = i
for i, n in enumerate(nums):
diff = target - n
if diff in indices and indices[diff] != i:
return [i, indices[diff]]
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
const indices = {}; // val -> index
for (let i = 0; i < nums.length; i++) {
indices[nums[i]] = i;
}
for (let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
if (indices[diff] !== undefined && indices[diff] !== i) {
return [i, indices[diff]];
}
}
return [];
}
}
4. Hash Map(One Pass) Method
This method iterate through the array, check if the complement already exists in the hash map. If not, add the current number with its index to the map.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
int n = nums.size();
unordered_map prevMap;
for (int i = 0; i < n; i++) {
int diff = target - nums[i];
if (prevMap.find(diff) != prevMap.end()) {
return {prevMap[diff], i};
}
prevMap.insert({nums[i], i});
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap prevMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int diff = target - num;
if (prevMap.containsKey(diff)) {
return new int[] { prevMap.get(diff), i };
}
prevMap.put(num, i);
}
return new int[] {};
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {} # val -> index
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
const prevMap = new Map();
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if (prevMap.has(diff)) {
return [prevMap.get(diff), i];
}
prevMap.set(nums[i], i);
}
return [];
}
}
