Log inSign up
easyLeetCodeNot Started

Two Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input has exactly one valid solution, and you may not use the same element twice. You can return the answer in any order.

Example 1 · Standard Pair Found:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 2 + 7 == 9, we return [0, 1].

Example 2 · Later Pair & Skipping Self-Match:

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] == 2 + 4 == 6. Note that nums[0] + nums[0] == 3 + 3 == 6 is NOT valid because you cannot use the element at index 0 twice.

Example 3 · Duplicate Values at Different Positions:

Input: nums = [3, 3], target = 6
Output: [0, 1]
Explanation: The two values are identical (3 and 3), but because they are at distinct indices (0 and 1), they form a valid pair.

Example 4 · Negative Numbers and Zero Target:

Input: nums = [-3, 4, 3, 90], target = 0
Output: [0, 2]
Explanation: nums[0] + nums[2] == (-3) + 3 == 0. Negative numbers work identically with complement calculation: 0 - (-3) = 3.

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.
  • Cannot use the same element at the same index twice.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array indexing and linear iteration
  • Hash Map / Object key-value lookups
  • Time and space complexity fundamentals (Big-O)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Transform pair-sum requirements into complement lookup equations: complement = target - nums[i].
  • Analyze the time-space trade-off between quadratic nested loops (O(N²)) and hash table storage (O(N)).
  • Master the single-pass hash map technique that inserts elements only after checking to prevent self-pairing.
  • Implement clean, standalone, production-ready solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Question asks for a pair of numbers satisfying a target arithmetic condition (a + b = target).
  • The input array is unsorted and requires an O(N) linear time solution.
  • Original indices must be preserved in the final output.

Algorithmic Decision Tree:

  • If unsorted and original indices are required -> Use a One-Pass Hash Map (O(N) time, O(N) space).
  • If sorted and only values or boolean existence needed -> Use Two Pointers from opposite ends (O(N) time, O(1) space).
  • If extra memory is strictly prohibited (O(1) space) -> Sort index-value pairs (O(N log N) time) or Brute Force (O(N²) time).

Connected Patterns:

Complement LookupTwo PointersFrequency MapPrefix Sum + Hash Map (Subarray Sum Equals K)3Sum / 4Sum

1. Brute Force — Check All Pairs

Intuition

Iterate through every pair of elements using nested loops and verify if their sum equals the target.

Algorithm

  1. Loop with index i from 0 to N - 1.
  2. Nested loop with index j from i + 1 to N - 1.
  3. Check if nums[i] + nums[j] == target.
  4. If equal, return [i, j].
  5. If no pair matches after checking all pairs, return an empty array.

Brute Force All Pairs Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, 8, 4, 2, 9]
Current operationSTEP 1 OF 6
Pair (0, 1): Fix i=0 (value 3)
Visual state
Values and pointers at this exact step
table
S
3
8
4
2
9
0
↑ i=0
1
↑ j=1
2
3
4
Fixed i0 (val 3)
Inner j1 (val 8)
Sum11
Target10
StatusNo Match
Variables at this step
Fixed i
0 (val 3)
Inner j
1 (val 8)
Sum
11
Target
10
Status
No Match
Check / comparison
nums[0] + nums[1] = 3 + 8 = 11 != 10
Decision / next transition
Sum 11 != target 10. Advance j to index 2.
Why this step matters

Pair (0, 1): Fix i=0 (value 3). Test j=1 (value 8). Sum is 11, which does not equal 10. Increment j.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: Check all pairs
6vector<int> twoSum(const vector<int>& nums, int target) {
7 int n = nums.size();
8 for (int i = 0; i < n; i++) {
9 for (int j = i + 1; j < n; j++) {
10 if (nums[i] + nums[j] == target) {
11 return {i, j};
12 }
13 }
14 }
15 return {};
16}
17
18int main() {
19 vector<int> nums = {3, 2, 4};
20 int target = 6;
21 vector<int> result = twoSum(nums, target);
22
23 cout << "Output: [" << result[0] << ", " << result[1] << "]" << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N²) — The outer loop runs N times and the inner loop runs up to N times, totaling N × (N - 1) / 2 comparisons = O(N²) quadratic time.
  • Space complexity: O(1) — Only a few integer loop variables (i, j) are used. No extra data structures are allocated.

