Hope you are doing well on this Friday. This morning my wife and I woke up with outside temperatures in the low 40’s F. I closed the window in the kitchen, set the thermostats to 68 F and started the furnace. This was the first time this season. The furnace ran for a few minutes heating downstairs. The rest of the day we warmed up with the oven and the sun that shined on and off. Beside next Monday and Tuesday that the high temperature will be in the low 70’s F, the high temperatures will be in the low 50’s and 60’s.
My wife woke up not feeling well. It seems that something she ate yesterday did not go well with her. As far as we can tell, both had the same meals. I am feeling well as usual. We were planning on getting a few grocery items this afternoon. We decided to go tomorrow instead.
This morning we spoke with our younger son. It seems that the plans for them visiting us next week have been scrapped. Hopefully we will have an opportunity in the near future to get together.
Spoke with my best friend earlier today. He got back home last Sunday. He was visiting her daughter in Canada. All is well with his family. His wife will be spending a couple more weeks and will return home after her daughter’s birthday. He had to get back earlier this week due to his work schedule.
Earlier this morning I selected LeetCode 410 Split Array Largest Sum which is rated Hard.
Given an array `nums` which consists of non-negative integers and an integer `m`, you can split the array into `m` `non-empty` `continuous` subarrays. Write an algorithm to `minimize` the `largest sum` among these `m` subarrays. Constraints: o 1 <= nums.length <= 1000 o 0 <= nums[i] <= 106 o 1 <= m <= min(50, nums.length) Related Topics: o Array o Binary Search o Dynamic Programming o Greedy
This problem is quite similar to Divide Chocolate. If you are interested in this problem I would suggest you to read the previous post before attempting to solve this one.
We are given an array of integers and an integer `m`. We are supposed to split the array into `m` sub arrays. The caveat is that we need to minimize the largest sum among the `m` sub arrays.
Take a look at the Related Topics. We have binary search and Greedy. Let’s see if we can use a similar approach to solve this problem.
We will be solving this problem using Java and the VSCode IDE on a Windows computer. We will not use the IDE provided by LeetCode. Due to this, we will have to write a simple test scaffold which will NOT BE PART OF THE SOLUTION.
public int splitArray(int[] nums, int m) {
}
The signature of the function in question is similar to the previous post. We are provided with an array of integers and a number. So far it seems that we might be used a similar approach to the one we used last.
7,2,5,10,8 2 main <<< nums: [7, 2, 5, 10, 8] main <<< m: 2 splitArray <<< lo: 10 hi: 32 splitArray <<< mid: 21 split <<< num: 7 split <<< num: 2 split <<< num: 5 split <<< num: 10 split <<< num: 8 splitArray <<< pieces: 2 splitArray <<< lo: 10 hi: 21 splitArray <<< mid: 15 split <<< num: 7 split <<< num: 2 split <<< num: 5 split <<< num: 10 split <<< num: 8 splitArray <<< pieces: 3 splitArray <<< lo: 16 hi: 21 splitArray <<< mid: 18 split <<< num: 7 split <<< num: 2 split <<< num: 5 split <<< num: 10 split <<< num: 8 splitArray <<< pieces: 2 splitArray <<< lo: 16 hi: 18 splitArray <<< mid: 17 split <<< num: 7 split <<< num: 2 split <<< num: 5 split <<< num: 10 split <<< num: 8 splitArray <<< pieces: 3 splitArray <<< lo: 18 hi: 18 main <<< Output: 18 1,2,3,4,5 2 main <<< nums: [1, 2, 3, 4, 5] main <<< m: 2 splitArray <<< lo: 5 hi: 15 splitArray <<< mid: 10 split <<< num: 1 split <<< num: 2 split <<< num: 3 split <<< num: 4 split <<< num: 5 splitArray <<< pieces: 2 splitArray <<< lo: 5 hi: 10 splitArray <<< mid: 7 split <<< num: 1 split <<< num: 2 split <<< num: 3 split <<< num: 4 split <<< num: 5 splitArray <<< pieces: 3 splitArray <<< lo: 8 hi: 10 splitArray <<< mid: 9 split <<< num: 1 split <<< num: 2 split <<< num: 3 split <<< num: 4 split <<< num: 5 splitArray <<< pieces: 2 splitArray <<< lo: 8 hi: 9 splitArray <<< mid: 8 split <<< num: 1 split <<< num: 2 split <<< num: 3 split <<< num: 4 split <<< num: 5 splitArray <<< pieces: 3 splitArray <<< lo: 9 hi: 9 main <<< Output: 9 1,4,4 3 main <<< nums: [1, 4, 4] main <<< m: 3 splitArray <<< lo: 4 hi: 9 splitArray <<< mid: 6 split <<< num: 1 split <<< num: 4 split <<< num: 4 splitArray <<< pieces: 2 splitArray <<< lo: 4 hi: 6 splitArray <<< mid: 5 split <<< num: 1 split <<< num: 4 split <<< num: 4 splitArray <<< pieces: 2 splitArray <<< lo: 4 hi: 5 splitArray <<< mid: 4 split <<< num: 1 split <<< num: 4 split <<< num: 4 splitArray <<< pieces: 3 splitArray <<< lo: 4 hi: 4 main <<< Output: 4
We are provided with two input lines. The first holds the values for the array. The second holds the number of times we need to split the array.
Our test scaffold seems to read the two input lines, display the values to make sure they match the input, call the function of interest which seems to display several messages, and then returns the output which is displayed by the test scaffold.
The messages displayed by the function of interest and an auxiliary function are NOT PART OF THE SOLUTION. They are there to help us understand the algorithm. I commented out the messages before submitting the code for evaluation.
/**
* 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[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read m ****
int m = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
System.out.println("main <<< m: " + m);
// **** call function of interest and display result ****
System.out.println("main <<< Output: " + splitArray(nums, m));
}
Not much to add to the description of our test scaffold which IS NOT PART OF THE SOLUTION. LeetCode provides a test scaffold with 30 test cases.
/**
* Write an algorithm to `minimize` the `largest sum`
* among these `m` subarrays.
* Modified binary search using Greedy algorithm.
* Execution: O(n * log(m)) - Space: O(1)
*
* With streams:
* 30 / 30 test cases passed.
* Status: Accepted
* Runtime: 8 ms
* Memory Usage: 38.6 MB
*
* Without streams:
* 30 / 30 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.7 MB
*/
public static int splitArray(int[] nums, int m) {
// **** initialization (using streams) ****
// int lo = IntStream.range(0, nums.length)
// .map(i -> nums[i])
// .max()
// .getAsInt();
// int hi = IntStream.range(0, nums.length)
// .map(i -> nums[i])
// .sum();
// **** initialization (NOT using streams) ****
int lo = 0;
int hi = 0;
for (int num : nums) {
if (num > lo) lo = num;
hi += num;
}
// ???? ????
System.out.println("splitArray <<< lo: " + lo + " hi: " + hi);
// **** binary search - O(log(m)) ****
while (lo < hi) {
// **** compute mid ****
int mid = lo + (hi - lo) / 2;
// ???? ????
System.out.println("splitArray <<< mid: " + mid);
// **** greedy approach - O(n) ****
int pieces = split(nums, mid);
// ???? ????
System.out.println("splitArray <<< pieces: " + pieces);
// **** ****
if (pieces > m) lo = mid + 1;
else hi = mid;
// ???? ????
System.out.println("splitArray <<< lo: " + lo + " hi: " + hi);
}
// **** either `hi` or `lo` will do since lo == hi ****
return lo;
}
Our approach will be to use a modified binary search algorithm and an auxiliary function which will implement the Greedy algorithm. It looks quite similar to the previous problem.
We start by initializing a couple variables. These variables will be used as limits to split the input array in our modified binary search.
Note that for my first pass I went with streams. After submitting the solution the timing was not as good as desired. Given that streams are compact to program, their performance seems to be lacking when compared to other methods. I commented out the use of streams and implemented equivalent code using a loop. The runtime changed from 8 to 0 milliseconds. I guess streams perform better when processing large amounts of data.
We now enter a loop in which we compare the `lo` with the `hi` values. This seems to be standard when implementing the binary search algorithm.
The first thing is to compute the `mid` value. Note that we are dealing with the sums of sub arrays and not positions in the `nums` array.
At this point in a binary search we need to determine if we continue searching in the left or the right side array of the sub array. Now we will use an auxiliary function that determines using the Greedy algorithm if we go right or left. This is done using the number of `pieces` when compared to `m`.
When we exit the while loop, we return the sum of the elements in the sub array we carved in the modified binary search.
/**
* Greedy algorithm
* Execution: O(n)
*/
private static int split(int[] nums, int largestSum) {
// **** initialization ****
int pieces = 1;
int sum = 0;
// **** traverse nums[] - O(n) ****
for (int num : nums) {
// ???? ????
System.out.println("split <<< num: " + num);
// **** split array (if needed) ****
if (sum + num > largestSum) {
sum = num;
pieces++;
} else sum += num;
}
// **** return number of pieces ****
return pieces;
}
This function implements the Greedy algorithm. After the initialization step, we traverse the contents of the `nums` array. The condition to split the array increments the pieces or elements in the array we need to select. Once the loop is completed, the number of pieces is returned. This value is used by the caller to determine if the modified binary search continues to the left or right.
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 web sites (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