UPDATE UPDATE UPDATE
I wish to correct a statement in this post. I mentioned that my wife and I received ballots for the next presidential election. It turns out that the envelopes contain requests for ballots, not the actual ballots. One way or the other we will vote as usual in person at a assigned polling center on Election Day.
I have been reading a few articles regarding the next presidential elections. Some Democrats do not appear to want to use a voter ID to reduce election fraud. The reasons, which you may find on-line, seem to be somewhat childish to say reject a national voter ID registration and card. They are used in most countries.
Due to the COVID-19 pandemic (thanks China), the brilliant idea (I am being facetious) is to have voters mail in their completed ballots using the secure USPS. In addition you can request a ballot be mailed to you in most (not sure if in all) states. But that is not all, my wife and I live in Minnesota and we have received two (2) unsolicited ballots which we will not use. We will keep them as a souvenir to remember, what I consider, the last nail in the coffin for democracy in the USA.
I am not stating that all people or political parties will commit election fraud. 
But if you read the news, and we are still about a month away from elections day, fraud is happening all over. Fresh ballots are found in bulk, completed ballots which favor of the Republican candidate have been ditched. What prevents me or any other 3,460,663 registered voters in the state of Minnesota to vote once by mail and a second time in person at a voting site on Election Day? And that is only considering Minnesota.
Election fraud has been around in the US for at least five decades. We have never before seen so much fraud prior to Election Day. So what is going to happen Election Day? After the count of fraud ballots is completed, chances are that there are going to be more votes than registered voters. The elections might be dismissed and we will have to wait a few months or year before a mechanism is deployed (i.e., voter ID) to reduce (eliminate would be too much to hope for) fraud.
All of the turmoil to occur (i.e., riots, protests, looting, lack of groceries) will put the USA at a disadvantage to counter the push of China to dominate and enslave the world (including the USA). Who knows, we might have to buy all Chinese products from Chinese companies (bye bye Apple). We will be forced to work 996 (09:00 AM – 09:00 PM 6 days a week).
Please think before you vote. I personally want to maintain our way of life with some few changes to capitalism and democracy.
Sorry for the long introduction in this post, but I am very concerned about the mockery a group of people have made out of our electoral system. I love the USA and our founding values are being threatened by a few local and foreign interests.
I randomly picked up problem 351 from LeetCode named Count Negative Numbers in a Sorted Matrix.
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in grid. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 100 -100 <= grid[i][j] <= 100
In a nutshell we are given a matrix of integer values. The values in each row are ordered from high to low. Some rows may or may not contain negative values. The challenge if you wish to accept it, is to return the total number of negative values in the provided grid.
I might have missed something, so if interested, please read the requirements for this problem in the LeetCode site.
I will solve the problem using the Java programming language, using the VSCode IDE on a Windows 10 machine. In addition, for sake of learning something extra, I like to build my own test scaffolding.
class Solution {
public int countNegatives(int[][] grid) {
}
}
We need to develop the countNegatives() function which will count the number of negative integers in the provided grid.
[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] main <<< m: 4 populateGrid <<< n: 4 main <<< grid: [4, 3, 2, -1] [3, 2, 1, -1] [1, 1, -1, -2] [-1, -1, -2, -3] main <<< countNegatives: 8 main <<< countNegatives1: 8 [[3,2],[1,0]] main <<< m: 2 populateGrid <<< n: 2 main <<< grid: [3, 2] [1, 0] main <<< countNegatives: 0 main <<< countNegatives1: 0 [[1,-1],[-1,-1]] main <<< m: 2 populateGrid <<< n: 2 main <<< grid: [1, -1] [-1, -1] main <<< countNegatives: 3 main <<< countNegatives1: 3 [[-1]] main <<< m: 1 populateGrid <<< n: 1 main <<< grid: [-1] main <<< countNegatives: 1 main <<< countNegatives1: 1
The examples are the ones provided by LeetCode. In a nutshell, we get the values for the grid which we need to proves to create and populate the grid that is passed as an argument to the function we need to develop.
The program displays the number of rows in the grid. The function we use to populate the grid displays the number of columns in the grid. To be honest, I 
was not sure if the rows in the matrix would be of different lengths (sparse matrix). Apparently all the rows are of the same length; at least in these examples.
After we load the grid, we display it to make sure we loaded it properly.
We then call two versions of the solution. The results seem to match. Both were accepted by LeetCode.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read matrix data ****
String[] strs = sc.nextLine().split("\\],\\[");
// **** close scanner ****
sc.close();
// **** extract m ****
int m = strs.length;
// ???? ????
System.out.println("main <<< m: " + m);
// **** loop removing '[' and ']' ****
for (int i = 0; i < m; i++) {
strs[i] = strs[i].replace("[", "");
strs[i] = strs[i].replace("]", "");
}
// **** create and populate grid ****
int[][] grid = populateGrid(m, strs);
// ???? ????
System.out.println("main <<< grid: ");
for (int i = 0; i < m; i++)
System.out.println(Arrays.toString(grid[i]));
// **** count and display count of negative numbers in grid ****
System.out.println("main <<< countNegatives: " + countNegatives(grid));
// **** count and display count of negative numbers in grid ****
System.out.println("main <<< countNegatives1: " + countNegatives1(grid));
}
We need to read the input data, create and load the grid. Then we can call the solution function. This is shown in the source code for the test scaffolding.
/**
* Create and populate grid
*/
static int[][] populateGrid(int m, String[] strs) {
// **** get 'n' ****
String[] ints = strs[0].split(",");
int n = ints.length;
// ???? ????
System.out.println("populateGrid <<< n: " + n);
// **** allocate grid ****
int[][] grid = new int[m][n];
// **** populate grid ****
for (int i = 0; i < m; i++) {
// **** ****
ints = strs[i].split(",");
// **** ****
for (int j = 0; j < grid[i].length; j++)
grid[i][j] = Integer.parseInt(ints[j]);
}
// **** return the grid ****
return grid;
}
This function is part of the test scaffolding and not the solution. We receive an array of strings with the values for each row of the matrix. We allocate the grid. We then enter a loop that is used to populate all the rows in the grid. A second inner loop is used to populate each row of the matrix.
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 39.6 MB, less than 95.07% of Java online submissions.
* Runtime O(n)
*/
static int countNegatives(int[][] grid) {
// **** count of negative numbers ****
int count = 0;
// **** numbers per row ****
int n = grid[0].length;
// **** loop once per array ****
for (int i = 0; i < grid.length; i++) {
// **** locate first negative number ****
int j = 0;
for ( ; j < n && grid[i][j] >= 0; j++);
// **** update count ****
count += (n - j);
}
// **** return count of negative numbers ****
return count;
}
This function implements my first approach to the solution. We start by clearing the count of negative numbers. For ease we assign the number of elements in a row to variable ‘n’. We then enter a loop in which we process a row at a time. For the second inner loop, we want to traverse the row until we find a negative value. At that point we compute the number of negative values left in the current row. Finally we return the total count. In the comment section of the function we have the time it took to process.
I seems like this function is simple and elegant. That said, I could see many samples with many rows and columns in which the numbers are all positive with few exceptions (if any). This would force our previous function to take as long as possible.
How about a binary search per row? Perhaps the number of elements in a row is not large enough to support a binary search. Let’s find out.
/**
* Use binary search per row.
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 39.2 MB, less than 99.79% of Java online submissions.
* Runtime O(log(n) * m)
*/
static int countNegatives1(int[][] grid) {
// **** count of negative numbers ****
int count = 0;
// **** numbers per row ****
int right = grid[0].length;
// **** traverse all rows in the grid ****
for (int i = 0; i < grid.length; i++) {
// **** find the location of the first negative number (binary search) ****
int firstNegLoc = findNegLocation(grid[i], 0, right - 1);
// **** increment the count (if needed) ****
if (firstNegLoc >= 0)
count += (right - firstNegLoc);
}
// **** return count of negative numbers ****
return count;
}
This is similar to the previous function, with the difference in the way we determine the position of the first negative value. We make use of a second recursive call to find and return the index of the first negative integer.
/**
* Find the location of the first negative number in the array.
* Recursive call.
* Runtime O(log(n))
*/
static int findNegLocation(int[] arr, int left, int right) {
// **** base condition (negative number not found) ****
if (left > right) {
return -1;
}
// **** compute mid ****
int mid = (left + right) / 2;
// **** continue search on right ****
if (arr[mid] >= 0)
return findNegLocation(arr, mid + 1, right);
// **** continue search on left ****
else if (mid > left)
return findNegLocation(arr, left, mid);
// **** found location ****
else
return mid;
}
We start by defining the base condition (stops recursion). If we cannot find a negative value, the function returns a -1 for an index.
We then compute the midpoint for the next pass. We decide if we need to search to the right of the array, the left of the array, or we found the location of the first negative number. If so we return it.
This approach was also accepted by LeetCode. The timing is included in the comments section of the countNegatives1() function.
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 serve of assistance 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 message using the following address: john.canessa@gmail.com. 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 2790 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa