Two Sum Problem Java | Fresher Interview
Fast recall
Quick revision
Core answer
x, check if target - x is already in the map; if so you have the pair, otherwise store x. That's O(n) time and O(n) space in a single pass.Whether you can convert the O(n^2) pair search into an O(n) hash-map lookup in one pass
Storing all elements first then searching (two passes) or using the same element twice for the pair
Do it in one pass - check for the complement before inserting the current value
Interview-ready guide
Interview answer
Two Sum asks me to find two indices in an array whose values add up to a target.
The brute force is a double loop checking every pair, which is O of n squared. The insight that makes it fast is the complement. For any value x, the only number that completes the pair is target minus x.
So instead of searching for that partner by scanning, I keep a HashMap that maps each value I've seen to its index, which lets me check for the complement in constant time. The clean version does it in a single pass.
As I walk through the array, for the current value I compute what I need, which is target minus the current value, and I ask the map whether I've already seen that complement. If I have, I immediately return the stored index and the current index. If I haven't, I put the current value and its index into the map and keep going.
That's O of n time and O of n space. A subtle but important detail is the order: I check for the complement before I insert the current value. That guarantees I never pair an element with itself, because the current element isn't in the map yet when I do the lookup.
A common mistake is doing it in two passes, filling the whole map first and then searching, which works but isn't necessary and can accidentally match an element with itself if you're not careful with indices. So the headline is: complement plus a hash map gives you Two Sum in one linear pass.
For example, with [2, 7, 11, 15] and target 9, index 0 stores 2 -> 0. At index 1, the value is 7, so the needed value is 2; the map returns index 0 and the answer is [0, 1].
Two Sum Problem Java | Fresher Interview
Direct Answer
Two Sum: find two indices whose values add up to a target. The brute force is O(n^2). The optimal uses a HashMap of value -> index: for each number x, check if target - x is already in the map; if so you have the pair, otherwise store x. That's O(n) time and O(n) space in a single pass.
Deep Dive & Architecture
What the map means
Before index i is processed, the map contains only values from indexes 0 through i - 1. This is the useful invariant. The lookup therefore asks a precise question: has the partner for the current number already appeared?
Dry run
Take [3, 2, 4] with target 6. At index 0, x = 3 and the needed value is 3; the map is empty, so store 3 -> 0. At index 1, x = 2 needs 4; store 2 -> 1. At index 2, x = 4 needs 2, which is already mapped to index 1, so return [1, 2].
Checking before inserting matters. With [3, 3], the first 3 is stored and the second 3 finds it, so two different indexes are used. If the current item were inserted first, it could match itself.
Each array item causes one lookup and at most one insertion. Hash-map operations are O(1) on average, so the complete scan is O(n) time. The map may keep n entries, which is the O(n) space trade-off.
Common Mistakes & Pitfalls
Storing all elements first then searching (two passes) or using the same element twice for the pair
Check your understanding
Answer these without looking back at the article.
- What is the time complexity of common array operations in Java?
- How do you reverse a string in Java without using built-in reverse methods?
- How do you find duplicates in an array in Java?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.