Why Brute Force Doesn't Scale:

For an array of size N, brute force performs N × (N - 1) / 2 comparisons.

For N = 10,000: 10,000² / 2 ≈ 50,000,000 operations.

For N = 100,000: 100,000² / 2 ≈ 5,000,000,000 operations (5 billion checks).

Even though brute force is logically correct, its quadratic growth causes Time Limit Exceeded (TLE) on large inputs.

At N = 104: Brute Force takes ~50,000,000 ops (~150ms). Hash Map takes ~10,000 ops (< 2ms).

2. Better — Sort with Indices & Two Pointers

Intuition

Store value-index pairs, sort them by value, and converge using two pointers from opposite ends.

Algorithm

  1. Store each number alongside its original index as a pair (val, idx).
  2. Sort the pairs in ascending order by value.
  3. Set pointer left = 0 and pointer right = N - 1.
  4. Calculate currentSum = pairs[left].val + pairs[right].val.
  5. If currentSum == target, return [pairs[left].idx, pairs[right].idx].
  6. If currentSum < target, increment left.
  7. If currentSum > target, decrement right.

Two Pointers on Sorted Indexed Pairs

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 8, 9, 14]
Current operationSTEP 1 OF 6
Step 1 — Initial Boundary Evaluation: Pointers start at opposite ends
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
8
9
14
0
↑ L=0 (Val 1)
1
2
3
4
5
↑ R=5 (Val 14)
Variables at this step
L Pointer
Idx 0 (val 1)
R Pointer
Idx 5 (val 14)
Sum
15
Target
10
Action
R--
Check / comparison
sorted[0].val + sorted[5].val = 1 + 14 = 15 > 10
Decision / next transition
Sum 15 > target 10. Decrement R to index 4 to reduce total sum.
Why this step matters

Step 1 — Initial Boundary Evaluation: Pointers start at opposite ends. Sum is 15. Because 15 > 10, no value paired with 14 can reach 10. Decrement R.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Pair: {value, originalIndex}
7vector<int> twoSum(vector<int>& nums, int target) {
8 int n = nums.size();
9 vector<pair<int, int>> pairs(n);
10 for (int i = 0; i < n; i++) {
11 pairs[i] = {nums[i], i};
12 }
13
14 // Sort by value ascending
15 sort(pairs.begin(), pairs.end());
16
17 int left = 0, right = n - 1;
18 while (left < right) {
19 int currentSum = pairs[left].first + pairs[right].first;
20 if (currentSum == target) {
21 return {pairs[left].second, pairs[right].second};
22 } else if (currentSum < target) {
23 left++;
24 } else {
25 right--;
26 }
27 }
28 return {};
29}
30
31int main() {
32 vector<int> nums = {3, 2, 4};
33 int target = 6;
34 vector<int> result = twoSum(nums, target);
35
36 cout << "Output: [" << result[0] << ", " << result[1] << "]" << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting N value-index pairs takes O(N log N) time. The two-pointer search takes O(N) linear time. The overall time complexity is dominated by sorting: O(N log N).
  • Space complexity: O(N) — An auxiliary array of size N is allocated to store value-index pairs so original indices are retained.

3. Optimal — One-Pass Hash Map (Complement Lookup)

Intuition

Traverse the array once while storing seen numbers in a Hash Map. For each number, check if its complement (target - x) was already seen.

Algorithm

  1. Create an empty Hash Map seen to store value -> index.
  2. Iterate through the array with index i from 0 to N - 1.
  3. Calculate complement = target - nums[i].
  4. Check if complement exists in seen.
  5. If found, return [seen[complement], i].
  6. If not found, store seen[nums[i]] = i and continue.

One-Pass Hash Map Complement Lookup Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
InputINPUT nums = [3, 8, 5, 2, 7]
Current operationSTEP 1 OF 5
Step 1 — Element 3: We inspect index 0 (value 3)
Visual state
Values and pointers at this exact step
hashmap
Input array
S
3
8
5
2
7
0
↑ i = 0
1
2
3
4
Hash map state
1 stored entry
key
3
maps to index
0
7 not found in map. Store seen[3] = 0. Advance to i = 1.
Variables at this step
Index i
0
Current Element
3
Target
10
Needed Complement
7
Map Lookup
MISS (Not Found)
Hash Map Contents
{ 3: 0 }
Check / comparison
Current nums[0] = 3. Complement = target - 3 = 10 - 3 = 7. Is 7 in map? Map = {}.
Decision / next transition
7 not found in map. Store seen[3] = 0. Advance to i = 1.
Why this step matters

Step 1 — Element 3: We inspect index 0 (value 3). The required partner to reach target 10 is complement = 10 - 3 = 7. The hash map is currently empty, so 7 has not been seen yet. We record { 3: 0 } and move to index 1.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6// Optimal: One-Pass Hash Map
7vector<int> twoSum(const vector<int>& nums, int target) {
8 unordered_map<int, int> seen; // value -> index
9
10 for (int i = 0; i < (int)nums.size(); i++) {
11 int complement = target - nums[i];
12
13 // If complement was already seen, return indices
14 if (seen.find(complement) != seen.end()) {
15 return {seen[complement], i};
16 }
17
18 // Store current number with its index
19 seen[nums[i]] = i;
20 }
21 return {};
22}
23
24int main() {
25 vector<int> nums = {2, 7, 11, 15};
26 int target = 9;
27 vector<int> result = twoSum(nums, target);
28
29 cout << "Output: [" << result[0] << ", " << result[1] << "]" << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) avg — The array is traversed once (N iterations). Hash Map lookup and insertion take O(1) time on average. Total time = N × O(1) = O(N) average time.
  • Space complexity: O(N) — In the worst case, the hash map stores up to N - 1 entries, requiring O(N) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N²)O(1)Check every possible pair (i, j) with nested loops.Repeatedly scanning remaining elements takes ~N²/2 operations.
