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

    ReplyDelete
  2. A better solution:
    public class SortedMatrix {
    static int findMaxRowWithOne(int[][] m) {
    int max_row = 0;
    int r = 0;
    int c = m[0].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

    ReplyDelete