2Sum Problem

Problem Overview

The "Two Sum" problem is one of the most popular problems in the LeetCode library, often cited as a classic introduction to algorithm design in interview settings. The problem requires finding two numbers in an array that sum up to a specific target value.

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 target. Each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example:

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

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Understanding the Problem

In this problem, you are given an array of integers, which could include both positive and negative values. Your task is to determine two distinct indices in the array where the numbers at those indices add up to a given target sum. It is crucial to ensure that each index provided is unique and not reused in the pair.

Key DSA Concepts and Theory

Arrays

An array is a basic data structure that can hold a fixed number of values, essentially a list of elements. Arrays provide efficient access to elements with constant-time complexity due to their indexed nature, making them a suitable choice for operations that require direct access to elements.

Hash Map (Hash Table)

A hash map is an advanced data structure that offers a mechanism to store key-value pairs. Utilizing a hash function, the hash map provides average constant-time complexity (O(1)) for lookups, insertions, and deletions, making it highly efficient for problems where search operations are required.

Key Properties:

• Efficient storage of key-value pairs.
• Average constant-time complexity for operations.

Problem Resolution Strategy with Hash Maps

The hash map will be instrumental in storing previously encountered values and their indices. As you iterate through the array, you can determine if the current element's complement (i.e., target - current number) exists in the hash map, indicating the two numbers that add up to the target.

Solution Approach

To effectively solve the problem, a hashing approach offers a more optimal solution compared to brute-force, reducing time complexity significantly.

Step-by-Step Solution

1. Initialize a Hash Map: Create an empty hash map to store numbers and their indices as you iterate through the array.

2. Iterate through the Array:

   • For each element in the array (denoted as current), calculate its complement with respect to the target (complement = target - current).
   • Check if the complement is present in the hash map.

3. Complement Check:

   • If found, return the current index and the stored index of the complement.
   • If not found, store the current element and its index in the hash map.

C++ Implementation

#include <iostream>
#include <vector>
#include <unordered_map>

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> num_map;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (num_map.find(complement) != num_map.end()) {
            return {num_map[complement], i};
        }
        num_map[nums[i]] = i;
    }
    return {};
}

Java Implementation

import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            numMap.put(nums[i], i);
        }
        return new int[] {};
    }
}

Time and Space Complexity Analysis

• Time Complexity: (O(n))

  • The algorithm y passes over the list only once, resulting in linear time complexity.

• Space Complexity: (O(n))

  • In the worst-case scenario, the hash map may need to store n elements, where n is the number of elements in the array.

Common Mistakes to Avoid

1. Using Elements Twice: Ensure that the indices of the two numbers are distinct; you cannot add a single element to itself.

2. Ignoring Edge Cases: Consider including checks for edge cases, such as arrays with less than two elements.

Similar Problems on LeetCode

1. 3Sum (Medium) - Question 15
2. 4Sum (Medium) - Question 18
3. Two Sum II - Input array is sorted (Medium) - Question 167
4. Two Sum IV - Input is a BST (Easy) - Question 653

Additional Resources and References

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• GeeksforGeeks - Hash Table
• Wikipedia - Hash Table
• LeetCode Discuss - Two Sum Discussion

This comprehensive guide provides insights into the problem statement, solution strategies, coding implementations, and advanced concepts behind the "Two Sum" problem on LeetCode, offering a full exploration for both beginners and experienced programmers alike.