Mohith

Posted on Mar 19

two sum- java

#algorithms #beginners #java #tutorial

Optimizing the Two Sum Problem in Java Using Hashing

Introduction

The Two Sum problem is one of the most fundamental problems in data structures and algorithms. It is simple to understand, yet it provides a strong foundation for learning how to optimize solutions.

When I first approached this problem, I used a brute force method. While it worked, it was not efficient. This led me to rethink the problem and arrive at a better solution using hashing.

Problem Statement

Given an array of integers and a target value, return the indices of the two numbers such that they add up to the target.

Brute Force Approach

The most straightforward solution is to check every possible pair.

“Check each pair and verify if their sum equals the target.”

Although this works correctly, it requires nested loops, resulting in a time complexity of O(n²). This approach becomes inefficient as the input size increases.

Rethinking the Problem

Instead of checking all pairs, a better way is to reframe the question.

Rather than asking:

“Which two numbers add up to the target?”

We can ask:

“For each number, what value is required to reach the target?”

This shift in perspective allows us to reduce unnecessary computations.

Optimized Approach Using Hashing

To implement this idea efficiently, we use a HashMap.

Steps:

Create a HashMap to store elements and their indices.
Traverse the array once.
For each element:

Compute the complement: complement = target - current element
Check if the complement exists in the HashMap.
If it exists, return the indices.
Otherwise, store the current element in the map.

Example Walkthrough

Input:

nums = [2, 7, 11, 15];
target = 9;

Step 1:

Current = 2 → complement = 7 → not found
Store → {2:0}

Step 2:

Current = 7 → complement = 2 → found

Output:

[0, 1]

Java Implementation

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<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[] {};
    }
}

Line-by-Line Explanation

Import Statement

import java.util.HashMap;

Imports the HashMap class used for storing key-value pairs.

Class Definition

class Solution {

Defines the class containing the solution.

Method Declaration

public int[] twoSum(int[] nums, int target)

Returns an array of indices
Accepts the input array and target value

Create HashMap

HashMap<Integer, Integer> map = new HashMap<>();

Stores elements in the format:
number → index

Loop Through Array

for (int i = 0; i < nums.length; i++)

Iterates through each element of the array.

Calculate Complement

int complement = target - nums[i];

Determines the value needed to reach the target.

Check for Complement

if (map.containsKey(complement))

Checks if the required value already exists in the map.

Return Result

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

Returns the indices of the two numbers.

Store Current Element

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

Stores the current element for future reference.

Default Return

return new int[] {};

Returns an empty array if no solution is found.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

This is significantly more efficient than the brute force approach.

Key Insight

The main idea is to avoid repeated work. By storing previously seen elements, we can directly check whether the required complement exists instead of searching repeatedly.

Conclusion

The Two Sum problem highlights how a small change in perspective can lead to a more efficient solution. Using hashing reduces time complexity and simplifies the implementation.

DEV Community