Challenge #18 - Count Negative Numbers in a Sorted Matrix

Hey-yo!

Welcome to day #18 of my coding diary. It has been a great journey so far, a really good daily-code-workout. It's too much fun, trust me.

TLDR;

• Problem seemed pretty easy to me at first but it turned out be a gem when I tried to optimize the solution.
• This is one of the cleverest problems I have ever seen.
• One can just slap on the brute force approach and get on with his life BUT I would recommend everyone to just solve this problem once.

---

Problem of the day - Count Negative Numbers in a Sorted Matrix

Tag - Easy

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

---

Ahhmmm, calm down, calm down! I know this seems pretty easy. I could not stop my hands, coding the brute force O(n2)solution for it.

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int res = 0;
        for(auto row: grid) {
            for(int val: row) {
                if(val < 0) res++;
            }
        }
        return res;
    }
};

Quite straightforward. 30 seconds of code! haha. But pretty bad from an optimization point of view. Let's think of a good approach.

---

When I see something sorted, I call my dearest friend, binary search. Let's reduce the time complexity from O(n2) to O(n log m).

Here is the code

class Solution {
public:
    int getIndex(vector<int> row) {
        int low = 0;
        int high = row.size() - 1;
        int mid = (low+high)/2;

        while(low != high) {
            mid = (low+high)/2;
            if(row[mid] >= 0) {
                low = mid +1; 
            } else {
                high = mid;
            }
        }
        return row[low] >= 0 ? -1 : low;
    }

    int countNegatives(vector<vector<int>>& grid) {
        int res = 0;
        int index;
        for(auto row: grid) {
            index = getIndex(row);
            res += (index == -1 ? 0 : row.size() - index);
        }
        return res;
    }
};

Pardon my ugly code style.

I hit submit and was about to celebrate my small achievement BUT a small text below the problem statement shattered all my hopes.

Follow up: Could you find an O(n + m) solution?

Oh man, I thought I cracked the best solution for this. Ah shit, here we go again.

---

No worries, let's try to find it can be done in O(n + m).

I am not gonna lie. I tried my best but could not find any approach to solving it in the given time complexity. I can just think of something, checking for negative element, if found, based on that, just tick mark the index for new rows also.

After checking out the discussion tab, I was blown away by the approach. It was so clever.

So, We start from the upper right, check if one positive element is found, we just jump to the next row, for the same index (as we know columns are also in a sorted manner).

I know, it's complex to understand. This guy has written an excellent explanation. Check it out.

Here is the smartest approach

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int res = 0;

        int row = grid.size();
        int col = grid[0].size();
        int r = 0;
        int n = col - 1;

        while(r < row) {
            while(n >= 0 && grid[r][n] < 0) n--;
            res += col - n - 1;
            r++;
        }
        return res;
    }
};

I am in love with this problem. The way, it's designed is commendable. It was fun solving it.

As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

Do let me know if you are also solving problems.

---

You might like previous editions of my coding diary

• Day #17 - Sum of Unique Elements.
• Day #16 - Best Time to Buy and Sell Stock.
• Day #15 - Count Number of Pairs With Absolute Difference K.
• Day #14 - Minimum Number of Operations to Move All Balls to Each Box.
• Day #13 - Number Of Rectangles That Can Form The Largest Square.
• Day #12 - Unique Morse Code Words.
• Day #11 - Count the Number of Consistent Strings.
• Day #10 - Find Greatest Common Divisor of Array.