The Question

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Constraints: - 2 <= nums.length <= 10^4 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9 - Only one valid answer exists.

Java

Hash Map

Questions & Insights

Clarifying Questions

Is the input array sorted? (Assumption: No, it is unsorted).

Can we use the same element twice to reach the target? (Assumption: No, each index can be used at most once).

What should be returned if no solution exists? (Assumption: The problem guarantees exactly one solution, but we will return an empty array or throw an exception as a fail-safe).

What are the constraints on the size of the array and the values of the integers? (Assumption: Array size up to

10^5

, values can be large enough to require standard int or long, but int is typical for indices).

Thinking Process

To achieve a sub-quadratic time complexity, we need a way to check if the complement (i.e., target - current_value) has been seen before in

O(1)

average time.

A Hash Map is the ideal data structure here, mapping the value of the element to its index.

We can iterate through the array once (single-pass). For each element, we calculate its required complement. If the complement exists in our map, we have found the pair. Otherwise, we store the current element and its index in the map and continue.

This approach optimizes space-time trade-off, moving from

O(n^2)

(brute force) to

O(n)

time complexity by using

O(n)

extra space.

Implementation Breakdown

Problem Set

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

Constraints:

2 \le nums.length \le 10^4

-10^9 \le nums[i] \le 10^9

-10^9 \le target \le 10^9

Exactly one valid solution exists.

Approach

Algorithm: One-Pass Hash Map

Data Structure: HashMap<Integer, Integer>

Complexity:

Time:

O(n)

- We traverse the list containing

n

elements only once. Each lookup in the table costs only

O(1)

time.

Space:

O(n)

- The extra space required depends on the number of items stored in the hash table, which stores at most

n

elements.

Implementation

Wrap Up

Advanced Topics

Memory Efficiency: In high-performance Java systems (like HFT or big data processing), using HashMap<Integer, Integer> can be heavy due to Integer object boxing. Using primitive collections like FastUtil or Trove's IntIntMap can significantly reduce the memory footprint and GC pressure.

Sorted Input: If the input array were sorted, we could use the Two-Pointer technique, which reduces space complexity to

O(1)

while maintaining

O(n)

time.

Parallelization: For extremely large datasets that don't fit in memory, we could use a distributed hash map (like Redis or Hazelcast) or perform a MapReduce-style join, though this is overkill for standard in-memory arrays.