Two Sum: Find Indices of Two Numbers with a Target Sum

117.9k
0

Given an integer array nums and an integer target, find two different indices whose values add up to target.

The same array position cannot be used twice. Return the indices of the two selected elements in any order.

Return an empty array when no valid pair exists.

Example 1

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

Output: [0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9. Therefore, indices 0 and 1 are returned.

Example 2

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

Output: [1, 2]

Explanation: nums[1] + nums[2] = 2 + 4 = 6. Therefore, indices 1 and 2 are returned.

Example 3

Input: nums = [3, 3], target = 6

Output: [0, 1]

Explanation: nums[0] + nums[1] = 3 + 3 = 6. Even though both values are the same, they are present at different indices.

Brute Force Approach

The direct approach examines every possible pair of different indices.

For each first index, every later index becomes the second candidate. Beginning the second index at first + 1 prevents the same position from being used twice and avoids checking the same pair again in reverse order.

Algorithm

  • Store the array size in n. If n < 2, return an empty array because two different indices are required to form a pair.

  • Traverse first from index 0 to n - 2, allowing each element to act as the first value of a possible pair.

  • For every first, traverse second from first + 1 to n - 1. Starting from the next index prevents using the same position twice and avoids checking the same pair again in reverse order.

  • Calculate the sum of nums[first] and nums[second] to check whether the current pair satisfies the target.

  • If the sum equals target, return [first, second] immediately because a valid pair has been found.

  • Return an empty array after all pairs have been checked if no valid pair exists.

Dry Run

Two Sum Brute Force Dry Run.png

Two Sum Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// A pair requires two different indices.
if (n < 2) {
return {};
}
/*
* Check every pair once by keeping
* the second index ahead of the first.
*/
for (int first = 0; first < n - 1; first++) {
for (int second = first + 1; second < n; second++) {
long long sum =
(long long) nums[first] + nums[second];
// The current pair gives the required sum.
if (sum == target) {
return {first, second};
}
}
}
// No valid pair exists.
return {};
}
};
int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(nums, target);
for (int index : answer) {
cout << index << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. In the worst case, every possible pair of indices is examined.

Space Complexity: O(1), because only loop indices and the current sum require auxiliary storage.

Better Approach

Sorting places smaller values toward the beginning and larger values toward the end. Two pointers can then determine which side should move after comparing the current sum with target.

However, sorting changes element positions. Every value must therefore remain paired with its original index so that the required indices can still be returned after the pair is found. The sorting and two-pointer method requires O(N log N) time.

Algorithm

  • Store the array size in n. If fewer than two elements are available, return an empty array because a valid pair cannot be formed.

  • Create valueIndexPairs, storing each value together with its original index so that sorting does not lose the positions required in the answer.

  • Sort the pairs by value, then initialize left at the smallest value and right at the largest value.

  • While left < right, calculate the sum of the values at both pointers and compare it with target.

  • If the sum is smaller than target, increment left to try a larger value. If the sum is greater, decrement right to try a smaller value. If the sum matches, return the two stored original indices.

  • Return an empty array if the pointers meet without finding a valid pair.

Dry Run

Two Sum Better Appraoch Dry Run.png

Two Sum Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// A pair requires two different indices.
if (n < 2) {
return {};
}
vector<pair<long long, int>> valueIndexPairs;
/*
* Keep each value with its original index
* because sorting changes array positions.
*/
for (int index = 0; index < n; index++) {
valueIndexPairs.push_back({nums[index], index});
}
sort(valueIndexPairs.begin(), valueIndexPairs.end());
int left = 0;
int right = n - 1;
while (left < right) {
long long sum =
valueIndexPairs[left].first +
valueIndexPairs[right].first;
// The stored indices belong to the original array.
if (sum == target) {
return {
valueIndexPairs[left].second,
valueIndexPairs[right].second
};
}
// A smaller sum needs a larger value from the left.
if (sum < target) {
left++;
}
// A larger sum needs a smaller value from the right.
else {
right--;
}
}
// No valid pair exists.
return {};
}
};
int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(nums, target);
for (int index : answer) {
cout << index << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N represents the array size. Sorting the value-index pairs requires O(N log N) time, while the two-pointer traversal requires O(N) time.

Space Complexity: O(N), because one value-index pair is stored for every array element. Sorting may also require language-specific internal memory.

Optimal Approach

For every current value, only one other value can complete the required sum.

This required value is called the complement:

complement = target - currentValue

A hash map stores values that have already been visited together with their indices. Before storing the current value, the algorithm checks whether its complement has appeared earlier.

Searching before insertion ensures that the current position cannot match with itself. Hash-based lookup reduces the average running time to O(N).

Algorithm

  • Store the array size in n. If n < 2, return an empty array because two different positions are required.

  • Create a hash map valueToIndex, where each previously visited value is stored with its index.

  • Traverse the array using current and calculate complement = target - nums[current], which is the only value that can complete the required sum with the current element.

  • Search for complement in valueToIndex before inserting the current value. This ensures that only an earlier index can be paired with current.

  • If the complement exists, return its stored index together with current. Otherwise, store nums[current] and its index so later elements can use it.

  • Return an empty array after the traversal if no valid pair is found.

Dry Run

Two Sum Optimal Appraoch Dry Run.png

Two Sum Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// A pair requires two different indices.
if (n < 2) {
return {};
}
unordered_map<long long, int> valueToIndex;
for (int current = 0; current < n; current++) {
long long complement =
(long long) target - nums[current];
/*
* Check before insertion so the current
* index cannot be paired with itself.
*/
if (valueToIndex.find(complement) !=
valueToIndex.end()) {
return {
valueToIndex[complement],
current
};
}
// Save this value for elements that appear later.
valueToIndex[nums[current]] = current;
}
// No valid pair exists.
return {};
}
};
int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
Solution solution;
vector<int> answer = solution.twoSum(nums, target);
for (int index : answer) {
cout << index << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N represents the array size. Every element requires one average constant-time hash-map lookup and at most one insertion.

Space Complexity: O(N), because the hash map may store almost every array value before a valid pair is found.

FAQS

Q1. Can the same array position be selected twice?

No. The required pair must contain two different indices, even when the needed values are equal.

Q2. Can duplicate values form a valid pair?

Yes. Duplicate values stored at different indices may be used. For nums = [3, 3] and target = 6, indices 0 and 1 form a valid answer.

Q3. Why does the sorting-based approach store original indices?

Sorting changes the positions of the values. Attaching each value to its original index preserves the information required by the answer.

Q4. Why does the smaller-sum condition move the left pointer?

After sorting, moving left rightward replaces the current smaller value with an equal or larger value, which can increase the sum.

Q5. Why is the complement checked before inserting the current value?

Checking first ensures that only previously visited indices are available. This prevents the current element from being paired with itself.

Q6. What should be stored when the same value appears multiple times?

For the standard problem, storing the most recent earlier index is sufficient because any earlier occurrence at a different index can form the required pair.

Two PointerHashingArrays

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.4k
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.6k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. tuf-examples-1 Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cel...

67k
Comments0