Two Sum III - Data structure design

class PairSum {
private:
    unordered_map<long long, int> counts;
    
public:
    PairSum() {}
    
    void addNumber(int num) {
        if (counts.find(num) != counts.end())
            counts[num]++;
        else
            counts[num] = 1;
    }
    
    bool check(int target) {
        for (const auto &item : counts) {
            long long needed = static_cast<long long>(target) - item.first;
            if (needed != item.first) {
                if (counts.find(needed) != counts.end())
                    return true;
            } else {
                if (item.second > 1) return true;
            }
        }
        return false;
    }
};

The problem involves designing a data structure that supports adding numbers and can verify if a pair with a given sum exists within these added numbers, using C++.

• Data Structure Used: unordered_map<long long, int> counts. This hashmap stores numbers as keys and their frequencies as values.

Methods in the Data Structure:

1. addNumber(int num):

   • Updates the hashmap by incrementing the count of the number added. If the number is not in the map, it initializes its count to 1.

2. check(int target):

   • Iterates through each item in the hashmap to determine if a pair summing up to the target exists.
   • For each number, it calculates the required complement by subtracting the current number from the target.
   • Checks two conditions:
     • If the complement is different from the number, checks if the complement exists in the map.
     • If the complement is the same as the number, checks if this number appears at least twice.
   • Returns true if any of the above conditions are satisfied, otherwise false after all checks.

This structure efficiently adds numbers and checks for the existence of two sum pairs by optimizing search operations through the use of a hashmap, leveraging the average O(1) time complexity for insertions and lookups.

import java.util.HashMap;
    
class PairSum {
    private HashMap<Integer, Integer> countMap;
    
    public PairSum() {
        this.countMap = new HashMap<>();
    }
    
    public void addElement(int num) {
        if (this.countMap.containsKey(num)) this.countMap.put(
                num,
                this.countMap.get(num) + 1
            );
        else this.countMap.put(num, 1);
    }
    
    public boolean checkPair(int target) {
        for (HashMap.Entry<Integer, Integer> element : this.countMap.entrySet()) {
            int needed = target - element.getKey();
            if (needed != element.getKey()) {
                if (this.countMap.containsKey(needed)) return true;
            } else {
                if (element.getValue() > 1) return true;
            }
        }
        return false;
    }
}

The provided Java code implements a data structure called PairSum designed to facilitate efficient addition of numbers and then allow checking if there exist any two unique or identical numbers which sum to a given target value. This task solution involves utilizing a HashMap to store each number added and their respective count of occurrences.

• Initialization:

  • The PairSum class features a constructor that initializes a HashMap called countMap, storing numbers as keys and their occurrences as values.

• Add Element:

  • The addElement method takes an integer num as an argument. This method checks if the number already exists in countMap. If it does, it increments its count; otherwise, it adds the number to the map with a count of one.

• Check Pair:

  • The checkPair method determines whether there exists a pair of numbers in countMap that adds up to a specified target value.
  • For each number in the countMap, it calculates the needed complementary number to meet the target sum by subtracting the current number from the target.
  • It checks two conditions:
    • If the complementary number is different from the current number and exists in countMap, it returns true indicating a successful pair match.
    • If the complementary number is the same as the current number, it checks if the count is greater than one; if so, it also returns true.
  • If no such conditions meet for any number, the method returns false, indicating no pair exists that sums to the target.

This structure makes it particularly efficient for operations where frequent additions and pair-checking are required, such as real-time data analysis or computational finance scenarios preferring quick response over bulky operations.

typedef struct {
    int id;
    int occurrences;
    UT_hash_handle hashHandler;
} ElementFrequency;
    
typedef struct {
    ElementFrequency* elementsFrequency;
} ArrayElementCounter;
    
ArrayElementCounter* createCounter() {
    ArrayElementCounter* counter = (ArrayElementCounter*)malloc(sizeof(ArrayElementCounter));
    counter->elementsFrequency = NULL;
    return counter;
}
    
void addElement(ArrayElementCounter* counter, int element) {
    ElementFrequency* elementFreq;
    HASH_FIND_INT(counter->elementsFrequency, &element, elementFreq);
    if (elementFreq == NULL) {
        elementFreq = (ElementFrequency*)malloc(sizeof(ElementFrequency));
        elementFreq->id = element;
        elementFreq->occurrences = 0;
        HASH_ADD_INT(counter->elementsFrequency, id, elementFreq);
    }
    elementFreq->occurrences++;
}
    
bool findIfPossibleSum(ArrayElementCounter* counter, int sum) {
    for (ElementFrequency* current = counter->elementsFrequency; current != NULL; current = current->hashHandler.next) {
        long required = (long)sum - current->id;
        if (required != (int)required) continue;
        ElementFrequency* foundElement;
        HASH_FIND_INT(counter->elementsFrequency, &required, foundElement);
        if (foundElement != NULL) {
            if (foundElement->id == current->id && current->occurrences > 1) {
                return true;
            } else if (foundElement->id != current->id) {
                return true;
            }
        }
    }
    return false;
}
    
