Approach Summary
Start at bottom-left. If negative, all elements to the right are also negative — add count and move up. Else move right.
How to Recognize This Pattern
- Sorted rows and columns — start at a corner
- Staircase walk from bottom-left: O(m+n) beats binary search per row
Complexity Analysis
Time Complexity
O(m + n)
Space Complexity
O(1)
Tags
Array Binary Search Matrix