2.Better — Sort with IndicesO(N log N)O(N)Pair values with indices, sort, and search with Two Pointers.Sorting is slower than a direct single-pass hash lookup.
3.Optimal — One-Pass Hash MapOptimalO(N) avgO(N)Store seen numbers in a Hash Map and check for complement on each step.Traded space for speed.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Reusing the same index twice when target is 2 × nums[i] (e.g. returning [0, 0] when nums[0] = 3 and target = 6).

Pitfall 2:

Returning array values (e.g. [2, 7]) instead of their 0-based indices [0, 1].

Pitfall 3:

Sorting the original array in-place without storing original indices first.

Pitfall 4:

Assuming hash maps guarantee mathematical O(1) in every scenario without understanding hash collisions.

Crucial Edge Cases to Validate:

  • Array with exactly two elements: nums = [3, 3], target = 6 — minimum valid input size.
  • Negative numbers and zeroes: nums = [-3, 4, 3, 90], target = 0 — complement formula handles negative arithmetic cleanly.
  • Target is negative: nums = [-5, -2, -1, -8], target = -7 -> nums[0] + nums[1] == (-5) + (-2) == -7.
  • Target is twice the value of an element: nums = [3, 2, 4], target = 6 — ensure index 0 is not matched with itself.
  • Large values near 109: values fit safely within standard 32-bit signed integers.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the O(N²) brute-force solution first (15-20 seconds) before optimizing to demonstrate structured problem-solving.
  2. Explicitly write the complement equation complement = target - nums[i] before writing the hash map code.
  3. Explain why the one-pass approach guarantees you never use the same index twice (the current element is only stored after checking).
  4. Clearly articulate the Time-Space trade-off: trading O(N) auxiliary space for an acceleration from O(N²) down to O(N) linear time.
  5. Clarify whether the returned indices can be in any order and whether 0-based indexing is expected.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Two Sum?

2.Why is the brute force approach suboptimal for large inputs in Two Sum?

3.Which data structure or technique enables the optimal solution for Two Sum?

Back to DSA Sheet