Good morning. Hope your day has started on the right note. If you follow this blog you have noticed that I recommend social distancing in order to reduce the chances of COVID-19 to spread in your local community. My wife and I wear a mask when we go shopping. As soon as we return to our vehicle we remove the mask and apply had sanitizer to our hands. We are planning to continue this behavior for the foreseeable future.
My wife has been to the Mall of America a couple times during the pandemic. She and a friend have not been shopping but walking. On each occasion my wife told me that the mall was almost empty with many stores closed. That is a shame.
Moving forward, it seems that COVID-19 vaccines are being administered to more and more people in our country and all over the world. At this time it seems that one from Pfizer is the most recommended and safe of the ones available.
Over the weekend I read an article that in Israel a large percentage of the population has been vaccinated. The government has lifted most of the restrictions that were imposed to prevent the spread of the COVID-19 virus. Due to the change back to a new normal, people started going out to bars and restaurants at what seemed to full capacity. A person in the article mentioned that she was in a restaurant in an indoors setting with friends, having a meal and drinks for over three hours. I hope nothing happens to her and friends as a result in the next couple weeks. BTW she and her friends had already been vaccinated.
Back at home, on Saturday which was the warmest day of the year so far (we reached the low 60s F) my wife and I stopped by the Eagan Premium Outlets. I could not believe my eyes. The parking lots and ramp were pretty much full like it was a normal summer day (we are still in winter). You could see shoppers all over the grounds. They all seemed to be wearing masks.
After picking us some items at a store, we got back in the car and headed to the Mall of America. The parking ramp were we usually park was relatively full. No problem finding an open spot to park. We entered the MOA through an anchor retailer. The store seemed to have a regular weekend crowd. My wife was looking to replenish her supply of body creams and perfumes. She could not find the ones she was looking for, so the very pleasant attendant ordered them for home delivery. We were there less than half hour. When done we headed home, called our kids, and grilled some steaks. After all it was, so far, the warmest day this year.
I decided to give a try to the newest (the ones with the largest numbers) LeetCode problems. Will see how it goes. I selected LeetCode 1793 Maximum Score of a Good Subarray. This problem was in the Greedy algorithm category. The key in a Greedy algorithm is to make locally optimal choices at each step. With this in mind let’s take a look at the requirements for the problem.
You are given an array of integers nums (0-indexed) and an integer k. The score of a subarray (i, j) is defined as: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A "good" subarray is a subarray where i <= k <= j. Return the maximum possible score of a good subarray. Constraints: o 1 <= nums.length <= 105 o 1 <= nums[i] <= 2 * 104 o 0 <= k < nums.length
It seems to me that the text for a problem may change with time. If interested in the problem, I recommend for you to visit the LeetCode page and get the current version of the problem description.
Not sure how popular the definition of “good” sub array might be, but there it is. I had to read the problem a few times and experiment with the two sample cases in order to be clear on what was expected.
Hints: o Greddy o Try thinking about the prefix before index k and the suffix after index k as two separate arrays. o Using two pointers or binary search, we can find the maximum prefix of each array where the numbers are less than or equal to a certain value.
In addition to the problem classification (Greedy) LeetCode provided two hints which would represent what you may expect in a well conducted interview. Most times I read one hint at a time, but in this case I was short in time so I decided to take the two hints at once. The hints were quite useful while attempting to get a start on an algorithm to solve the problem using pen and paper.
More on this while we take a look at the test scaffold that I wrote. I prefer to solve the problems on my own computer and then paste the solution to be evaluated on the LeetCode site. The simplest way is to solve the problem directly on the on-line IDE provided by LeetCode.
We will use the Java programming language and the VSCode IDE on a Windows 10 computer.
public int maximumScore(int[] nums, int k) {
}
The signature for the method in question seems reasonable. We are provided an array of integers and an index in the array from which we need to determine the “good” array by extending the left and right bounds from the index specified by k. Putted this way we can start to figure out how the Greedy algorithm might be used.
1,4,3,7,4,5 3 main <<< nums: [1, 4, 3, 7, 4, 5] main <<< k: 3 <<< maxScore: 7 (3,3) <<< maxScore: 8 (3,4) <<< maxScore: 12 (3,5) <<< maxScore: 12 (2,5) <<< maxScore: 15 (1,5) <<< maxScore: 15 (0,5) main <<< score: 15 5,5,4,5,4,1,1,1 0 main <<< nums: [5, 5, 4, 5, 4, 1, 1, 1] main <<< k: 0 <<< maxScore: 5 (0,0) <<< maxScore: 10 (0,1) <<< maxScore: 12 (0,2) <<< maxScore: 16 (0,3) <<< maxScore: 20 (0,4) <<< maxScore: 20 (0,5) <<< maxScore: 20 (0,6) <<< maxScore: 20 (0,7) main <<< score: 20 6569,9667,3148,7698,1622,2194,793,9041,1670,1872 5 main <<< nums: [6569, 9667, 3148, 7698, 1622, 2194, 793, 9041, 1670, 1872] main <<< k: 5 <<< maxScore: 2194 (5,5) <<< maxScore: 3244 (4,5) <<< maxScore: 4866 (3,5) <<< maxScore: 6488 (2,5) <<< maxScore: 8110 (1,5) <<< maxScore: 9732 (0,5) <<< maxScore: 9732 (0,6) <<< maxScore: 9732 (0,7) <<< maxScore: 9732 (0,8) <<< maxScore: 9732 (0,9) main <<< score: 9732
This screen capture shows our test scaffold in action. The first two examples are the ones provided by LeetCode. The rest also come from LeetCode because I made mistakes. Most of them were from copying the wrong pieces of code from my solution. Some were my mistakes.
Our code reads the line of integers and the value for k. The array holding the integers and variable k are displayed to make sure all is well so far.
The maxScore is an artifact of our solution. We will cover it when we look at the code for the method in question. At this time let’s take the hints and figure out what we want to do.
input array: [1,4,3,7,4,5]
indices: 0 1 2 3 4 5
k: 3
scores array: [1,3,3,7,4,4]
k: 3
In the input array we are told to start with element at index 3 which maps to value 7. From then on we need to take into account what we need to maximize which is the product of two values. The values are a combination of the contents of the scores array and the indices for the span of the array.
If we go back and look at the values of the maxScore followed by the two values which represent the left and right index into the scores array we can observe that for the first pass we are looking at an array that starts with k and has a single element which is 7. Since we get a larger value when including the element to the right we get a value of 8 and our array has expanded to [3:4]. We then look to expand our array to include [3:5] and our max value is now 12. At that point we have to look to the left since we have no more entries to the right.
We expand our array to [2:5] and the value remains at 12. We repeat a couple more times and when we with an array [1:5] our max score is 15. If you look at the example in the LeetCode web site, we have found the expected answer.
At this time I would suggest to get a piece of paper and a pen and go through this and the next test cases. Note that in the second test case k == 0 so we cannot grow our array left, we can only go right. In that example we read our max value when the array is in the range [0:4] which matches the expected value. I will wait for you to experiment with paper and pen…
…OK you are back. Let’s move forward.
/**
* Test scaffold.
*
* !!!! NOT PART OF SOLUTION !!!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and create int[] array ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read k ****
int k = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
System.out.println("main <<< k: " + k);
// **** get the maximum possible score of a good subarray ****
int maxScore = maximumScore(nums, k);
// ???? ????
System.out.println("main <<< score: " + maxScore);
}
This is going to be our test scaffold. Note that if you develop the code using the IDE in the LeetCode site, you do not need to build a test scaffold.
The code is simple. We read the input values and populate the nums int[] array and the variable k. We display the values to make sure all is well so far. We then make a call to the method of interest. The result is displayed.
/**
* Return the maximum possible score of a good subarray.
*
* Runtime: 5 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 53.4 MB, less than 100.00% of Java online submissions.
*
* Execution time: O(n)
* Space: O(n)
*/
static int maximumScore(int[] nums, int k) {
// **** initialization ****
int len = nums.length;
// **** generate and populate the scores array ****
int[] scores = new int[len];
scores[k] = nums[k];
// **** go left - O(n) ****
for (int i = k - 1; i >= 0; i--)
scores[i] = nums[i] < scores[i + 1] ? nums[i] : scores[i + 1];
// **** go right - O(n) ****
for (int i = k + 1; i < len; i++)
scores[i] = nums[i] < scores[i - 1] ? nums[i] : scores[i - 1];
// **** loop looking for the maximum score (greedy) - O(n) ****
int maxScore = -1;
int left = k;
int right = k;
while (true) {
// **** compute current score ****
int currentScore = (scores[left] < scores[right]) ? scores[left] : scores[right];
// **** determine if we found a better score ****
maxScore = (maxScore > (right - left + 1) * currentScore) ? maxScore : (right - left + 1) * currentScore;
// ???? ????
System.out.println("<<< maxScore: " + maxScore + " (" + left + "," + right + ")");
// **** check if done with the loop ****
if (left == 0 && right == len - 1)
break;
// **** determine direction to grow subarray ****
if (left == 0)
right++; // must go right
else if (right == len - 1)
left--; // must go left
else if (scores[left - 1] > scores[right + 1])
left--; // go left
else
right++; // go right
}
// **** return max score ****
return maxScore;
}
We start by performing the initialization steps. We need to declare and populate the scores array as we did on paper. We do so by populating the value at index k. We then move to the left and when done to the right of k. At some point I was displaying the scores array but I removed that line. I believe that it is an important step to make sure the scores array is as expected. Note that populating the scores array take O(n) time.
Now we need to loop and include the next element in the array going right or left based on the best results (greedy algorithm). We compute the current score. We then check if this is a maximum score at the time.
We then decide if we are done because there is no place to move left or right in the scores array. If we are not done, we have to decide in which way to move.
Note that we first need to check that we are not going over the physical scores array bounds. The decision in which direction to move is then made by the next left and right values.
The loop continues until all elements in the scores array have been visited. The maximum score is then returned.
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, or if you would like for me to help out 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. 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