Two Sum III - Data structure design

Problem

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

• TwoSum() Initializes the TwoSum object, with an empty array initially.
• void add(int number) Adds number to the data structure.
• boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

Constraints

• -105 <= number <= 105
• -231 <= value <= 231 - 1
• At most 104 calls will be made to add and find.

Solution

The problem Two Sum III - Data structure design can be solved using the design from Two Sum. However, this time, there are a few more considerations and optimizations.

• Space can be saved by using a single map to keep track of both given numbers and their count
• When value below double the minimum given value or over double the maximum given value is searched for, we can immediately return false, reducing the number of operations
• From within the iteration, if the number required to add up to the target value is outside integer range, we can continue on with the search, reducing the number of operations
• If the value searched is double the number in hash table, we need to check if a pair indeed exists (i.e. if the number is added at least twice)

Implementation

class TwoSum
{
  private:
    unordered_map<int, int> nums;
    int min_num;
    int max_num;

  public:
    TwoSum() : min_num(100001), max_num(-100001) {}

    void add(int number)
    {
        nums[number] += 1;
        min_num = min(min_num, number);
        max_num = max(max_num, number);
    }
    bool find(int value)
    {
        if ((long)value < 2 * min_num || 2 * max_num < (long)value)
            return false;

        for (auto num : nums)
        {
            long target = (long)value - num.first;
            if (target < INT_MIN || INT_MAX < target)
                continue;

            if (nums.find(target) != nums.end())
            {
                if (num.first == target && num.second == 1)
                    continue;
                return true;
            }
        }
        return false;
    }
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */