Tomorrow is Thanksgiving Day 2020. My wife finished preparing three containers with cheesy potatoes casserole. She has been making this dish as far as I can remember. Due to the ingredients we tend to have it once or twice a day. I will provide the recipe and some pictures on tomorrows post. If I am not able to solve a problem and generate a post, will generate a post as soon as possible.
We are still in the midst of the COVID-19 pandemic. About two million people around the world have die of complications related to the novel coronavirus. My wife and I have some friends’ originally from Vietnam. We learned today that one of them is in the hospital and the other barely making it at home. One of my wife’s brothers has been diagnosed with COVID-19. He, his wife and two kids are in quarantine at home. Our best wishes and our thoughts go out to them for a quick and safe recovery.
Earlier today I decided to give LeetCode problem 523 Continuous Subarray Sum a try. In my opinion this is a good problem to solve. Sometime ago know I had to use a similar approach to solve a different problem. I was not able to locate the post or the associated code. Sorry about that.
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer. Constraints: o The length of the array won't exceed 10,000. o You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
We are given a set of integers and a target integer ‘k’. The idea is to find if we have a sub array of at least two contiguous integers which is a multiple of ‘k’. If interested take a look at the problem description and samples in the LeetCode web site.
I decided to use Java and the Visual Studio Code IDE on a Windows 10 machine. I like to work on a computer with a large 4K monitor.
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
}
}
We will get an array of integers and the ‘k’ value. As you know I like to solve the problems on my machine using the tools I have installed. Due to this fact, I also have to write a test scaffolding. Note that the test scaffolding is not part of the solution.
23,2,4,6,7
6
main <<< nums: [23, 2, 4, 6, 7]
main <<< k: 6
checkSubarraySum <<< sums: [5, 0, 0, 0, 0]
checkSubarraySum <<< i: 0 sum: 23
checkSubarraySum <<< i: 0 sum: 5
checkSubarraySum <<< hm: {0=-1, 5=0}
checkSubarraySum <<< sums: [5, 1, 0, 0, 0]
checkSubarraySum <<< i: 1 sum: 7
checkSubarraySum <<< i: 1 sum: 1
checkSubarraySum <<< hm: {0=-1, 1=1, 5=0}
checkSubarraySum <<< sums: [5, 1, 5, 0, 0]
checkSubarraySum <<< i: 2 sum: 5
checkSubarraySum <<< i: 2 sum: 5
checkSubarraySum <<< sum: 5
checkSubarraySum <<< sums[i]: 5
main <<< checkSubarraySum: true
23,2,6,4,7
6
main <<< nums: [23, 2, 6, 4, 7]
main <<< k: 6
checkSubarraySum <<< sums: [5, 0, 0, 0, 0]
checkSubarraySum <<< i: 0 sum: 23
checkSubarraySum <<< i: 0 sum: 5
checkSubarraySum <<< hm: {0=-1, 5=0}
checkSubarraySum <<< sums: [5, 1, 0, 0, 0]
checkSubarraySum <<< i: 1 sum: 7
checkSubarraySum <<< i: 1 sum: 1
checkSubarraySum <<< hm: {0=-1, 1=1, 5=0}
checkSubarraySum <<< sums: [5, 1, 1, 0, 0]
checkSubarraySum <<< i: 2 sum: 7
checkSubarraySum <<< i: 2 sum: 1
checkSubarraySum <<< sum: 1
checkSubarraySum <<< sums[i]: 1
checkSubarraySum <<< hm: {0=-1, 1=1, 5=0}
checkSubarraySum <<< sums: [5, 1, 1, 5, 0]
checkSubarraySum <<< i: 3 sum: 5
checkSubarraySum <<< i: 3 sum: 5
checkSubarraySum <<< sum: 5
checkSubarraySum <<< sums[i]: 5
main <<< checkSubarraySum: true
23,2,6,4,7
9
main <<< nums: [23, 2, 6, 4, 7]
main <<< k: 9
checkSubarraySum <<< sums: [5, 0, 0, 0, 0]
checkSubarraySum <<< i: 0 sum: 23
checkSubarraySum <<< i: 0 sum: 5
checkSubarraySum <<< hm: {0=-1, 5=0}
checkSubarraySum <<< sums: [5, 7, 0, 0, 0]
checkSubarraySum <<< i: 1 sum: 7
checkSubarraySum <<< i: 1 sum: 7
checkSubarraySum <<< hm: {0=-1, 5=0, 7=1}
checkSubarraySum <<< sums: [5, 7, 4, 0, 0]
checkSubarraySum <<< i: 2 sum: 13
checkSubarraySum <<< i: 2 sum: 4
checkSubarraySum <<< hm: {0=-1, 4=2, 5=0, 7=1}
checkSubarraySum <<< sums: [5, 7, 4, 8, 0]
checkSubarraySum <<< i: 3 sum: 8
checkSubarraySum <<< i: 3 sum: 8
checkSubarraySum <<< hm: {0=-1, 4=2, 5=0, 7=1, 8=3}
checkSubarraySum <<< sums: [5, 7, 4, 8, 6]
checkSubarraySum <<< i: 4 sum: 15
checkSubarraySum <<< i: 4 sum: 6
checkSubarraySum <<< hm: {0=-1, 4=2, 5=0, 6=4, 7=1, 8=3}
main <<< checkSubarraySum: false
23,2,6,4,7
0
main <<< nums: [23, 2, 6, 4, 7]
main <<< k: 0
checkSubarraySum <<< sums: [23, 0, 0, 0, 0]
checkSubarraySum <<< i: 0 sum: 23
checkSubarraySum <<< i: 0 sum: 23
checkSubarraySum <<< hm: {0=-1, 23=0}
checkSubarraySum <<< sums: [23, 25, 0, 0, 0]
checkSubarraySum <<< i: 1 sum: 25
checkSubarraySum <<< i: 1 sum: 25
checkSubarraySum <<< hm: {0=-1, 23=0, 25=1}
checkSubarraySum <<< sums: [23, 25, 31, 0, 0]
checkSubarraySum <<< i: 2 sum: 31
checkSubarraySum <<< i: 2 sum: 31
checkSubarraySum <<< hm: {0=-1, 23=0, 25=1, 31=2}
checkSubarraySum <<< sums: [23, 25, 31, 35, 0]
checkSubarraySum <<< i: 3 sum: 35
checkSubarraySum <<< i: 3 sum: 35
checkSubarraySum <<< hm: {0=-1, 35=3, 23=0, 25=1, 31=2}
checkSubarraySum <<< sums: [23, 25, 31, 35, 42]
checkSubarraySum <<< i: 4 sum: 42
checkSubarraySum <<< i: 4 sum: 42
checkSubarraySum <<< hm: {0=-1, 35=3, 23=0, 25=1, 42=4, 31=2}
main <<< checkSubarraySum: false
0,0
0
main <<< nums: [0, 0]
main <<< k: 0
checkSubarraySum <<< sums: [0, 0]
checkSubarraySum <<< i: 0 sum: 0
checkSubarraySum <<< i: 0 sum: 0
checkSubarraySum <<< sum: 0
checkSubarraySum <<< sums[i]: 0
checkSubarraySum <<< hm: {0=-1}
checkSubarraySum <<< sums: [0, 0]
checkSubarraySum <<< i: 1 sum: 0
checkSubarraySum <<< i: 1 sum: 0
checkSubarraySum <<< sum: 0
checkSubarraySum <<< sums[i]: 0
main <<< checkSubarraySum: true
It seems that we are given a set of integers and the ‘k’ value in a consecutive line. Our test scaffolding seems to read the data and generate the two arguments to call the checkSubarraySum() method.
The method in questions seems to display several messages. I decided to leave the messages enabled. I had to comment them out when I submitted the code for evaluation.
The final line seems to return the answer. The first and second examples are the ones provided by LeetCode on the requirements page. The others came about when submitting code that failed.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// **** read array contents ****
String[] strs = reader.readLine().trim().split(",");
// **** read k ****
int k = Integer.parseInt(reader.readLine().trim());
// **** close reader ****
reader.close();
// **** create and populate array of numbers ****
int[] nums = new int[strs.length];
for (int i = 0; i < strs.length; i++) {
nums[i] = Integer.parseInt(strs[i]);
}
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
System.out.println("main <<< k: " + k);
// **** check for sub array and display result ****
System.out.println("main <<< checkSubarraySum: " + checkSubarraySum(nums, k));
}
As expected we read the two lines of data. We generate the array and extract the binary value for ‘k’ from the second line. As usual we display the arguments to make sure all is well. We then call the method we need to implement and display the returned value.
The code was accepted by LeetCode. It has O(n) complexity.
/**
* Runtime: 2 ms, faster than 99.42% of Java online submissions.
* Memory Usage: 39.2 MB, less than 99.38% of Java online submissions.
*/
static boolean checkSubarraySum(int[] nums, int k) {
// **** initialization ****
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
hm.put(0, -1);
int sum = 0;
// ???? ????
int[] sums = new int[nums.length];
// **** loop computing sums [0, n - 1] ****
for (int i = 0; i < nums.length; i++) {
// ???? update running sum ????
sums[i] = nums[i];
if (i > 0)
sums[i] += sums[i - 1];
if (k != 0)
sums[i] %= k;
// ???? ????
System.out.println("checkSubarraySum <<< sums: " + Arrays.toString(sums));
// **** update sum ****
sum += nums[i];
// ???? ????
System.out.println( "checkSubarraySum <<< i: " + i + " sum: " + sum);
// **** remainder ****
if (k != 0) {
sum %= k;
}
// ???? ????
System.out.println( "checkSubarraySum <<< i: " + i + " sum: " + sum);
// **** check if we have this sum ****
if (hm.containsKey(sum)) {
// ???? ????
System.out.println("checkSubarraySum <<< sum: " + sum);
System.out.println("checkSubarraySum <<< sums[i]: " + sums[i]);
// **** the sum is larger than 1; sub array was found ****
if (i - hm.get(sum) > 1) {
return true;
}
}
// **** add this sum to the hash map ****
hm.putIfAbsent(sum, i);
// ???? ????
System.out.println("checkSubarraySum <<< hm: " + hm.toString());
}
// **** sub array not found ****
return false;
}
You might want to remove all the debugging and testing code to make it simpler to follow. I left it enables because the output will allow us to follow what is happening.
At the code of the problem is the mechanism that we need to use to track the different sub arrays. Note that we can have up to 10,000 integers in the array. If we try all possibilities with 2, 3, …, 9999 elements, it might take a very long time to execute. This would be the brute force approach which we will skip.
Take a look at the following array:
array: 2, 5, 9, 11, 13
index: 0 1 2 3 4
| Subarray | Sum |
| (0, 0) | 2 |
| (0, 1) | 7 |
| (0, 2) | 16 |
| (0, 3) | 27 |
| (0, 4) | 40 |
The sum of the sub array from 0 to 0 or (0, 0) is 2. The sum for (0, 1) is 7, and so forth. Within this example we could compute the following:
(2, 3) = (0, 3) – (0, 1) = 27 – 7 = 20 = 9 + 11
Since we need to have a multiple of ‘k’ we would have:
((0, a) – (0, b)) % k = 0
(0, a) % k == (0, b) % k
The ‘a’ and ‘b’ would represent incremental sums from left to right. In other words ‘a’ would be less than ‘b’ and both values would match. The positions of ‘a’ and ‘b’ must be at least contiguous and greater than 1.
We start by declaring a hash map to store the sum and the remainder as key and value pairs. We initialize the first sum to 0:-1 to deal with the 0 value. Remove this line of code and try the example with 0 values.
We now enter a loop. In the loop we traverse the array from left to right. On each step we update the sum and get it’s remainder (if possible). We then check if the remainder is in the hash map. If so we make sure that the current position (i) in the array is at least 1 greater that the value associated with the remainder. This is done because the minimum size of the sub array is two contiguous elements. If we would be required three or more consecutive integers, we would have to change the > 1 for a larger value i.e., >2 or > 3. If we do not have the proper value, we insert the current key : value pair and proceed on looping.
If we complete the loop, it indicates that we did not find a proper sub array. We have to return ‘false’.
Make sure you understand what is going on. There are different problems that share similar approaches. Let’s see if I can address one like that in the next post (scheduled for tomorrow Thanksgiving Day).
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. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,603 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
john.canessa@gmail.com