LEETCODE: 1. TWO SUM (Single Pass Hash Table)

Efficiently Solving the Two-Sum Problem in C++ Using Hash Table: A Detailed Walkthrough

In a previous post, we explored a brute force solution to the Two-Sum problem. Today, we're going to optimize this solution using a single pass hash table approach. This new approach greatly improves our algorithm's efficiency, particularly for larger inputs.

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. We may assume that each input would have exactly one solution, and we cannot use the same element twice.

Hash Table Solution:

    
#include <unordered_map>
#include <vector>

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

This code begins by creating an unordered_map to store integer values from the array and their respective indices. We then loop over the array. For each iteration, we calculate the complement - the number we need to find in the map to get two numbers adding up to the target.

If this complement is found in the map, we've found our two numbers, and we return their indices. If not, we insert the current number and its index into the map, then move on to the next iteration. If no two numbers add up to target, we return an empty vector.

Complexity Analysis:

Time Complexity:

The time complexity of this solution is O(n). This is because we are simply performing a single pass through the input array, resulting in linear time complexity.

Space Complexity:

The space complexity is also O(n), as in the worst case scenario we might end up storing every element of the input array in the hash table.

Conclusion:

This hash table solution provides a more efficient way to solve the Two-Sum problem, especially for larger inputs, due to its linear time complexity. Happy coding!