Leftmost Column with at Least a One

Medium Binary Search 2D Binary Search + Step Search Original on LeetCode

Reported atUber

Leftmost Column with at Least a One is a medium binary search problem solved with the 2d binary search + step search pattern. The best approach, optimal (staircase from the top-right corner), runs in O(rows + cols) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (scan column by column) up.

Problem

A binary matrix has every row sorted in non-decreasing order, so each row is a run of 0s followed by a run of 1s. Return the index of the leftmost column that contains at least one 1, or -1 if the matrix has no 1 at all.

You cannot see the matrix directly. It is given through a BinaryMatrix object with two methods: get(row, col) returns the value of one cell, and dimensions() returns [rows, cols]. Solutions that call get more than 1000 times are rejected.

Examples

Example 1

Input
mat = [[0,0,1],[0,1,1],[0,0,0]]
Output
1
Why
Row 1 has its first 1 in column 1, and no row has a 1 in column 0.

Example 2

Input
mat = [[0,0],[0,0]]
Output
-1
Why
There is no 1 anywhere.

Example 3

Input
mat = [[1,1,1,1],[0,0,1,1]]
Output
0
Why
Row 0 starts with a 1.

Constraints

  • rows == mat.length, cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] is 0 or 1, and every row is sorted in non-decreasing order
  • At most 1000 calls to get are allowed.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan column by column)O(rows · cols)O(1)
Better (binary search in every row)O(rows · log cols)O(1)
Optimal (staircase from the top-right corner)O(rows + cols)O(1)

1Brute force (scan column by column)

TimeO(rows · cols)In the worst case every cell is read once.
SpaceO(1)Only loop counters.

Check columns from left to right and, inside each column, every row. The first column where some row holds a 1 is the answer. This ignores the sorted rows and may read every cell, which breaks the call limit on large matrices.

  1. Read rows and cols from dimensions().
  2. For c from 0 to cols - 1, for r from 0 to rows - 1: if get(r, c) == 1, return c.
  3. Return -1.
class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int rows = dim.get(0), cols = dim.get(1);
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                if (binaryMatrix.get(r, c) == 1) return c;
            }
        }
        return -1;
    }
}

2Better (binary search in every row)

TimeO(rows · log cols)One binary search of about log cols reads per row (about 700 reads for a 100 x 100 matrix).
SpaceO(1)A few integers.

Each row is 0s then 1s, so the index of its first 1 can be binary searched. The answer is the smallest such index over all rows.

  1. Set best = cols (meaning: no 1 found yet).
  2. For each row, binary search the first column in [0, cols) with get(r, c) == 1; lo ends at cols if the row has no 1.
  3. best = min(best, lo).
  4. Return best == cols ? -1 : best.
class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int rows = dim.get(0), cols = dim.get(1);
        int best = cols;
        for (int r = 0; r < rows; r++) {
            int lo = 0, hi = cols;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (binaryMatrix.get(r, mid) == 1) hi = mid;
                else lo = mid + 1;
            }
            best = Math.min(best, lo);
        }
        return best == cols ? -1 : best;
    }
}

3Optimal (staircase from the top-right corner)

TimeO(rows + cols)Every read moves the pointer left or down, and it can do that at most cols + rows times.
SpaceO(1)Three integers.

Start at the top-right cell. If it is 1, this column is a candidate and anything better lies to the left, so record it and step left. If it is 0, every cell to its left in this row is also 0, so the row is finished: step down. Each read moves one step left or down, so the walk ends after at most rows + cols reads.

  1. r = 0, c = cols - 1, ans = -1.
  2. While r < rows and c >= 0: if get(r, c) == 1, set ans = c and c--; otherwise r++.
  3. Return ans.
class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int rows = dim.get(0), cols = dim.get(1);
        int r = 0, c = cols - 1, ans = -1;
        while (r < rows && c >= 0) {
            if (binaryMatrix.get(r, c) == 1) {
                ans = c;
                c--;
            } else {
                r++;
            }
        }
        return ans;
    }
}

Edge cases to test

  • No 1 in the whole matrix: return -1
  • A single row or a single column
  • Every row is all 1s: the answer is 0
  • Only the last column holds 1s, in the last row

Hints

Hint 1

Because rows are sorted, each row is some 0s followed by some 1s. The first 1 of a row can be found with binary search.

Hint 2

Start at the top-right corner. A 1 means the answer is this column or further left, so step left; a 0 means this row cannot help further, so step down.

FAQ

What is the best time complexity for Leftmost Column with at Least a One?

Optimal (staircase from the top-right corner) runs in O(rows + cols) time and O(1) extra space. Every read moves the pointer left or down, and it can do that at most cols + rows times.

Which pattern does Leftmost Column with at Least a One use?

It is a binary search problem that uses the 2d binary search + step search pattern. Other problems with the same pattern: Row with max 1s, Search a 2D Matrix, Search a 2D Matrix II (Young Tableau).

Is there a brute force solution for Leftmost Column with at Least a One?

Yes. Brute force (scan column by column) takes O(rows · cols) time and O(1) space. Check columns from left to right and, inside each column, every row.

Which edge cases should I test for Leftmost Column with at Least a One?

No 1 in the whole matrix: return -1; A single row or a single column; Every row is all 1s: the answer is 0; Only the last column holds 1s, in the last row.