Good morning! It is Friday and the weekend is just around the corner. In the Twin Cities of Minneapolis and St. Paul we received our first snow dusting of the season. Yesterday early morning I drove my wife to a healthcare facility to get a radiological exam. Traffic was heavier than what we expected. We got back home around 09:00 AM. The rest of the day ended for me at 19:00 PM. It was a very long and exciting day.
As the weather changes, I have slightly modified my workdays. I work in 2-hour blocks. The blocks are dictated by the EyeDefender app. I tend to work four to five blocks during the week and one to two on weekends. After each block I get on a stationary bike and pedal backwards for about two minutes and forward for six. This gives me over half an hour of exercise per day and half on weekends.
Starting this week, I will not stop immediately after EyeDefender tells me to do so. Will continue with the bike exercise after each block. Doing this will reduce the blocks to four on workdays. I guess it is better to continue working past the two hours until I reach a normal breaking point based on the task at hand. Will let you know my findings as far as productivity is related early next year.
One last thing, most of the times that I generate a post, I check on the number of subscribers. Today’s count is 10,025 subscribers Thanks a lot!!! This implies that in the very near future I will, in addition to this post, start a YouTube channel with similar content or will just switch to YouTube and discontinue this blog. One way or the other, I will be getting the necessary video hardware and software tools, and will start experimenting with them. I am planning on having the YouTube channel up and running by January 2022.
Yesterday I was able to pick up a problem which is the main topic for this post.
I like to solve problems that can check for correctness. In this case I just have a recollection of the problem a software manager and I were discussing. When we solve problems in this blog from some websites i.e., Codility, HackerRank, or LeetCode, accepted solutions are tested against several test cases which were not created by us (the developers). It is important to have a third party test the code generated by a development group. In this case this code has not been checked by a third party.
We are given an array of integers with values in ascending but not contiguos order, followed by descending values also not in continuous order. A single high value is guaranteed. We need to find and return the highest value in the array. Throwing a wrench into the problem: o values at contiguous positions may repeat Assumptions: o -1000 <= arr[i] <= 1000 o 3 <= arr.length <= 1000
While discussing the problem we did not have a written description. What you just read is my edited recollection of the problem description.
We are given an array with integers. Initially the values are in ascending order but they are not contiguous. At some point there is a single high value. From that point the integers are in a descending order but they are not contiguous. Please take a look at the test cases in the next few lines to make sure the description of the contents of the array are understood.
The idea is to implement a function of interest that would return the highest value in the array.
We will cover two implementations. The first is a brute force approach and the second is more efficient and elegant.
To top it off, we are given a complication. The integers in the initial array are unique. We need to solve the same problem but with duplicate values.
public int findHigh(int[] arr) {
}
The signature for the function of interest indicates that we are given an int[] array and we must return the high value from the array.
We will be solving this problem using the Java programming language and the VSCode IDE on a Windows platform.
-20,-10,2,10,20,30,40,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 30, 40, 2, -10, -20] main <<< result: 40 <<< len: 10 <<< l: 0 r: 9 <<< arr[4]: 20 <<< l: 5 r: 9 <<< arr[7]: 2 <<< l: 5 r: 6 <<< arr[5]: 30 <<< l: 6 r: 6 <<< arr[6]: 40 main <<< result: 40 -20,-10,2,10,20,30,40,20,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 30, 40, 20, 2, -10, -20] main <<< result: 40 <<< len: 11 <<< l: 0 r: 10 <<< arr[5]: 30 <<< l: 6 r: 10 <<< arr[8]: 2 <<< l: 6 r: 7 <<< arr[6]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,30,40,2,2,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 30, 40, 2, 2, 2, -10, -20] main <<< result: 40 <<< len: 15 <<< l: 0 r: 14 <<< arr[7]: 20 <<< l: 8 r: 14 <<< arr[11]: 2 <<< (2,2,2) <<< i: 2 (40,-10) <<< l: 8 r: 9 <<< arr[8]: 30 <<< l: 9 r: 9 <<< arr[9]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,30,40,2,2,2,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 30, 40, 2, 2, 2, 2, -10, -20] main <<< result: 40 <<< len: 16 <<< l: 0 r: 15 <<< arr[7]: 20 <<< l: 8 r: 15 <<< arr[11]: 2 <<< (2,2,2) <<< i: 2 (40,2) <<< l: 8 r: 9 <<< arr[8]: 30 <<< l: 9 r: 9 <<< arr[9]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,30,40,2,2,2,2,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 30, 40, 2, 2, 2, 2, 2, -10, -20] main <<< result: 40 <<< len: 17 <<< l: 0 r: 16 <<< arr[8]: 30 <<< l: 9 r: 16 <<< arr[12]: 2 <<< (2,2,2) <<< i: 2 (2,2) <<< i: 3 (40,-10) <<< l: 9 r: 9 <<< arr[9]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,20,30,40,2,2,2,2,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 20, 30, 40, 2, 2, 2, 2, 2, -10, -20] main <<< result: 40 <<< len: 18 <<< l: 0 r: 17 <<< arr[8]: 20 <<< l: 9 r: 17 <<< arr[13]: 2 <<< (2,2,2) <<< i: 2 (2,2) <<< i: 3 (40,-10) <<< l: 9 r: 10 <<< arr[9]: 30 <<< l: 10 r: 10 <<< arr[10]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,20,20,30,40,2,2,2,2,2,-10,-20 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 20, 20, 30, 40, 2, 2, 2, 2, 2, -10, -20] main <<< result: 40 <<< len: 19 <<< l: 0 r: 18 <<< arr[9]: 20 <<< l: 10 r: 18 <<< arr[14]: 2 <<< (2,2,2) <<< i: 2 (2,2) <<< i: 3 (40,-10) <<< l: 10 r: 11 <<< arr[10]: 30 <<< l: 11 r: 11 <<< arr[11]: 40 main <<< result: 40 -20,-10,2,10,20,20,20,20,20,20,30,40,2,2,2,2,2,-10,-20,-25 main <<< arr: [-20, -10, 2, 10, 20, 20, 20, 20, 20, 20, 30, 40, 2, 2, 2, 2, 2, -10, -20, -25] main <<< result: 40 <<< len: 20 <<< l: 0 r: 19 <<< arr[9]: 20 <<< l: 10 r: 19 <<< arr[14]: 2 <<< (2,2,2) <<< i: 2 (2,2) <<< i: 3 (40,-10) <<< l: 10 r: 11 <<< arr[10]: 30 <<< l: 11 r: 11 <<< arr[11]: 40 main <<< result: 40 -9,17,-1 main <<< arr: [-9, 17, -1] main <<< result: 17 <<< len: 3 <<< l: 0 r: 2 <<< arr[1]: 17 main <<< result: 17 -9,17 main <<< arr: [-9, 17] main <<< result: -2147483648 main <<< result: -2147483648
Since we do not have a third party writing test cases which we can rely on to verify the validity of our solution, I generated multiple variations of a sequence of integers when the problem was being discussed. Note that at the time we never attempted to generate code.
In order to process the input line of integers, generate an int[] array, call the function of interest and display the result, we need to generate a test scaffold.
Each test case in the screen capture is separated from the next by two blank lines.
It seems that our test code reads the input line and populates an int[] array. The contents of the array are displayed to verify that all is well so far.
Our test scaffold seems to call an implementation of the function of interest and display the result. By inspection the results of all test cases seem to be correct.
It appears that our test code calls a different implementation of the function of interest. A set of values are displayed which should help us follow the logic of our algorithm. When all is said and done the result for the second implementation is displayed.
Note that the first two examples dela with arrays in which the values do not repeat next to each other.
The rest of the test cases repeat contiguous values. We will discuss why such conditions will create problems in our initial second implementation. The test cases run the brute force implementation followed by the one that addresses consecutive duplicate values. Please feel free to run the optimized implementation that does not support duplicate consecutive values with the rest of the test cases to better understand why the approach fails.
/**
* 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[] arr ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** call function of interest and display result ****
System.out.println("main <<< result: " + findHigh0(arr));
// **** call function of interest and display result ****
System.out.println("main <<< result: " + findHigh(arr));
}
Our test code is quite simple. We read the line with the integer values and populate the int[] `arr`. The contents of the `arr` are displayed to make sure all is well before calling an implementation of the function of interest. The result is displayed. A second implementation is called and the associated result is displayed.
/**
* We are given an array of integers with values in ascending but not contiguos order,
* followed by descending values also not in continuous order.
* A single high value is guaranteed.
*
* Brute force approach.
*
* Execution: O(n) - Space: O(1)
*/
static public int findHigh0(int[] arr) {
// **** traverse array looking for max val - O(n) ****
for (int i = 0; i < arr.length; i++) {
// **** check for i in range - O(n) ****
if ((i > 0 && i < arr.length - 1) &&
// **** check previous against current against next ****
(arr[i - 1] < arr[i] && arr[i] > arr[i + 1])) {
// **** this value meets condition ****
return arr[i];
}
}
// **** did not find a high value ****
return Integer.MIN_VALUE;
}
This implementation represents the brute force approach. Note that it works for the initial and the enhanced problem. The code is short and simple, but the execution is O(n), which is not bad in most problems, but as you can figure out, the problem calls for a more efficient implementation.
The idea is to traverse the int[] `arr` checking if the current entry in the array is larger than the previous and smaller than the next. If such conditions are met, we have found the high value and our function returns it.
If the loop ends because we did not find a high value, we return MIN_VALUE to indicate a problem. We should have thrown an exception, but as I was developing the code, I set for starters the returned value to be MIN_VALUE.
/**
* We are given an array of integers with values in ascending but not contiguos order,
* followed by descending values also not in continuous order.
* A single high value is guaranteed.
*
* Binary search approach
*
* Execution: O(log(n)) - Space: O(1)
*/
static public int findHigh1(int[] arr) {
// **** sanity check(s) ****
if (arr.length < 3) return Integer.MIN_VALUE;
// **** initialization ****
int len = arr.length;
int l = 0;
int r = len - 1;
// **** binary search ****
while (l <= r) {
// ???? ????
System.out.println("<<< l: " + l + " r: " + r);
// **** compute mid point ****
int mid = l + (r - l) / 2;
// ???? ????
System.out.println("<<< arr[" + mid + "]: " + arr[mid]);
// **** check for high element ****
if ((mid > 0 && mid < len - 1) &&
(arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]))
return arr[mid];
// **** go left ****
if (arr[mid - 1] > arr[mid])
r = mid - 1;
// **** go right ****
else
l = mid + 1;
}
// **** high value NOT found ****
return Integer.MIN_VALUE;
}
This implementation uses the standard binary search algorithm that we have used in many posts in this blog. For performance reasons I like the iterative over the recursive approach.
We start by performing some sanity check(s). We then initialize variables. The `l` index flags the left side of the current window, and the `r` index keeps track of the right side of the window.
We then enter the main loop. We compute the midpoint in the current window and check for the high value in the array. If we find it we return with it.
Otherwise; we check if we go left on the window by moving the right index, or right by moving the left index.
Given the requirements, we know there is a unique high value so our algorithm should find it.
If we get past the while loop, then we have a problem with the data or our code. In this case we return a value to flag the issue. As I mentioned before in this post, instead we should throw an exception.
Note that this is an O(n log(n)) time algorithm.
/**
* We are given an array of integers with values in ascending but not contiguos order,
* followed by descending values also not in continuous order.
* A single high value is guaranteed.
*
* Some values in the int[] arr repeated.
*
* Binary search approach
*
* Execution: O(log(n) * k) - Space: O(1)
*/
static public int findHigh(int[] arr) {
// **** sanity check(s) ****
if (arr.length < 3) return Integer.MIN_VALUE;
// **** initialization ****
int len = arr.length;
int l = 0;
int r = len - 1;
// ???? ????
System.out.println("<<< len: " + len);
// **** binary search - O(log(n) + k)****
while (l <= r) {
// ???? ????
System.out.println("<<< l: " + l + " r: " + r);
// **** compute mid ****
int mid = l + (r - l) / 2;
// ???? ????
System.out.println("<<< arr[" + mid + "]: " + arr[mid]);
// **** check for high element ****
if ((mid > 0 && mid < len - 1) &&
(arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]))
return arr[mid];
// **** go left ****
if (arr[mid - 1] > arr[mid]) {
r = mid - 1;
}
// **** go right ****
else if (arr[mid] < arr[mid + 1] ) {
l = mid + 1;
}
// **** determine which direction to go - O(k) ****
else {
// ???? ????
System.out.println("<<< (" + arr[mid - 1] + "," + arr[mid] + "," + arr[mid + 1] + ")");
// **** expand check left and right ****
for (int i = 2; mid - i > 0 && mid + i < len; i++) {
// ???? ????
System.out.println("<<< i: " + i + " (" + arr[mid - i] + "," + arr[mid + i] + ")");
// **** go left ****
if (arr[mid - i] > arr[mid]) {
r = mid - i;
break;
}
// *** go right ****
else if (arr[mid] > arr[mid + i]) {
l = mid + i;
break;
}
}
}
}
// **** high value NOT found ****
return Integer.MIN_VALUE;
}
In this implementation we will attempt to take care of the condition of encountering consecutive duplicate values in the int[] `arr`.
All seems to be the same until after we check for the high element. This is the section that we need to determine if we go left or right in our binary search. We need to take care of the condition where three consecutive entries share the same value.
We do so by expanding the check for the same conditions but using an expanding window based on the midpoint.
If a high value is not found, we return the MIN_VALUE to indicate we encounter a logic or a data issue.
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 / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John