Two Sum III - Data structure design

🏠 ⬅️ ➡️

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.

Example 1:

Input [ "TwoSum ", "add ", "add ", "add ", "find ", "find "] [[], [1], [3], [5], [4], [7]] Output [null, null, null, null, true, false]

Explanation TwoSum twoSum = new TwoSum(); twoSum.add(1); // [] --> [1] twoSum.add(3); // [1] --> [1,3] twoSum.add(5); // [1,3] --> [1,3,5] twoSum.find(4); // 1 + 3 = 4, return true twoSum.find(7); // No two integers sum up to 7, return false

Constraints:

  • -105 <= number <= 105
  • -231 <= value <= 231 - 1
  • At most 104 calls will be made to add and find.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use :: two_sum_mod
    implicit none

    type(TwoSum) :: two_sum
    integer :: i
    integer, parameter :: n = 6
    integer, parameter :: nums(n) = [1, 3, 5, 4, 7, 2]
    logical, parameter :: expected(n) = [.false., .true., .true., .true., .false., .false.]

    do i = 1, n
        call two_sum%add(nums(i))
        write(*, '(A, L1)') 'find(', nums(i), ') = ', two_sum%find(nums(i))
    end do

end program main

module two_sum_mod
    implicit none

    private
    public :: TwoSum

    type :: TwoSum
        private
        integer, allocatable :: numbers(:)
    contains
        procedure, pass :: add
        procedure, pass :: find
    end type TwoSum

contains

    subroutine add(this, number)
        class(TwoSum), intent(inout) :: this
        integer, intent(in) :: number

        allocate(this%numbers(size(this%numbers)+1))
        this%numbers(size(this%numbers)) = number
    end subroutine add

    function find(this, value) result(has_pair)
        class(TwoSum), intent(in) :: this
        integer, intent(in) :: value
        logical :: has_pair
        integer :: i, j

        has_pair = .false.
        do i = 1, size(this%numbers)-1
            do j = i+1, size(this%numbers)
                if (this%numbers(i) + this%numbers(j) == value) then
                    has_pair = .true.
                    exit
                end if
            end do
            if (has_pair) exit
        end do
    end function find

end module two_sum_mod
❌ Compiled
❌ Executed
❌ Correct 
! Declare the TwoSum class
module TwoSum

! Declare the data structure
type :: TwoSum
    integer, allocatable :: numbers(:)
end type TwoSum

! Declare the constructor
interface TwoSum
    module procedure :: createTwoSum
end interface TwoSum

! Declare the add method
interface add
    module procedure :: addNumber
end interface add

! Declare the find method
interface find
    module procedure :: findSum
end interface find

contains

! Create a new TwoSum object
function createTwoSum() result(this)
    type(TwoSum) :: this

    ! Allocate the array
    allocate(this%numbers(0))
end function createTwoSum

! Add a number to the data structure
subroutine addNumber(this, number)
    class(TwoSum), intent(inout) :: this
    integer, intent(in) :: number

    ! Allocate more space in the array if necessary
    if (size(this%numbers) == 0) then
        allocate(this%numbers(1))
    else if (size(this%numbers) == size(this%numbers, 1)) then
        allocate(this%numbers(2 * size(this%numbers)))
        this%numbers(1:size(this%numbers) - 1) = this%numbers
    end if

    ! Add the number to the end of the array
    this%numbers(size(this%numbers)) = number
end subroutine addNumber

! Check if there exists any pair of numbers that sum up to a particular value
function findSum(this, value) result(exists)
    class(TwoSum), intent(in) :: this
    integer, intent(in) :: value
    logical :: exists
    integer :: i, j

    ! Initialize the result
    exists = .false.

    ! Loop through the array
    do i = 1, size(this%numbers)
        ! Check if the current number is equal to the value
        if (this%numbers(i) == value) then
            exists = .true.
            exit
        end if

        ! Check if the current number is less than the value
        if (this%numbers(i) < value) then
            ! Loop through the rest of the array
            do j = i + 1, size(this%numbers)
                ! Check if the current number plus the previous number is equal to the value
                if (this%numbers(i) + this%numbers(j) == value) then
                    exists = .true.
                    exit
                end if
            end do
            if (exists) exit
        end if
    end do
end function findSum

end module TwoSum

! Test the TwoSum class
program testTwoSum
    use TwoSum
    implicit none

    ! Create a new TwoSum object
    type(TwoSum) :: twoSum

    ! Add some numbers to the data structure
    call twoSum%add(1)
    call twoSum%add(3)
    call twoSum%add(5)

    ! Check if there exists any pair of numbers that sum up to 4
    write(*,*) twoSum%find(4)

    ! Check if there exists any pair of numbers that sum up to 7
    write(*,*) twoSum%find(7)
end program testTwoSum
🌐 Data from online sources 
class TwoSum:

    def __init__(self):
        self.nums = {}

    def add(self, number: int) -> None:
        if number in self.nums:
            self.nums[number] += 1
        else:
            self.nums[number] = 1

    def find(self, value: int) -> bool:
        for num in self.nums:
            target = value - num
            if target in self.nums:
                if target != num or self.nums[num] > 1:
                    return True
        return False

We create a class TwoSum to represent the data structure. We use a hashmap (unordered_map in C++, HashMap in Java, dictionary in Python, and object in JavaScript) to store the numbers as keys and their counts as values.

In the add method, we simply increment the count of the number in the hashmap.

In the find method, we iterate through the keys of the hashmap. For each number, we calculate its complement (value - number). If the complement is present in the hashmap, we check two cases: 1. If number and complement are the same, we need at least two occurrences of the number in the hashmap to form a pair. 2. If number and complement are different, we have our required pair and return true.

If we go through the entire hashmap and don't find any pair that satisfies one of the above conditions, we return false.

🌐 Data from online sources 
class TwoSum {
public:
    unordered_map<int, int> m;

    TwoSum() {

    }

    void add(int number) {
        m[number]++;
    }

    bool find(int value) {
        for (auto &pair : m) {
            int num1 = pair.first;
            int num2 = value - num1;
            if (num1 == num2 && pair.second > 1 || num1 != num2 && m.count(num2)) {
                return true;
            }
        }
        return false;
    }
};

We create a class TwoSum to represent the data structure. We use a hashmap (unordered_map in C++, HashMap in Java, dictionary in Python, and object in JavaScript) to store the numbers as keys and their counts as values.

In the add method, we simply increment the count of the number in the hashmap.

In the find method, we iterate through the keys of the hashmap. For each number, we calculate its complement (value - number). If the complement is present in the hashmap, we check two cases: 1. If number and complement are the same, we need at least two occurrences of the number in the hashmap to form a pair. 2. If number and complement are different, we have our required pair and return true.

If we go through the entire hashmap and don't find any pair that satisfies one of the above conditions, we return false.