The Question

Two Sum

Given an array of integers and a target sum, return the indices of the two distinct elements that add up to the target. Assume exactly one valid answer exists.

Java

HashMap

Questions & Insights

Thinking Process

Complement Search: Instead of iterating through all possible pairs, we can rephrase the problem: for every number x at index i, we need to find if there exists a number y (where y = target - x) that we have already encountered.

Efficient Lookup: To avoid nested loops, we use a Hash Map to store elements we've seen so far. This reduces the search time for the "complement" from

O(n)

O(1)

on average.

Single Pass Optimization: We can populate the map and check for the complement in a single iteration. If the complement exists in the map, we immediately return the current index and the stored index.

Implementation Breakdown

Problem Set

Functional Requirements: Find two distinct indices i and j such that nums[i] + nums[j] == target.

Constraints:

Exactly one solution exists.

2 \le \text{nums.length} \le 10^4

-10^9 \le \text{nums[i]} \le 10^9

-10^9 \le \text{target} \le 10^9

Approach

Algorithm: Single-pass Hash Map.

Data Structure: HashMap<Integer, Integer> where Key = value in nums and Value = index of that value.

Complexity:

Time:

O(n)

since we traverse the list containing

n

elements only once.

Space:

O(n)

to store up to

n

elements in the hash map.