Classic two sum problem
Problem
Given the array of integer, A = {1, 6, 8, 2. 7}, and target sum, 9, you need to write the problem to tell where there are two integers whose sum equals 9.
2022-03-22: Additional constraints
How will you change your algorithm if the input has duplicate values and you can't use the same values twice? You should return all matching number pairs.
A = {1,3,3,5,7,8,4,4}, target sum 8
[ [3,5], [4,4]]
This is a classic two-sum problem.
Given the array, A, and a target sum, S.
Basically, we can use HashTable, which provides $O(1)$ for accessing the element with a key, to search the value, L, where $$L = S - A_{i} \text {, where} A_{i} \in A$$.
For each $A_{i} \in A$, we can perform the check stated above. This takes $O(N)$ time thanks to the HashTable.
Here is the rough algorithm:
1. Add all numbers in A to the hash table.
2. Check if L exists in the hash table. Return true if exists.
Here is the algorithm running in $O(N)$, theoretically but $O( N \log N) practically due to the std::set data structure.
Practice statistics
10 mins: to write up the code.
UPDATE: 2019-09-24
Encounter this problem during the interview and could think of the solution with HashTable. I came up with a different solution using Dynamic problems. However, it was overkill.
Here is the solution in Python running in $O(N)$.
Given the array, A, and a target sum, S.
Basically, we can use HashTable, which provides $O(1)$ for accessing the element with a key, to search the value, L, where $$L = S - A_{i} \text {, where} A_{i} \in A$$.
For each $A_{i} \in A$, we can perform the check stated above. This takes $O(N)$ time thanks to the HashTable.
Here is the rough algorithm:
1. Add all numbers in A to the hash table.
2. Check if L exists in the hash table. Return true if exists.
Here is the algorithm running in $O(N)$, theoretically but $O( N \log N) practically due to the std::set data structure.
Practice statistics
10 mins: to write up the code.
UPDATE: 2019-09-24
Encounter this problem during the interview and could think of the solution with HashTable. I came up with a different solution using Dynamic problems. However, it was overkill.
Here is the solution in Python running in $O(N)$.
UPDATE: 2022-03-27
Encounter the new two-sum variation and got it wrong during the interview. It wasn't that important interview but I felt bad.
If there are duplicate numbers in the input and we can't use the same number twice in the answer, we need to keep the count of the numbers in the hashmap and keep track of the count for both numbers used in the answer.
The initial answer did not decrease the count for the first number and got the wrong answer.
Here is the python answer running in $O(N)$ time.
Comments
Post a Comment