Count Negative Numbers in a Sorted Matrix Java Program - The Coding Shala

Home >> Java Program >> Count Negative Numbers in a Sorted Matrix

 In this post, we are going to write a Java Program to Count Negative Numbers in a Sorted Matrix.

Count Negative Numbers in a Sorted Matrix Problem

Given an m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in the 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 numbers in the matrix.

Example 2:
Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:
Input: grid = [[1,-1],[-1,-1]]
Output: 3

Count Negative Numbers in a Sorted Matrix Java Solution

Approach 1

By using two loops, we will check every element and count the negative numbers.

We can improve this approach as we know the matrix is sorted, so in each row, if we get a negative number then the rest of the elements in that row will be negative.

Java Program: 

class Solution {
    public int countNegatives(int[][] grid) {
        int ans = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j]<0){
                    ans += grid[i].length - j;
                    break;
                }
            }
        }
        return ans;
    }
}

Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.
By

Comments

Post a Comment

Popular Posts from this Blog

N-th Tribonacci Number Solution - The Coding Shala

Home >> Programming >> N-th Tribonacci Number  Hey there, welcome back to another post. In this post, we will learn how to solve the N-th Tribonacci Number problem and will implement its solution in Java. N-th Tribonacci Number Problem Statement The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn.  Example 1:  Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 N-th Tribonacci Number Java Solution using Bottom-Up DP This problem is similar to the Fibonacci series. We can solve it using the Bottom-Up approach of dynamic programming. Time Complexity: O(n) Space Complexity: O(n) The space complexity can be reduced to O(1) by using variables to store the previous three values instead of using an array. Java Program:  class Solution { public int tribonacci( int n) { if (n == 0) return 0; ...
Read more

Find Second Smallest Element in the Array - The Coding Shala

Home >> Programming >> Find Second Smallest Element in the Array  Hey there, welcome back to another post. In this post, we will learn how to find the second smallest number in the array in Java. Find Second Smallest Element in the Array Problem Statement You have given an integer array, return the second smallest element from the array if exists else return no second smallest element exists. Example 1:  Input: [1, 4, 2, 7, 90, -1, -4] Output: -1 Find Second Smallest Element in the Array Solution using Single Iteration Approach By using the below steps we can find the second smallest element in the array by using a single iteration: Initialize two variables first and second for smallest and second smallest numbers and the initial value will be Integer.MAX_VALUE. Traverse the array and check if the current element is smaller than the smallest element then update both first and second. If the current element is between first and second then only update...
Read more

Graph Representation using Adjacency Matrix - The Coding Shala

Image
Home >> Data Structures >> Graph Representation using Adjacency Matrix Graph Representation using Adjacency Matrix In this post, we will see how to represent a graph using the Adjacency Matrix. Generally, the Adjacency matrix is used to check if there is any edge available between two vertices or not. In the Adjacency matrix, we take a 2D array of size v*V, where V is the number of vertices in a graph and array[i][j] = 1 indicates that there is an edge between vertex i and j. The following example explains the Adjacency matrix of a graph: Graph Representation using Adjacency Matrix Java Program We have given the number of vertices 'v' and edges 'E' of a bidirectional graph. Our task is to build a graph through the adjacency matrix and print it. Example 1: Input: 5 7 0 1 0 4 1 2 1 3 1 4 2 3 3 4 Output: 0 1 0 0 1  1 0 1 1 1  0 1 0 1 0  0 1 1 0 1  1 1 0 1 0  Java Code: import java.util....
Read more

Time Complexity, Space Complexity, Asymptotic Notations - The Coding Shala

Image
Home >> Algorithms >> Time and space complexity Time Complexity, Space Complexity, and Asymptotic Notations Time complexity describes the time taken by an algorithm and space complexity describes the memory used by an algorithm. Asymptotic Notations are languages that allow us to calculate time complexity and space complexity. Big O is most commonly used for time complexity or analysis of algorithms. Time Complexity In Computer Science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lowers order terms.[From Wikipedia] In a simple way we can say how much time our code takes to execute.  So, How to calculate the running time of an algorithm? We can have three cases to analyze an algorithm: Worst Case Average Case Best C...
Read more

Java Method Overloading - The Coding Shala

Image
Home >> Learn Java >> Java Method Overloading Java Method Overloading Java class can have more than one method with the same name but different in parameters, known as Method Overloading. Question: What is the use of method overloading? Answer:  Suppose we want to perform some operation like an addition but addition can be performed between two numbers, three numbers or two floats or more. So instead of using different methods, we use the same name of the method with different parameters. This can increase the readability of the program. Method overloading can be achieved by changing numbers of arguments or by changing the data types. Example of Method Overloading in Java The following example explains Method Overloading: //Method Overloading example class Addition { public int add ( int a , int b ){ return a + b ; } public int add ( int a , int b , int c ){ return a + b + c ; ...
Read more