Two Sum#
Given an array of integers nums and an integer target, return indices of
the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Detailed Analysis#
Theoretical Best Time Complexity#
The theoretical best time complexity for this problem is \(\mathcal{O}(n^2)\),
where \(n\) is the length of the nums array. This is because the solution
involves a nested loop structure where each element is compared with each other
element in the array once.
Theoretical Best Space Complexity#
The theoretical best (auxiliary) space complexity for this problem is
\(\mathcal{O}(1)\). This is due to the fact that the solution only requires a
fixed amount of space to store the complement variable and the two indices to
be returned. No additional space that scales with input size is used. Even if I
added a len_ variable, it still wouldn’t scale with input size.
Space-Time Tradeoff#
This represents a space-time tradeoff: While the space complexity is very low, the time complexity is quite high. This could be improved with the use of additional space. For example, a hash map could be used to store previously seen elements, allowing us to check for the existence of the complement in constant time. This would increase the space complexity to \(\mathcal{O}(n)\), but reduce the time complexity to \(\mathcal{O}(n)\) as well.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""
Given a list of integers and a target integer, this function finds two
integers in the list that sum to the target. Returns a list of two indices
of the numbers that add up to the target.
Parameters
----------
nums : List[int]
The list of numbers.
target : int
The target number.
Returns
-------
List[int]
The indices of the two numbers that sum to the target.
Examples
--------
>>> nums = [15, 2, 3, 7]
>>> target = 9
>>> Solution().twoSum(nums, target)
[1, 3]
"""
len_: int = len(nums)
for i in range(len_):
for j in range(i + 1, len_):
complement: int = target - nums[i]
if nums[j] == complement:
return [i, j]
Time Complexity#
The time complexity of the given algorithm is \(\mathcal{O}(n^2)\). This is because we traverse the list of length \(n\) twice, once for the outer loop and once for the inner loop. Every operation inside these loops, including the subtraction and comparison, has a time complexity of \(\mathcal{O}(1)\).
To understand this in a more practical sense, consider the nested loops from
lines 31 to 35. Each line inside these loops has a time complexity of
\(\mathcal{O}(1)\), meaning it takes a constant amount of time to execute,
regardless of the size of the input. This suggests that a typical iteration
inside the loop would require approximately \(\mathcal{O}(3)\) time, given that
there are three operations within the loop.
However, since the outer loop runs \(n\) times and for each outer loop, the inner loop also runs \(n\) times (where \(n\) is the length of the input list), the overall time required would be \(n^2\) times the time required for a single iteration. This gives us:
In big-O notation, we typically omit constant multipliers since we’re primarily interested in how the runtime scales with the size of the input. Hence, we simplify \(\mathcal{O}(3n^2)\) to \(\mathcal{O}(n^2)\). This signifies that the runtime of the algorithm grows quadratically with the size of the input list.
Case |
Worst Case |
Average Case |
Best Case |
|---|---|---|---|
Element is in the list (Two numbers add up to target) |
\(\mathcal{O}(n^2)\) |
\(\mathcal{O}\left(\frac{n(n-1)}{4}\right)\) |
\(\mathcal{O}(1)\) |
Element is not in the list (No two numbers add up to target) |
\(\mathcal{O}(n^2)\) |
\(\mathcal{O}(n^2)\) |
\(\mathcal{O}(n^2)\) |
Remark 66 (The Average Case)
Assuming nums is an array of \(n\) elements, and \((i, j)\) is a potential
solution pair (i.e., nums[i] + nums[j] == target), where \(i\) and \(j\) are any
indices in the array.
If the inputs are uniformly distributed, the probability that \((i, j)\) is the solution is the same for all valid pairs of indices \((i, j)\).
In the case of nested loops, we generate all pairs of elements from nums. The
number of such pairs is \(\frac{n(n-1)}{2}\). Hence, on average, you’d have to
search through half of all possible pairs before finding the correct one.
That is, on average, we inspect \(\frac{n(n-1)}{4}\) pairs before finding the pair
that sums to target. While this evaluates to a different number of pairs than
the worst-case scenario, when we express this in terms of Big O notation, we
focus on the highest order term and ignore constant factors and lower order
terms.
Therefore, we still classify the average case time complexity as \(\mathcal{O}(n^2)\). This signifies that, on average, the runtime of the algorithm scales quadratically with the size of the input list.
Space Complexity#
Type |
Complexity |
Description |
|---|---|---|
Input Space |
\(\mathcal{O}(n)\) |
The input space depends on the size of the input list |
Auxiliary Space |
\(\mathcal{O}(1)\) |
The auxiliary space depends on the size of the |
Total Space |
\(\mathcal{O}(n)\) |
The total space is the sum of the input and auxiliary space. |
The auxiliary (extra) space required depends on the number of items stored in
complement variable and the two indices we return.
Input Space#
The input space for this function is the space needed to store the input data,
which in this case is the list nums. Since nums is a list of n integers,
the space required to store this list is proportional to n. Therefore, the
input space complexity is \(\mathcal{O}(n)\).
Auxiliary Space#
The auxiliary space is the extra space or the temporary space used by the
algorithm. In the given function, we use a variable complement to store the
result of the subtraction and we have two integers i and j that could be
returned. As such, regardless of the size of nums, the auxiliary space used
remains constant. Therefore, the auxiliary space complexity is \(\mathcal{O}(1)\).
Total Space#
The total space required by an algorithm is the sum of the input space and the auxiliary space. In this case, the total space is \(\mathcal{O}(n) + \mathcal{O}(1)\), which simplifies to \(\mathcal{O}(n)\). Therefore, the total space complexity of the given function is \(\mathcal{O}(n)\).
In summary, the given function has a space complexity of \(\mathcal{O}(n)\), where
n is the number of elements in the input list nums. This is because it
requires storing the input data (nums) and a constant amount of auxiliary
space.