Nikko Ferwelo

Posted on Aug 22

🚀 Solving the Two Sum Problem: Multiple Approaches Using Java/Python

#leetcode #twosum #java #python

The "Two Sum" problem is a popular coding challenge that tests your ability to find pairs in an array that sum up to a specific target. Let’s dive into various methods to solve this problem efficiently.

Problem Statement 🎯

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.

Example

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1] (because nums[0] + nums[1] == 9)

1. Brute Force Approach ⚔️

Python:

def two_sum_bruteforce(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Java:

public int[] twoSumBruteforce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return new int[] {}; // If no solution is found
}

Explanation:

Iterate over each pair of indices and check if their sum equals the target.

2. Hash Map Approach 📚

Python:

def two_sum_hash_map(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    return []

Java:

import java.util.HashMap;

public int[] twoSumHashMap(int[] nums, int target) {
    HashMap<Integer, Integer> numToIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numToIndex.containsKey(complement)) {
            return new int[] { numToIndex.get(complement), i };
        }
        numToIndex.put(nums[i], i);
    }
    return new int[] {}; // If no solution is found
}

Explanation:

Use a hash map to store the index of each number.
For each element, check if its complement (target - current number) exists in the hash map.

3. Two-Pointer Approach 🏃‍♂️

Python:

def two_sum_two_pointer(nums, target):
    nums_with_index = list(enumerate(nums))
    nums_with_index.sort(key=lambda x: x[1])

    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums_with_index[left][1] + nums_with_index[right][1]
        if current_sum == target:
            return [nums_with_index[left][0], nums_with_index[right][0]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Java:

import java.util.Arrays;
import java.util.Comparator;

public int[] twoSumTwoPointer(int[] nums, int target) {
    int[][] numsWithIndex = new int[nums.length][2];
    for (int i = 0; i < nums.length; i++) {
        numsWithIndex[i][0] = i;
        numsWithIndex[i][1] = nums[i];
    }
    Arrays.sort(numsWithIndex, Comparator.comparingInt(a -> a[1]));

    int left = 0, right = nums.length - 1;
    while (left < right) {
        int currentSum = numsWithIndex[left][1] + numsWithIndex[right][1];
        if (currentSum == target) {
            return new int[] { numsWithIndex[left][0], numsWithIndex[right][0] };
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] {}; // If no solution is found
}

Explanation:

First, sort the array while keeping track of the original indices.
Use two pointers to find the pair that sums up to the target.

4. Optimized Space Approach 🔍

Python:

def two_sum_optimized(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

Java:

import java.util.HashMap;

public int[] twoSumOptimized(int[] nums, int target) {
    HashMap<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (seen.containsKey(diff)) {
            return new int[] { seen.get(diff), i };
        }
        seen.put(nums[i], i);
    }
    return new int[] {}; // If no solution is found
}

Explanation:

Iterate through the array while maintaining a hash map of the numbers seen so far.
Check if the complement of the current number exists in the hash map.

Conclusion 🌟

These methods offer various ways to solve the Two Sum problem, each with its advantages and trade-offs. Whether you prefer the straightforward brute force method or the efficient hash map approach, understanding these techniques will enhance your problem-solving skills.

DEV Community

🚀 Solving the Two Sum Problem: Multiple Approaches Using Java/Python

Problem Statement 🎯

Example

1. Brute Force Approach ⚔️

Python:

Java:

2. Hash Map Approach 📚

Python:

Java:

3. Two-Pointer Approach 🏃‍♂️

Python:

Java:

4. Optimized Space Approach 🔍

Python:

Java:

Conclusion 🌟

Connect with me:

Top comments (0)

Read next

LeetCode Challenge: 134. Gas Station - JavaScript Solution 🚀

🚀 Building a User Management API with FastAPI and SQLite

ChatsAPI — The World’s Fastest AI Agent Framework

2182. Construct String With Repeat Limit