Teaching Kids Programming – Binary Matrix Leftmost One

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers matrix which contains 1s and 0s. Given that each row is sorted in ascending order with 0s coming before 1s, return the leftmost column index with the value of 1. If there’s no row with a 1, return -1.

Can you solve it faster than O(NM)

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5 6

matrix = [     [0, 0, 0, 0],     [0, 0, 1, 1],     [0, 0, 0, 1],     [0, 1, 1, 1] ]

matrix = [
    [0, 0, 0, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 1, 1, 1]
]

Output
1
Explanation
The last row contains the leftmost column with a one at index 1.

Bruteforce Algorithm (Sweep Line of Column) to Find LeftMost One in Binary Matrix

Since each row is sorted, the zeros come before ones, we can bruteforce the matrix from left to right and return the column as soon as we find one otherwise -1.

1
2
3
4
5
6
7
8
9

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        for c in range(len(matrix[0])):
            for r in range(len(matrix)):
                if matrix[r][c] == 1:
                    return c
        return -1

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        for c in range(len(matrix[0])):
            for r in range(len(matrix)):
                if matrix[r][c] == 1:
                    return c
        return -1

The time complexity is O(NM) – space complexity is O(1).

Greedy Algorithm to Find LeftMost One in Binary Matrix

We can start at top-right corner. If current cell is one, there is no point checking the cells down as they won’t improve the answer, in this case we move left. If it is zero, we can try moving down. When we are cross the boundary, we exit the process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        rows = len(matrix)
        cols = len(matrix[0])
        r, c = 0, cols - 1
        ans = -1
        while r < rows and c >= 0:
            if matrix[r][c] == 1:
                ans = c
                c -= 1
            else:
                r += 1
        return ans

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        rows = len(matrix)
        cols = len(matrix[0])
        r, c = 0, cols - 1
        ans = -1
        while r < rows and c >= 0:
            if matrix[r][c] == 1:
                ans = c
                c -= 1
            else:
                r += 1
        return ans

The time complexity is O(N + M) and the space complexity is O(1).

Binary Search Algorithm to Find LeftMost One in Binary Matrix

As each row is sorted, we can binary search each row for the leftmost ones.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        ans = math.inf
        for i in range(len(matrix)):
            x = bisect_left(matrix[i], 1)
            if x != len(matrix[i]):
                ans = min(ans, x)
        return ans if ans != math.inf else -1

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        ans = math.inf
        for i in range(len(matrix)):
            x = bisect_left(matrix[i], 1)
            if x != len(matrix[i]):
                ans = min(ans, x)
        return ans if ans != math.inf else -1

Time complexity is O(NLogM). The space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —