Good day. It is Wednesday and it feels like winter is just around the corner in the Twin Cities of Minneapolis and St. Paul.
Earlier today I attended an O’Reilly webinar. The subject was not as interesting as I thought. What called my attention was the fact that I had to download and install the RingCentral app. After the webinar was done I removed the app from my computer. For security reasons, I prefer to keep installed only the apps that I frequently use and download the ones that I seldom use when needed.
The app seems to be easy to use. I checked RingCentral on Wikipedia. The company is traded in NYSE and the company was founded in 1999. In 2019 their revenue was 902.8 million USD. Looks like the founders figured out there was an opportunity to profit during the COVID pandemic, and they offer a good product.
Out of curiosity, I looked up Zoom Video Communications on Wikipedia. I did not know that it was founded in 2011, long before the COVID pandemic. In 2021 their revenue was 2.7 billion USD. Zoom is another app that I install on my computer when needed.
Over the weekend visiting my younger son, the subject of personality types came up. My daughter in law sent me a few links. I have been reading them on and off. Will have more to say about my findings in my next post.
OK, enough chit-chat and let’s get into the main subject for his post.
I continue to solve the problems offered by Algorithm I in “14 Days Study Plan to Crack Algo” by LeetCode . Earlier today I tackled LeetCode problem 35 Search Insert Position.
If interested in this problem, I suggest you go to the LeetCode website and read the current description of the problem. After I am done working on a problem, I like to check on the web different approaches in addition to the solutions submitted to LeetCode. While I was looking at solutions on-line, I noticed that on some sites they did not include the complete current description. I will indicate the difference shortly.
Given a sorted array of `distinct` integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Constraints: o 1 <= nums.length <= 104 o -104 <= nums[i] <= 104 o nums contains distinct values sorted in ascending order. o -104 <= target <= 104 Related Topics: o Array o Binary Search
We are given an array of `distinct` integers and a `target` value. Our mission, if we do accept it, is to return the index in the array holding the `target` value. If we cannot find it, we need to return the index in the array in which we would insert it to keep the array in sorted order.
Regarding the change in the description, the “You must write an algorithm with O(n log(n)) runtime complexity” sentence was added. Without it you could just traverse the sorted array looking for the `target` in O(n) time complexity. With this added statement, one has to use an algorithm with a modified binary search.
1,3,5,6 5 main <<< nums: [1, 3, 5, 6] main <<< target: 5 <<< nums[1]: 3 <<< nums[2]: 5 main <<< output: 2 <<< nums[1]: 3 <<< nums[2]: 5 main <<< output: 2 1,3,5,6 2 main <<< nums: [1, 3, 5, 6] main <<< target: 2 <<< nums[1]: 3 <<< nums[0]: 1 main <<< output: 1 <<< nums[1]: 3 <<< nums[0]: 1 main <<< output: 1 1,3,5,6 7 main <<< nums: [1, 3, 5, 6] main <<< target: 7 main <<< output: 4 <<< nums[1]: 3 <<< nums[2]: 5 <<< nums[3]: 6 main <<< output: 4 1,3,5,6 0 main <<< nums: [1, 3, 5, 6] main <<< target: 0 main <<< output: 0 <<< nums[1]: 3 <<< nums[0]: 1 main <<< output: 0 1 0 main <<< nums: [1] main <<< target: 0 main <<< output: 0 <<< nums[0]: 1 main <<< output: 0 1 1 main <<< nums: [1] main <<< target: 1 main <<< output: 0 <<< nums[0]: 1 main <<< output: 0 1 2 main <<< nums: [1] main <<< target: 2 main <<< output: 1 <<< nums[0]: 1 main <<< output: 1
I will solve this problem using Java and the VSCode IDE on a Windows platform. My suggestion is for you to use the on-line IDE provided by LeetCode. That way you will not have to develop a test scaffold to read the input values, populate associated variables, call the function of interest and display the output.
public int searchInsert(int[] nums, int target) {
}
The signature for the function of interest is as expected. It takes an int[] array `nums` and a `target` value.
Going back to the snippet holding the test cases, we are provided two input lines. The first holds the sorted integer values for the `nums` array. The second line holds the value for the `target`.
Our test scaffold appears to read the two input lines, populate the proper set of variables and then displays them. This is done in order to verify that all is well so far.
It seems that we have two solutions. They both return the same output. The additional information is there to help us understand what is going on. Both implementations are almost identical. I decided to copy and paste the code and then make simple changes.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums int[] array ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read target ****
int target = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
System.out.println("main <<< target: " + target);
// **** call function of interest and display returned output ****
System.out.println("main <<< output: " + searchInsert0(nums, target));
// **** call function of interest and display returned output ****
System.out.println("main <<< output: " + searchInsert(nums, target));
}
Now that we have a good idea of what our test code is doing, we can take a look at it. It seems that there is little if any thing to add to the description of the test code at this time. Please note that the test scaffold IS NOT PART OF THE SOLUTION.
/**
* Return the index if the target is found.
* If not, return the index where it would
* be if it were inserted in order.
*
* Using binary search to locate index.
*
* 64 / 64 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.8 MB
*
* Execution: O(n log(n)) - Space: O(1)
*/
static public int searchInsert0(int[] nums, int target) {
// **** sanity check(s) ****
if (nums.length == 1 && nums[0] == target) return 0;
if (target < nums[0]) return 0;
if (nums[nums.length - 1] < target) return nums.length;
// **** initialization ****
int l = 0;
int r = nums.length - 1;
// **** search for the location in the array ****
while (l <= r) {
// **** compute mid point ****
int m = l + (r - l) / 2;
// ???? ????
System.out.println("<<< nums[" + m + "]: " + nums[m]);
// **** check if target was found ****
if (nums[m] == target) return m;
// **** decide which way to continue the search ****
if (nums[m] > target)
r = m - 1; // go left
else
l = m + 1; // go right
}
// **** return index to insert target ****
return l;
}
This is the first implementation of the function of interest. As we previously mentioned and as suggested as a hint by LeetCode, the implementation uses a modified binary search to solve the problem.
We start by performing some sanity checks. In a nutshell we take care of a single value array, and the conditions of having a `target` value that falls to the left or right of the `nums` array.
We then initialize the left and right ends of the current range of numbers in the `nums` array.
The loop is where the binary search takes place.
We start by computing the midpoint in the current range and assign it to the `m` variable.
We check if we found the `target` in the `nums` array at the `m` position. If so, we return `m`. Otherwise we update the range of interest in the `nums` array and start the next loop if the condition holds true.
If we do not find the `target` in the array we will be inserting the`target` value in the index held by the ‘l’ variable.
/**
* Return the index if the target is found.
* If not, return the index where it would
* be if it were inserted in order.
*
* Using binary search to locate index.
*
* 64 / 64 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.8 MB
*/
static public int searchInsert(int[] nums, int target) {
// **** initialization ****
int l = 0;
int r = nums.length - 1;
// **** search for the location in the array ****
while (l <= r) {
// **** compute mid point ****
int m = l + (r - l) / 2;
// ???? ????
System.out.println("<<< nums[" + m + "]: " + nums[m]);
// **** check if target was found ****
if (nums[m] == target) return m;
// **** decide which way to continue the search ****
if (nums[m] > target)
r = m - 1; // go left
else
l = m + 1; // go right
}
// **** return index to insert target ****
return l;
}
As you can verify, the only difference is that this version does not have the sanity check(s) statements. I believe the rest of the code is the same.
Note that the execution times are identical. The runtime and space are the same. This information is held in the comments section of the two implementations of the function of interest.
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.
Regards;
John