It is a very nice sunny day in the Twin Cities of Minneapolis and St. Paul. Today is March 29, 2021 and the high for the day is going to be around 70F. My wife and I talked about grilling chicken for lunch but it is a work day and the process of grilling, eating and cleaning might take a couple hours. That is fine on a holiday.
I decided to attempt to solve all problems in a section of LeetCode. It seems that several problems that I have solved before fall into this collection. I will take a problem from each category a day. Perhaps on weekends I will look at two.
Today we will look at Two Sum. I took a look at this problem and at the time I generated a post Two Sum.
Let’s take a look at the problem description.
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. Constraints: o 2 <= nums.length <= 103 o -109 <= nums[i] <= 109 o -109 <= target <= 109 Only one valid answer exists.
We are given an array of integers and an integer target. The idea is to return an array with the two indices (order not important) for the values in the array that sum up to the specified target. As usual, if you are interested in the problem please go to the LeetCode site and get the current description for Two Sum.
We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows 10 machine. We will not use the on-line IDE provided by LeetCode. Because of that we will have to generate some test code that will collect the input, process it, make the call for the function / method in questions and display the results.
4 2 7 11 15 9 main <<< n: 4 main <<< target: 9 main <<< arr: [2, 7, 11, 15] [1, 0] [0, 1] 11 2 3 4 6 10 11 12 13 17 22 29 20 main <<< n: 11 main <<< target: 20 main <<< arr: [2, 3, 4, 6, 10, 11, 12, 13, 17, 22, 29] [8, 1] [1, 8] 3 3 2 4 6 main <<< n: 3 main <<< target: 6 main <<< arr: [3, 2, 4] [2, 1] [1, 2]
The first input line contains the number of integers we are provided. The second line holds the actual integers. Note that the range is described in the constraints of the problem. In addition do not expect the integers to be in any particular order. Note that the first two examples contain integers in an ascending order. The third example does not. The third input line contains the target or sum of two integers in the array.
Our test scaffold reads the input data and displays it to make sure all is well so far. It then makes call to two implementations. Both seem to return the same values (in different order). As mentioned in the requirements, the order does not matter.
/**
* Test scafolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of integers in the array ****
int n = sc.nextInt();
// ???? ????
System.out.println("main <<< n: " + n);
// **** allocate array of integers ****
int[] arr = new int[n];
// **** populate the array ****
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// **** read the target ****
int target = sc.nextInt();
// ???? ????
System.out.println("main <<< target: " + target);
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** generate result (if possible) ****
int[] result = sumOfTwo1(arr, target);
// **** display result ****
System.out.println(Arrays.toString(result));
// **** generate result (if possible) ****
result = sumOfTwo(arr, target);
// **** display result ****
System.out.println(Arrays.toString(result));
}
The test scaffold seems to operate as described. After the input data is collected two implementations of the solution are called. The results are displayed.
/**
* Given an array of integers, return indices of the two numbers
* such that they add up to a specific target.
*
* You may assume that each input would have exactly one solution,
* and you may not use the same element twice.
*
* Worse case: O(n^2)
*
* Runtime: 0 ms
* Memory Usage: 39.3 MB
*/
static int[] sumOfTwo(int[] nums, int target) {
// **** traverse array O(n) ****
for (int i = 0; i < nums.length - 1; i++) {
// **** traverse array O(n) ****
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
// **** did not find solution ****
throw new IllegalArgumentException("No two sum solution");
}
This is the brute force approach. We start with the first entry in the array and loop for all other entries looking for the one that adds up to the target. If not found, we move to the next entry and repeat the process. Given the number and complexity of the test cases the approach seems to work well.
/**
* Given an array of integers, return indices of the two numbers
* such that they add up to a specific target.
*
* You may assume that each input would have exactly one solution,
* and you may not use the same element twice.
*
* Runtime: 0 ms
* Memory Usage: 38.9 MB
*/
static int[] sumOfTwo1(int[] nums, int target) {
// **** initialization ****
int[] result = new int[2];
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// **** generate a hashmap of values and indices O(n) ****
for (int i = 0; i < nums.length; i++) {
// **** generate the complement for this value ****
int complement = target - nums[i];
// **** check if complement in the hasmap (found matching number) ****
if (hm.containsKey(complement)) {
result[0] = i;
result[1] = hm.get(complement);
return result;
}
// **** add value to hash map ****
hm.putIfAbsent(nums[i], i);
}
// **** instead of returning [0, 0] ****
throw new IllegalArgumentException("No two sum solution");
}
This is an updated approach from the last post. The idea is to insert into the hash map the complement and the index in the array. As soon as we encounter the entry in the hash map we are done. If the complement is not in the hash map we add it to it.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all subscribers to this blog!!!
Regards;
John