Definition
- Two Sum – find the indices of two elements in an array that add up to a given target.
- Complement – for a current value
v, the complement istarget - v, the value needed to complete the pair. - HashMap approach – scan once, storing each value and its index; for each element check if its complement is already in the map.
- Time complexity – O(n) average because each map lookup and insert is O(1) average.
- Space complexity – O(n) for the map, trading memory for speed over the O(n squared) brute force.
The National Bank of India wants to find two transactions on Rajesh's account that together make up a suspicious round figure flagged by the fraud rules. Instead of comparing every transaction against every other, a clerk walks the list once holding a notebook of amounts already seen and where they were. For each new transaction the clerk works out how much would be needed to reach the target and checks the notebook. If that complement is already noted, the pair is found. One pass, with a quick notebook lookup each time.
Understanding the Concepts
What is the Two Sum problem?
The Two Sum problem asks for the indices of two elements in an array that add up to a given target. It is one of the most frequently asked coding interview questions and the foundation for multi-sum problems like 3Sum and 4Sum. The constraint is usually that exactly one valid pair exists, though variants ask for all pairs or allow no valid pair.
package com.bank.service;
public class TwoSumProblem {
// Given amounts and a target, return the indices of two amounts
// that add up to the target
public int[] twoSum(int[] amounts, int target) {
// implementation below
return new int[]{};
}
}
How does the HashMap complement approach work?
You create a HashMap whose keys are values you have already seen and whose values are the indices where you saw them. You loop once. For each element at index i, compute the complement as target - amounts[i]. Check whether the map contains the complement. If it does, return the stored index and the current index. If it does not, store the current value and its index in the map and continue.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class FraudPairDetector {
public static int[] findPair(BigDecimal[] amounts, BigDecimal target) {
Map<BigDecimal, Integer> seen = new HashMap<>();
for (int i = 0; i < amounts.length; i++) {
BigDecimal complement = target.subtract(amounts[i]);
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(amounts[i], i);
}
return new int[]{}; // no pair found
}
public static void main(String[] args) {
BigDecimal[] amounts = {
new BigDecimal("5000"), new BigDecimal("15000"),
new BigDecimal("10000"), new BigDecimal("25000")
};
BigDecimal target = new BigDecimal("25000");
int[] pair = findPair(amounts, target);
System.out.println("Pair: [" + pair[0] + ", " + pair[1] + "]");
}
}
Pair: [1, 2]
Why check before inserting?
The order matters: you check for the complement before inserting the current value. This naturally avoids pairing an element with itself. If you inserted first and then checked, an element whose value is exactly half the target could wrongly match itself. Checking before inserting means the current value is not yet in the map when you look for its complement.
// Wrong: insert first, then check
seen.put(amounts[i], i);
if (seen.containsKey(complement)) { ... }
// If amounts[i] == complement, it matches itself
// Correct: check first, then insert
if (seen.containsKey(complement)) { ... }
seen.put(amounts[i], i);
// amounts[i] is not in the map when we check
How is this different from the brute-force approach?
The brute force uses two nested loops, checking every pair, which is O(n squared). The HashMap approach reduces this to O(n) by trading O(n) space for O(1) lookups. For an array of 100,000 transactions, the brute force would do 5 billion comparisons, while the HashMap approach does 100,000.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute force | O(n squared) | O(1) | Two nested loops |
| HashMap | O(n) | O(n) | Single pass |
| Two pointers (sorted) | O(n) or O(n log n) | O(1) | Requires sorted input |
// Brute force: O(n^2)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (amounts[i].add(amounts[j]).compareTo(target) == 0) {
return new int[]{i, j};
}
}
}
How does the two-pointer alternative work on sorted data?
If the array is sorted, opposite-end two pointers find the pair in O(n) time with O(1) extra space. But sorting costs O(n log n) and loses the original indices. When the problem asks for original indices on unsorted data, the HashMap approach is the right choice.
package com.bank.service;
import java.math.BigDecimal;
public class SortedTwoPointer {
public static int[] findPairSorted(BigDecimal[] sorted, BigDecimal target) {
int left = 0, right = sorted.length - 1;
while (left < right) {
BigDecimal sum = sorted[left].add(sorted[right]);
int cmp = sum.compareTo(target);
if (cmp == 0) return new int[]{left, right};
else if (cmp < 0) left++;
else right--;
}
return new int[]{};
}
}
What about duplicate values?
If the same value appears twice and the target is twice that value, the map must hold the first occurrence so the second occurrence finds it. Checking before inserting makes this work correctly: when the second occurrence is processed, its complement (itself) was stored by the first occurrence.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class DuplicateValueCase {
public static void main(String[] args) {
BigDecimal[] amounts = {
new BigDecimal("5000"), new BigDecimal("5000")
};
BigDecimal target = new BigDecimal("10000");
Map<BigDecimal, Integer> seen = new HashMap<>();
for (int i = 0; i < amounts.length; i++) {
BigDecimal complement = target.subtract(amounts[i]);
if (seen.containsKey(complement)) {
System.out.println("Pair: [" + seen.get(complement) + ", " + i + "]");
return;
}
seen.put(amounts[i], i);
}
}
}
Pair: [0, 1]
What about BigDecimal scale normalisation?
BigDecimal equals() considers scale, so new BigDecimal("100") and new BigDecimal("100.00") are different HashMap keys. If the complement is stored as 100 but the lookup computes 100.00, the map will not find it. Normalise scale with stripTrailingZeros() before both storing and looking up.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class NormalisedTwoSum {
public static int[] findPair(BigDecimal[] amounts, BigDecimal target) {
Map<BigDecimal, Integer> seen = new HashMap<>();
for (int i = 0; i < amounts.length; i++) {
BigDecimal normalised = amounts[i].stripTrailingZeros();
BigDecimal complement = target.subtract(normalised).stripTrailingZeros();
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(normalised, i);
}
return new int[]{};
}
}
What are common mistakes?
The most common mistake is inserting before checking, which allows self-pairing. Another is forgetting to handle the no-pair case, returning a sentinel like -1 that callers misuse. A third is not normalising BigDecimal scale in financial code.
// Wrong: returns garbage indices when no pair exists
return new int[]{-1, -1};
// Correct: return empty or use Optional
return new int[]{};
// Or: return Optional.empty();
What should a senior engineer know?
A senior engineer knows that Two Sum is the building block for 3Sum and 4Sum. They return an Optional or empty array when no pair exists, normalise BigDecimal keys, and can discuss the trade-off between HashMap O(n) and two-pointer O(n log n) approaches. They also know that for finding all pairs (not just one), the map must store a list of indices per value rather than a single index.
Visual Overview
amounts = [5000, 15000, 10000, 25000] target = 25000
i=0: complement = 25000 - 5000 = 20000
seen = {} --> 20000 not found
seen = {5000: 0}
i=1: complement = 25000 - 15000 = 10000
seen = {5000: 0} --> 10000 not found
seen = {5000: 0, 15000: 1}
i=2: complement = 25000 - 10000 = 15000
seen = {5000: 0, 15000: 1} --> 15000 FOUND at index 1
RETURN [1, 2]
┌──────────────┐ ┌────────────────────┐
│ current = v │ --> │ complement = T - v │
└──────┬───────┘ └────────┬───────────┘
│ │
│ ┌───────▼────────┐
│ │ map.get(comp) │
│ └───┬────────┬───┘
│ found not found
│ │ │
│ return pair map.put(v, i)
│ continue
└─────────────────────────────┘
Key Takeaway
Two Sum asks for the indices of two elements that add up to a target, and the efficient solution is a single pass with a HashMap from value to index. For each element I compute the complement, which is the target minus the current value, and I check whether that complement is already in the map. If it is, the stored index and the current index are the answer. Otherwise I record the current value and index and move on. It is average O(n) time, which beats the O(n squared) brute-force double loop.
The ordering detail that keeps it correct is that I check for the complement before inserting the current value. That way an element is never paired with itself. If the same value legitimately appears twice and the target is twice that value, the second occurrence finds the first because it was stored on the previous iteration.
I note the alternative: on sorted data, a two-pointer approach uses O(1) extra space, but it needs sorting which costs O(n log n) or loses the original indices. When the problem wants original indices on unsorted data, the HashMap approach is the right default. For money I use BigDecimal keys and normalise scale, because BigDecimal equals considers scale and would otherwise miss a numerically equal complement.
In my banking project at the National Bank of India, I used this in the fraud engine to detect a split-into-two evasion pattern: finding whether any two transactions on Rajesh's account add up exactly to a flagged target and reporting which two. Amounts are BigDecimal with possible scale differences, so I normalise the keys.
Remember one sentence: store each value's index in a HashMap and look up the complement (target minus current) before inserting, giving O(n) pair detection in one pass.
---