Leetcode 1351 - Count Negative Numbers in a Sorted Matrix

Understanding the problem

LeetCode 1351 - Count Negative Numbers in a Sorted Matrix is a problem where you are given a sorted matrix of integers, and you need to count the number of negative integers in the matrix. Here is an example:

Input: matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Output: 8

Plan your solution

To solve this problem, we can use a simple linear search. We’ll iterate over the elements of the matrix, starting from the top right corner, and count the number of negative elements that we encounter. We can do this in O(n) time, where n is the number of elements in the matrix.

Implement your solution

Here is the implementation of the countNegatives function:

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        # Initialize a count variable to keep track of the number of negative elements that we have encountered
        count = 0
        # Iterate over the rows in the matrix
        for row in grid:
            # Iterate over the elements in the row
            for num in row:
                # Check if the element is negative
                if num < 0:
                    # If it is, increment the count variable
                    count += 1
        # Return the count variable as the result of the function
        return count

Test your solution

# Test case 1
matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
expected_output = 8
assert Solution().countNegatives(matrix) == expected_output

# Test case 2
matrix = [[-3,-2,-1,1],[-2,-1,0,2],[-1,0,1,3],[0,1,2,4]]
expected_output = 4
assert Solution().countNegatives(matrix) == expected_output

# Test case 3
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
expected_output = 0
assert Solution().countNegatives(matrix) == expected_output

# Test case 4
matrix = [[-4,-3,-2,-1],[-3,-2,-1,0],[-2,-1,0,1],[-1,0,1,2]]
expected_output = 16
assert Solution().countNegatives(matrix) == expected_output

# Test case 5
matrix = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
expected_output = 0
assert Solution().countNegatives(matrix) == expected_output

Related:

• search a 2d matrix ii
• search a 2d matrix
• single element in a sorted array
• search in rotated sorted array

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together