4.43
Because each row is strictly increasing and each column strictly decreasing, a row (and likewise a column) can contain at most one 0. Hence there are at most n zeros in the whole matrix.
Idea: exploit the ordering inside every row. Perform a binary search for the value 0 in every row; if it is found, increment a counter.
countZeros(A):
n = len(A)
cnt = 0
for i in range(n): # examine every row
l, r = 0, n-1
while l <= r: # binary search for 0
m = (l + r) // 2
if A[i][m] == 0:
cnt += 1 # only one 0 per row
break
elif A[i][m] < 0: # row is increasing ⇒ 0 is to the right
l = m + 1
else: # A[i][m] > 0 ⇒ 0 is to the left
r = m - 1
return cnt
Correctness:
• A row is strictly increasing, so binary search is applicable.
• Once 0 is discovered in a row we stop searching that row because no other 0 can appear there.
• All rows are examined, so every zero is counted exactly once.
Complexity: each binary search costs O(log n) time, and we perform it for all n rows, giving a total running time of O(n log n).
The algorithm uses only O(1) extra space.
Back to
Chapter 4
