A classic LeetCode Easy problem will be yet another gateway
into the fantastic world of optimization, which we have only begun to unlock with
Fibonacci recently.
The problem is the following:
·
You have a 1d array of integers
·
You are given a target number
·
There may or may not be a pair of numbers (only
one pair, and it will not be the same number twice) whose sum is the target
number
·
If such a pair exists, return an array with the
indices of the numbers that sum to the target
·
If no such pair exists, return [-1, -1] (recall
that -1 is the traditionally-used index for when something is not found in an
indexed collection)
It seems natural—naïve, yes, but natural—to check the
pairwise sum of every number with every other number. This does work and will
produce the correct result, but it is much less efficient than it could be.
The code might look something like
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i
< nums.length - 1; i++) {
for (int j = i
+ 1; j < nums.length; j++) {
if
(nums[i] + nums[j] == target) {
return
new int[] { i, j };
}
}
}
// Return [-1, -1]
if no solution is found
return new int[] {
-1, -1 };
}
No one reinvents the wheel here:
If this is our array:
|
2 |
3 |
5 |
2 |
1 |
4 |
6 |
And the target is 10,
the algorithm will check 2 and 3; 2 and 5; 2 and 2; 2 and 1; 2 and 4; 2 and 6;
3 and 5; 3 and 2; 3 and 1; 3 and 4; 3 and 6; 5 and 2; 5 and 1; 5 and 4; 5 and 6;
2 and 1; 2 and 4; 2 and 6; 4 and 6—and only on that last check will it find 4+
6 = 10, so it’ll return out {5, 6} since the match is in indices 5 and 6 (the 6th
and 7th positions, out of 7, in the array).
Again, this is correct, but wildly inefficient.
Let me propose a better solution: use a structure that we’ve already covered to
store both the current number and the number that would need to be found to pair
with it, to sum to the target.
Again, whatever structure we would use would need to do something like this,
storing pairs:
|
Found |
2 |
3 |
5 |
2 |
1 |
4 |
6 |
|
Need to see |
8 |
7 |
5 |
8 |
9 |
6 |
4 |
Can you think of any structures? How about, since we need to maintain the
pairs, a HashMap, whose key is an Integer and whose value is an Integer? Each
key-value pair then encodes what we’ve actually seen, and what we would need to
see to make a valid target-sum.
We can use the HashMap’s get() method to find the complement
of the number we’ve just seen. We can then use containsKey() to see if we have
the complement anywhere in the Map. If we come across a new number, calculate
its complement and put the new pair in the map. If we do eventually find a pair,
return where we found the pair; and if not, as before, we return {-1,-1}.
That looks like:
import java.util.HashMap;
public static int[] twoSum(int[] nums, int target) {
// Create a
HashMap to store numbers and their indices
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i
< nums.length; i++) {
// Calculate
the complement needed to reach the target
int complement
= target - nums[i];
// Check if
the complement has already been seen
if
(map.containsKey(complement)) {
// If
found, return the indices of the complement and current number
return new
int[] { map.get(complement), i };
}
// Otherwise,
store the current number and its index in the map
map.put(nums[i], i);
}
// If no solution
is found, return [-1, -1]
return new int[] {
-1, -1 };
}
Notice the enormous time savings this allows us to achieve in going from O(n^2)
looking at every possible pair, versus now looking at O(n) by having only one
pass through the array, since we’re using a map to store complements, updating
it as we go, and looking to see if the map contains a pair.
This problem is a classic for a reason: the naïve solution isn’t difficult at
all, but having the experience to know you can improve (and then actually
writing the improved solution) demonstrates you are no longer just a novice
programmer and have made real progress in learning how to systematically approach
