The 2-SUM Problem: Difference between revisions
| (7 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t. | Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t. Because the array is unsorted, we need to look at all numbers, so we cannot do better than Ω(n). | ||
=Naive Solution O(n<sup>2</sup>)= | |||
The naive solution would be to double loop over the array in O(n<sup>2</sup>) running time. | The naive solution would be to double loop over the array in O(n<sup>2</sup>) running time. | ||
=O(n log n) with No Additional Space Requirements= | |||
A better solution would be to sort the array O(n log n), then do a linear scan over the array and for each x<sub>i</sub> element search using [[Binary_Search#Overview|binary search]] for t - x<sub>i</sub>. Binary search on a sorted array is done in O(log n) time, so the total complexity is O(n log n) + n O(log n) = O(n log n). | |||
=Θ(n) with Additional Space Requirements= | |||
A better running time solution that comes with an extra space requirement, though, is to insert all numbers in a [[Hash_Table#Canonical_Use|hash table]] and then do a second pass where for each number we look to see if t - x<sub>i</sub> exists in the table. This is a Θ(n) solution. | |||
Latest revision as of 20:37, 16 October 2021
Internal
Overview
Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t. Because the array is unsorted, we need to look at all numbers, so we cannot do better than Ω(n).
Naive Solution O(n2)
The naive solution would be to double loop over the array in O(n2) running time.
O(n log n) with No Additional Space Requirements
A better solution would be to sort the array O(n log n), then do a linear scan over the array and for each xi element search using binary search for t - xi. Binary search on a sorted array is done in O(log n) time, so the total complexity is O(n log n) + n O(log n) = O(n log n).
Θ(n) with Additional Space Requirements
A better running time solution that comes with an extra space requirement, though, is to insert all numbers in a hash table and then do a second pass where for each number we look to see if t - xi exists in the table. This is a Θ(n) solution.