DEV Community

Nikko Ferwelo
Nikko Ferwelo

Posted on

🚀 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 []
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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.

Feel free to share your thoughts or additional methods in the comments!

Connect with me:

Happy coding! 🚀

Top comments (0)

Read next

mdarifulhaque profile image

2601. Prime Subtraction Operation

MD ARIFUL HAQUE -

myexamcloud profile image

Sealed class rules in Java

MyExamCloud -

mohiyaddeen7 profile image

Linear Regression : From Theory to Practice

mohiyaddeen7 -

dev-dhanushkumar profile image

Mastering Object-Oriented Programming in Java: A Comprehensive Guide ☕♨

Dhanush Kumar -