Started looking for an O(log N) solution and got mixed up, the interviewer looked for the O(N) solution which is: Start form the highest value on the first (lowest value) row, if the value is more than 0 then move one index to the left (towards the lower values in the same row) until you find a negative value or reach the end of the row. If you've reached the end of the row, the process is over, return the amount you've found so far. Otherwise the column index + 1 is the number of negative values in this row, because the row is sorted. Keep the column index and advance to the next row. Perform the process for every row while summing the indices you've found. Best Case runtime: every value is negative- go over 1 value in every row- total N = O(N) Worst Case runtime: the last row is the first row to have no negative values, so in total you've advanced N cells "down" and N cells "left", so 2N = O(N).