void freeCounter(ArrayElementCounter* counter) {
    ElementFrequency *current, *temp;
    HASH_ITER(hashHandler, counter->elementsFrequency, current, temp) {
        HASH_DEL(counter->elementsFrequency, current);
        free(current);
    }
    free(counter);
}

The code provided focuses on designing a data structure to efficiently manage and check sums of pairs in a dynamic set of integers using the C programming language. The main features of this implementation involve creating, adding elements to, finding possible sums within, and freeing a custom data structure.

The data structure is made up of two main structs:

• ElementFrequency: This stores each unique integer and its occurrence count in the dataset.
• ArrayElementCounter: This struct acts as a container that holds a hash table of ElementFrequency elements.

The four main functions described in the code operate as follows:

1. createCounter: Initializes an ArrayElementCounter. This function dynamically allocates memory for an ArrayElementCounter and sets its internal hash table to NULL, readying it for elements to be added.

2. addElement: Adds an integer to the ArrayElementCounter. If the integer is new, it is added to the hash table with an occurrence count initialized to 0, which is then incremented. For existing integers, the occurrence count is simply incremented.

3. findIfPossibleSum: Determines if there exists any two distinct elements within the hash table that sum up to a specified value. This function uses the HASH_FIND_INT macro to search for the required complementary element that would form the desired sum with the current element. If a suitable pair is found (considering edge cases where the two elements might be the same), it returns true; otherwise, it continues searching until the hash table is exhausted.

4. freeCounter: Properly releases all memory allocated for the ArrayElementCounter and its elements. It iterates through the hash table, removing and freeing each element before finally freeing the ArrayElementCounter itself.

This solution is efficient in terms of both time and space complexities, making good use of the uthash library to handle the underlying hash table operations, such as adding and searching for elements.

const NumberPair = function () {
    this.counter = {};
};
    
NumberPair.prototype.addNumber = function (num) {
    if (num in this.counter) this.counter[num]++;
    else this.counter[num] = 1;
};
    
NumberPair.prototype.checkPairSum = function (targetSum) {
    for (let x in this.counter) {
        let y = targetSum - x;
        if (y != x) {
            if (y in this.counter) return true;
        } else {
            if (this.counter[x] > 1) return true;
        }
    }
    return false;
};

This article provides a solution summary for a problem that involves designing a data structure to efficiently add numbers and check if there exists any pair of numbers that sum up to a specified target. The implementation is in JavaScript.

The data structure, NumberPair, includes two major functionalities:

• Add numbers to the data structure.
• Check if there exists a pair of numbers within the structure whose sum equals a specified target.

The implementation involves the following steps:

1. Initialize NumberPair with a counter object to keep track of numbers and their respective counts.
2. Implement the addNumber method, which adds a number to the counter. If the number is already present, increase its count by one; otherwise, set its count to one.
3. Implement the checkPairSum method:
   • Iterate through each number, x, in the counter.
   • Calculate the complementary number y as targetSum - x.
   • For pairs (x, y) where x is not equal to y, check if y exists in the counter. If so, return true.
   • For pairs where x equals y, ensure there are at least two occurrences of x in the counter to form a valid pair. If so, return true.
4. If no valid pair is found by the end of the iteration, return false.

Features of this implementation include:

• Efficient addition of numbers.
• Quick pair sum checking using a hash table for constant-time look-ups.
• Handling duplicates by tracking the frequency of each number.

class PairSum(object):
    
    def __init__(self) -> None:
        self.value_counter = {}
    
    def add_value(self, number: int) -> None:
        if number in self.value_counter:
            self.value_counter[number] += 1
        else:
            self.value_counter[number] = 1
    
    def check_pair(self, target: int) -> bool:
        for key in self.value_counter:
            complement = target - key
            if key != complement:
                if complement in self.value_counter:
                    return True
            elif self.value_counter[key] > 1:
                return True
    
        return False

The problem titled "Two Sum III - Data structure design" involves creating a data structure that supports adding values and checking if any pair of numbers sum to a given target. The provided Python implementation addresses this challenge with the following functionality:

• Initialization: An instance of PairSum class initializes with a dictionary value_counter to keep track of occurrences of each value added.

• Adding a Value:

  1. Call add_value with an integer.
  2. Check if this number is already in value_counter.
  3. If present, increment its count.
  4. If not, insert it into the dictionary with a count of one.

• Checking for a Pair:

  1. Call check_pair with a target sum integer.
  2. Iterate through the keys (unique numbers) in value_counter.
  3. Calculate the complement of each key as the difference between the target and the current key.
  4. If the complement differs from the key, check if the complement exists in value_counter.
  5. If the same number is needed twice (e.g., 5 + 5 = 10), then check if its count in value_counter is greater than one.
  6. If any such pair exists that satisfies the condition, return True.
  7. If no suitable pair is found after iterating through all the numbers, return False.

• Output:

  • The method add_value enhances the data structure dynamically with each added value ensuring quick lookup times.
  • The check_pair function efficiently checks the possibility of achieving the target sum, making optimal use of the value_counter for quick access and verification.

This implementation efficiently supports the operations necessary for solving the "Two Sum III" problem using a hash map to store and verify the existence of number pairs that sum to a specified target.