Programming Pearls

Question – Two Sum Problem

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) 
time complexity?

Answer:

Here’s a detailed explanation of how to implement the solution for the “Two Sum” problem using Java, including the code and a breakdown of the steps involved.

Java Code Implementation:

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Create a HashMap to store numbers and their indices
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // Iterate through the array
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];  // Calculate the complement
            
            // Check if the complement exists in the map
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };  // Return indices if found
            }
            
            // Add the current number and its index to the map
            map.put(nums[i], i);
        }
        
        // Throw an exception if no solution is found (though the problem guarantees a solution)
        throw new IllegalArgumentException("No two sum solution");
    }
}

Step-by-Step Explanation:

1. Understanding the HashMap Usage:

• We use a HashMap to store each number and its index as we traverse through the array.
• The key is the number from the array, and the value is its index.
• For each number in the array, we check if the “complement” (i.e., target - current number) already exists in the HashMap. If it does, that means we’ve found the two numbers that sum up to the target, and we return their indices.

2. findTwoSum Method:

• Input: An integer array nums and an integer target.
• Output: An integer array containing the two indices of the numbers whose sum is equal to the target.

Logic:

• We first initialize a HashMap<Integer, Integer> called map. This will store numbers as keys and their indices as values.
• We iterate through the array using a for loop:
  • For each number at the index i, we calculate the “complement,” which is target - nums[i].
  • We check if this complement is already present in the map. If it is, it means we have already seen a number that, when added to the current number, equals the target.
  • If the complement is found in the map, we return an array of two indices: the index of the complement (retrieved from the map) and the current index i.
  • If the complement is not found, we add the current number along with its index to the map for future reference.
• If no solution is found (though we are guaranteed one solution per the problem constraints), we throw an exception. This is just a safety check.

3. HashMap Operations:

• containsKey(complement): This checks whether the HashMap already contains the complement number (i.e., target - current number). This operation is efficient and has an average time complexity of O(1).
• put(nums[i], i): If the complement is not found, we store the current number and its index in the HashMap. This operation also runs in constant time O(1).

4. main Method:

• The main method contains test cases to verify the function:
  • nums1 = {2, 7, 11, 15} with target = 9: The function finds the numbers 2 and 7, and their indices are 0 and 1, so it prints “Indices: 0, 1”.
  • nums2 = {3, 2, 4} with target = 6: The function finds the numbers 2 and 4, and their indices are 1 and 2, so it prints “Indices: 1, 2”.
  • nums3 = {3, 3} with target = 6: The function finds two numbers 3 (both at index 0 and 1), so it prints “Indices: 0, 1”.

Time and Space Complexity:

Time Complexity: O(n)

• We iterate over the array once, and for each element, we perform a constant-time operation (i.e., checking for the complement and adding the element to the map).
• Thus, the overall time complexity is O(n), where n is the number of elements in the array.

Space Complexity: O(n)

• In the worst case, we store all n numbers in the HashMap, leading to a space complexity of O(n).

Key Points:

1. Efficient Lookup: The HashMap allows for fast lookups of previously seen numbers in constant time, making this approach much more efficient than a brute-force solution.
2. Handling Edge Cases:
   • Duplicate Numbers: The map handles duplicates well. For example, if the input is nums = [3, 3] with target = 6, the solution correctly returns the indices [0, 1].
   • Negative Numbers: The algorithm works for negative numbers as well, since subtraction and map lookups work just the same for negative values.
3. Guaranteed Solution: The problem guarantees exactly one solution, so we do not need to worry about cases where no solution exists.

This is an optimal and efficient solution for the Two Sum problem in terms of both time and space complexity.