Data Structures & Algorithms

Java Two Sum Problem (Optimized One-Pass HashMap)

Find two indices in an array of integers that add up to a specific target number using a single-pass HashMap in O(n) time.

Java Source Code

Editable code sample with line numbers

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;

public class Main {
    public static int[] twoSum(int[] nums, int target) {
        // Map to store number value -> its array index
        Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }

map.put(nums[i], i);
        }

return new int[] {}; // No match found
    }

public static void main(String[] args) {
        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;

int[] result = twoSum(numbers, target);

System.out.println("Input Array: " + Arrays.toString(numbers));
        System.out.println("Target: " + target);
        System.out.println("Matching Indices: " + Arrays.toString(result));
        if (result.length == 2) {
            System.out.println("Values: " + numbers[result[0]] + " + " + numbers[result[1]] + " = " + target);
        }
    }
}

Expected Output

When this program is compiled and executed, the terminal outputs:

Input Array: [2, 7, 11, 15]
Target: 9
Matching Indices: [0, 1]
Values: 2 + 7 = 9

How the Code Works

Instead of using a brute-force O(n²) nested loop, we maintain a HashMap while iterating through the array. For each element nums[i], we calculate the needed complement = target - nums[i]. If complement exists in our map, we immediately return its stored index alongside i. Otherwise, we record the current number and index into the map.

Time Complexity

O(N) single-pass lookup

Space Complexity

O(N) for HashMap entries

Key Takeaways & Best Practices

Hash tables provide O(1) amortized lookup, reducing polynomial search time to linear.
One-pass approach checks complement before inserting, preventing using the same element twice.

Master Java with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Java Examples

Trees & BFS

O(N)

Java Binary Tree Level Order Traversal (BFS)

Traverse a binary tree level by level using Breadth-First Search (BFS) with an ArrayDeque queue in Java.

Java Invert / Mirror Binary Tree

Invert a binary tree by recursively swapping left and right child pointers.

Java Program to Reverse a String (StringBuilder & Two Pointers)

Reverse strings in Java efficiently using StringBuilder and in-place char array two-pointer swapping.

Runnable Code

View Code

How the Code Works

Time Complexity

O(N) single-pass lookup

Space Complexity

O(N) for HashMap entries

Key Takeaways & Best Practices

Hash tables provide O(1) amortized lookup, reducing polynomial search time to linear.
One-pass approach checks complement before inserting, preventing using the same element twice.

Java Two Sum Problem (Optimized One-Pass HashMap)

Java Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Java with ZenCompiler

Related Java Examples

Java Binary Tree Level Order Traversal (BFS)

Java Invert / Mirror Binary Tree

Java Program to Reverse a String (StringBuilder & Two Pointers)

Platform & Tools

Account

Company & Help

Legal & Policies

Java Two Sum Problem (Optimized One-Pass HashMap)

Java Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Java with ZenCompiler

Related Java Examples

Java Binary Tree Level Order Traversal (BFS)

Java Invert / Mirror Binary Tree

Java Program to Reverse a String (StringBuilder & Two Pointers)