Good morning. Hope you enjoyed the Halloween festivities yesterday. Today is November 01, 2021 and most countries celebrate today “All Saints’ Day” and tomorrow “All Souls’ Day”. In the USA we do not celebrate these holidays.
One way or the other, yesterday shortly past noon the crew of technicians installing our new furnace left, leaving us with an installed, calibrated, and properly functioning furnace. Last night the low temperature in this part of the Twin Cities of Minneapolis and St. Paul was 30F. The furnace worked a few times at night. It was quieter than our previous unit. What is more important, it worked flawlessly.
Today I have a couple meetings. Besides that it will be a normal workday.
I continue working on the 14 Days Study Plan to Crack Algo by LeetCode. So far all days have included two or three problems. In addition to solving the problem and then attempting to optimize it, I have to write and publish an associated post. Today generating the post took longer than solving the actual problem. In general both take about the same time. As expected, problems rated “hard” typically take longer.
Enough of furnace chit-chat and let’s dive into the problem at hand.
In this post we will attempt to solve LeetCode 167 Two Sum II – Input Array Is Sorted.
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Constraints: o 2 <= numbers.length <= 3 * 104 o -1000 <= numbers[i] <= 1000 o numbers is sorted in non-decreasing order. o -1000 <= target <= 1000 o The tests are generated such that there is exactly one solution. Related Topics: o Array o Two Pointers o Binary Search
We are given an array of int and a target value which represents the sum of two numbers in the array. We need to return in an array the indices of the two values that add up to the specified target. If interested in this problem, I suggest you read the current requirements, plan an approach and then solve it using the on-line IDE provided by LeetCode.
In our case we will try to come up with a solution using the Java programming language and the VSCode IDE on a Windows platform. Because we are going to develop the solution in my Windows machine, we will have to write a test scaffold that will read the input values, populate a couple variables, call the function of interest and display the output. Note that the test code IS NOT PART OF THE SOLUTION.
public int[] twoSum(int[] numbers, int target) {
}
The signature for the function of interest seems to match the problem requirements. We are given as parameters the int[] with the sorted values and the target for the sum. We need to return an int[] with the indices of the two numbers that add up to the specified target.
2,7,11,15 9 main <<< numbers: [2, 7, 11, 15] main <<< target: 9 <<< l: 0 r: 3 sum: 17 <<< l: 0 r: 2 sum: 13 <<< l: 0 r: 1 sum: 9 main <<< output: [1, 2] 2,3,4 6 main <<< numbers: [2, 3, 4] main <<< target: 6 <<< l: 0 r: 2 sum: 6 main <<< output: [1, 3] -1,0 -1 main <<< numbers: [-1, 0] main <<< target: -1 <<< l: 0 r: 1 sum: -1 main <<< output: [1, 2]
There are a few test cases. Each test case is separated from the next by a couple blank lines. If not mistaken, the first two test cases were provided by LeetCode.
Each test case contains two input lines. The first holds the values for the numbers int[]. The second line holds the value for the target.
The values are then displayed by our test scaffold to make sure all is well before calling the function of interest.
The function of interest is then called. The next few lines are generated by the function of interest. They are there to help us understand the algorithm we are using. Such lines are NOT PART OF THE SOLUTION.
When all is said and done the test code displays an int[] which contains the two selected indices in the `numbers` array which when added together return the `target` value.
/**
* Test Scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] numbers ****
int[] numbers = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read int target ****
int target = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< numbers: " + Arrays.toString(numbers));
System.out.println("main <<< target: " + target);
// **** call function of interest and display output ****
System.out.println("main <<< output: " + Arrays.toString(twoSum(numbers, target)));
}
Our test code seems to be simple and follows our description of a test case. I have nothing else to add at this time.
/**
* Find two numbers such that they add up to
* the specified target number.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II.
* Memory Usage: 39.2 MB, less than 74.14% of Java online submissions for Two Sum II.
*
* 19 / 19 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 39.2 MB
*
* Runtime: O(n) - Space: O(1)
*/
static public int[] twoSum(int[] numbers, int target) {
// **** initialization ****
int l = 0;
int r = numbers.length - 1;
// **** compute sum converging from left and right ****
while (l < r) {
// **** compute sum ****
int sum = numbers[l] + numbers[r];
// ???? ????
System.out.println("<<< l: " + l + " r: " + r + " sum: " + sum);
// **** check how to proceed ****
if (sum == target)
return new int[] {l + 1, r + 1};
else if (sum > target)
r--; // go left
else
l++; // go right
}
// **** should NOT occur based on requirements ****
return null;
}
I always like to start functions / methods with sanity checks. In this case, due to the requirements, I did not fill such a section. Perhaps I should have removed the comment (I removed it as we speak).
Our function of interest declares two indices. The `l’ will traverse the `numbers` array from left to right while the `r` will do the same from right to left.
We then enter a loop which will help us zero on the target value on each pass.
In the loop we compute the sum and act based on its value. If we find it we return an int[] array with the updated `l` and `r` values to take into account the requirements; otherwise we decide if we move `r` to the left one position or `l` one position to the right.
I believe the requirements indicate that a solution will be found so our code will not reach the end of the loop.
You can find performance information in the comments section of the function of interest. Seems that in this case the solution is quite optimal.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
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.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John