This weekend my wife and I spent it in Madison, Wisconsin visiting our son and family. We left Friday after work and returned Sunday afternoon. The drive is between 3.5 and 4.0 hours depending on traffic. Given that we are in the middle of the COVID-19 pandemic, we were amazed at how much traffic we encountered.
Last Friday morning I took a look into a couple problems but did not have time to write the associated posts. I will do if I have some time in the near future. Note that I have already addressed a similar problem in my post Sum of Two earlier this year.
In this post I will cover a problem I searched for on the web. This problem comes in different flavors. I found the one on LeetCode so I decided to take a stab at it.
The problem can be found using this URL. The name of the problem is Two 
Sum. F interested please read the complete description at the specified URL.
In a nutshell the idea is that given and array of integers, one must return the indices of the two numbers (hence the title of the post) such that they add up to a specific target.
Most (never say all) sites provide a window with an IDE. Not sure if developers use it. I do not. I like to read the problem description and generate the test scaffolding. In this case one is not provided. Once I have the test scaffolding I check it against the one provided by the site and if needed, make the necessary adjustments.
I decided to solve this problem using the Java programming language. I used the VSCode IDE by Microsoft.
At that point in time I am ready to code the function / method of interest. In this case we need to code the following function:
public int[] twoSum(int[] nums, int target) {
}
The arguments make sense. We receive the array of integers and a target number. The idea is to find the two integers that when added will produce the target sum.
4 2 7 11 15 9 [0, 1]
The first line contains the number of integers in the second line. The second line contains a set of integers which we will use to return the two indices in the array that will add to the number specified in the third row. This was the test example provided by LeetCode.
11 2 3 4 6 10 11 12 13 17 22 29 20 [1, 8]
This was my own test. I changed the numbers a few times in order to make sure things made sense.
3 3 2 4 6 [1, 2]
This was a test problem that failed after my first attempt to run my solution at LeetCode. If you are generating your own solutions, make sure you try these examples before any submissions. Of course, if you do not feel like generating your own test scaffolding, you will have to do your development on-line at LeetCode.
I do not feel compelled to save a few minutes developing my own test scaffolding. In my opinion I like to research and learn. I do not participate in challenges that are time sensitive. At work I prefer to put the extra time and come up with elegant and efficient solutions.
/**
* 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 = sumOfTwo(arr, target);
// **** display result ****
System.out.println(Arrays.toString(result));
}
My test scaffolding reads the data as expected. It then calls the specified function. 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.
*/
static int[] sumOfTwo(int[] nums, int target) {
// **** ****
int[] result = new int[2];
// **** generate a hashmap of values and indices O(n) ****
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
// !!!! generate the complement !!!!
int complement = target - nums[i];
// !!!! check if complement in hasmap !!!!
if (hm.containsKey(complement)) {
System.out.println(Arrays.toString(new int[] { hm.get(complement), i }));
}
// **** add value to hash map ****
hm.putIfAbsent(nums[i], i);
}
// **** traverse the array O(n) ****
for (int i = 0; i < nums.length; i++) {
// **** generate the complement ****
int complement = target - nums[i];
// **** look up the complement in the hashmap ****
if (hm.containsKey(complement) && (i != hm.get(complement))) {
result[0] = i;
result[1] = hm.get(complement);
return result;
}
}
// **** instead of returning [0, 0] ****
throw new IllegalArgumentException("No two sum solution");
}
I started by declaring an array which will be returned by this function. Note that when I was done, the array could have been defined when needed to be returned. The last line indicates this fact. The code throws an exception if the pair was not found. As you know, exceptions are expensive and the caller must deal with them. In this case, it seems that returning an array with two zeros would have been a welcomed approach.
I did not take time to address the brute force approach that takes O(n^^2) to complete. If you feel like that is something you feel is needed during your approach, go for it. The LeetCode site covers such approach.
My solution had two loops. In the first I populate a hash map which I will use in the second loop. Note the two comments with !s. These two statements were added after my base code was operational and had been accepted by LeetCode. It eliminates the second loop. It does the same work as the additional loop.
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, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1,579 subscribers to my blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa