## Tuesday, October 2, 2012

### Sorted matrix

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

#### 2 comments:

1. Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

Supposing row are sorted by ascending value.

0000111
0000001
0011111
0000111
0000111
0000001
0001111

A brute force algorithm, which scans all rows/cols counting the numbers of 1s, has n^2 complexity

max_row
max_ones = 0
for (r=0 ; r max_ones
max_ones = count
max_row = r
return max_row

Complexity can be reduced inverting the scan order with the following algorithm:

for (c=0 ; c<N; c++)
for (r=0 ; r<N; r++)
if matrix[r][c] == 1
return r

Fabio
fabioang@gmail.com

2. A better solution:
public class SortedMatrix {
static int findMaxRowWithOne(int[][] m) {
int max_row = 0;
int r = 0;
int c = m.length-1;
while ( (r < m.length) && (c >=0) ) {
if (m[r][c]==1) {
--c;
max_row = r;
} else {
++r;
}
}
return max_row;
}

public static void main(String[] args) {
int[][] m = { { 0, 0, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 0, 0, 1, 1 }, };
System.out.println(findMaxRowWithOne(m));
}
}

Fabio
fabioang@gmail.com