LeetCode 1: Two Sum Problem – Explained with Java Code

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target. Each input has exactly one solution, and you may not use the same element twice.

Example:

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1] (since 2 + 7 = 9)

Solution Approaches

1. Brute-Force Approach

Description:

This straightforward method involves checking every possible pair of numbers to see if they sum up to the target.

Steps:

1. Iterate through each element i in the array.
2. For each element i, iterate through the subsequent elements j.
3. Check if nums[i] + nums[j] == target.
4. If true, return the indices [i, j].

Java Implementation:

public int[] twoSum(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 };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Complexity Analysis:

• Time Complexity: O(n²) – Due to the nested loops iterating over the array.
• Space Complexity: O(1) – No additional space is used.

Pros:

• Simple and easy to understand.

Cons:

• Inefficient for large datasets due to its quadratic time complexity.

2. HashMap Approach

Description:

Utilize a HashMap to store the difference between the target and each element, allowing for constant-time lookups to find the complement.

Steps:

1. Create a HashMap to store the value and its index.
2. Iterate through the array:
   • Calculate the complement: complement = target - nums[i].
   • If the complement exists in the HashMap, return the indices [map.get(complement), i].
   • Otherwise, add nums[i] and its index to the HashMap.

Java Implementation:

import java.util.HashMap;

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);
    }
    throw new IllegalArgumentException("No two sum solution");
}

Complexity Analysis:

• Time Complexity: O(n) – Single pass through the array with constant-time lookups.
• Space Complexity: O(n) – HashMap stores up to n elements.

Pros:

• More efficient than the brute-force approach.
• Suitable for large datasets.

Cons:

• Requires additional space for the HashMap.

3. Two-Pointer Approach (For Sorted Arrays)

Description:

If the array is sorted, use two pointers starting from the beginning and end of the array to find the target sum.

Steps:

1. Initialize two pointers: left at the start (index 0) and right at the end (index n-1).
2. Calculate the sum of the elements at these pointers.
3. If the sum equals the target, return the indices [left, right].
4. If the sum is less than the target, move the left pointer to the right.
5. If the sum is greater than the target, move the right pointer to the left.
6. Repeat until the solution is found.

Java Implementation:

public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[] { left, right };
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Complexity Analysis:

• Time Complexity: O(n) – Each element is processed at most once.
• Space Complexity: O(1) – No additional space is used.

Pros:

• Efficient with linear time complexity.
• Minimal space usage.

Cons:

• Only applicable if the array is already sorted.
• If the array isn’t sorted, sorting it first would add O(n log n) time complexity.

Conclusion

Understanding multiple approaches to the Two Sum problem enhances problem-solving skills and prepares you for various scenarios in coding interviews. The brute-force method is simple but inefficient for large datasets. The HashMap approach offers a balance between time and space efficiency and is widely applicable. The two-pointer technique is optimal for sorted arrays but requires the array to be sorted beforehand.

By mastering these methods, you can tackle similar problems with confidence and choose the most efficient solution based on the given constraints.