Lecture on solving a popular LeetCode Problem
Problem Statement
- Given an input array and a target sum, find two values in the array that sum to the target.
- Return the indices of these two values.
- Example: Input array =
[2, 7, 1, 5, 3]
, target = 9
=> Output = [0, 1]
(indices of 2
and 7
).
- Assumptions:
- There is exactly one solution.
- No need to consider multiple or no solutions.
Brute Force Solution
-
Approach:
- Check every combination of two values.
- Examine if they sum to the target.
- Process: For each element, check it with every possible combination with the remaining elements.
-
**Example:
- Start with
2
:
- Check
2
with remaining elements 1, 5, 3
, none sum to 9
.
- Move to
1
:
- Check
1
with 5
and 3
.
1 + 3 = 4
(find the pair that sums up to the target).
-
Complexity:
Optimized Solution Using Hash Map
-
**Concept:
- Utilize a hash map to store elements and their indices.
- Check if the complement of the current element exists in the hash map.
-
**Steps:
- Initialize an empty hash map.
- Iterate through the array:
- For current element
x
, calculate the complement needed to reach the target: complement = target - x
.
- Check if
complement
exists in the hash map.
- If it exists, return the indices of
complement
and x
.
- Otherwise, add
x
to the hash map.
-
**Algorithm:
- Initialize an empty hash map. (Python:
previousMap = {}
)
- Iterate over the array elements (need both index
i
and actual value n
):
for i, n in enumerate(array):
complement = target - n
if complement in previousMap:
return [previousMap[complement], i]
previousMap[n] = i
- If a solution exists, it will be found during iteration.
- No need for special return cases as one solution is guaranteed.
-
**Complexity:
- Time Complexity:
O(n)
(due to single pass and constant time lookup/add operations).
- Space Complexity:
O(n)
(for storing elements in hash map).
Implementation in Python
array = [2, 7, 1, 5, 3]
target = 9
previousMap = {}
for i, n in enumerate(array):
complement = target - n
if complement in previousMap:
print([previousMap[complement], i]) # Output the result
previousMap[n] = i
- Code will find the solution and print indices of values that sum to the target.