Search smallest number in a binary matrix
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2421)

Suppose you are given an \( N \times N \) binary matrix with following properties -


    Each row is sorted ( 0 's followed by 1 's)
    Each row is unique (No duplicates)
    Each row represents an unsigned integer

How will you find the row representing the smallest integer.


Posted Answers

Since the binary matrix has dimension \( N \times N \) and the digits in each row are sorted in ascending order, there will be atmost N+1 unique values.
e.g , for N=3 , matrix can be formed from any 3 of the \( \left( \begin{array}{lll}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1
\end{array} \right) \) rows.
Similarly for N=4 and N=5 , matrix rows can be from any 4 and 5 of the \( \left( \begin{array}{llll}
0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array} \right) \) and \( \left( \begin{array}{lllll}
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1
\end{array} \right) \) rows respectively.

The algorithm works as :


  • Start from the first element at array[0][0] .
  • If it is 0 , check the element right to it at array[0][1] .
  • If it is 1 , skip this row and check the element in the next row but same column.
  • Repeat the last two steps until all the rows have been visited or find a row with all zeros.

Time complexity = \( O(N) \).

public int findSmallestEleminBinaryMatrix(int[][] array){

int i = 0;
int j = 0;
int rowNumber = 0;

/* Iterate through the rows from first to last */
while(i < array.length){

/* At each row check whether the element is '0' or '1' */
/* Check until the element is '0' */
while(j < array.length & & array[i][j] == 0) {
j++;
if(rowNumber != i)
rowNumber = i;
/* End of row : Visited all the columns in this row */
if(j == array.length)
break;
}
i++;
}
return rowNumber;
}

You need to Sign In to post your solution.