WAP to .Count of -ve numbers Effciiently in 2D Matrix(n * n) of positive and negative numbers is given. Matrix is sorted rowwise and columnwise.

Its Not tough but Its Tricky & Requires Deep Thing so why it has Great Credit

Algorithm

if a[0][n]<0 it menas all the element before it are negative so add count+=j+1; & incement row number
else if its greater > 0 then decrement the column number

#include
using namespace std;

int main()
{
int a[4][3] ={{-30,-29,-28},{-29,30,40},{-25,40,60},{55,65,75}}; // 4*3 Matrix

/*{ { -9, -3,- 2, 120 },
{ -8, -2, 30, 230 },
{ -7, -1, 40, 420 }, 4*4 Matrix
{ -6, 90, 91, 520 }
};

{
{-15, -10, 4, 6},
{-10, -3, 7, 10}, 3*4 Matrix
{-5, -1, 12, 15},
};

*/

int m=4, n=3, num=0, count=0;
for(int i=0, j=n-1; i=0; )
{
if(num > a[i][j])
{
i++;
count += (j+1);
}
else
j--;
}


cout << count << endl;


return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/GhUXg