1428. Leftmost Column with at Least a One

MediumArrayBinary SearchInteractiveMatrix

Problem Description

The given problem presents a binary matrix with rows sorted in a non-decreasing order. That means each row transitions from 0’s to 1’s. The task is to find the index of the leftmost column that contains at least one '1'. If there's no such column, we return -1.

Access to the matrix is restricted to two operations. One is BinaryMatrix.get(row, col), which returns the value at a specified row and column, and the other is BinaryMatrix.dimensions(), which returns the number of rows and columns.

A key constraint is that any solution must limit the number of calls to BinaryMatrix.get to 1000, making straightforward solutions like scanning every element inefficient and infeasible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The problem is essentially asking us to find the smallest column index that contains the value '1'. Given that each row is sorted, a linear scan from the leftmost column to the rightmost in each row would be wasteful since we might traverse a lot of zeros before finding a one, especially in large matrices.

Instead, the optimal approach is to utilize binary search within each row. Binary search can quickly home in on a '1' in a sorted array by repeatedly halving the search space. For each row, we perform a binary search to find the leftmost '1'. We keep track of the smallest column index across all rows.

With the provided solution, we iterate over each row and perform a binary search. If we find a '1', we update the result to be the minimum of the current result and the column index where '1' was found.

The binary search within each row is optimized with the condition while left < right, which keeps narrowing down the range until left and right converge. When they converge, we check if the leftmost position contains a '1' to consider it as a candidate for our answer.

Since we are only making a couple of calls to BinaryMatrix.get per row (one for each step of the binary search), we stay within the limit of 1000 calls and arrive at an efficient solution.

Learn more about Binary Search patterns.

Solution Approach

The solution follows the Binary Search algorithm to narrow down the leftmost column that contains a '1'. Since we know that each row is sorted, this property allows us to use binary search to efficiently find the first occurrence of '1' per row, if it exists.

The process of binary search starts by initializing two pointers, left and right, which represent the range of columns we're searching in. At the start, left is set to 0, and right is set to the last column index cols - 1. The middle of the range, mid, is then calculated by averaging left and right.

We then enter a loop that continues to narrow down the range by checking if the mid position contains a '0' or a '1'. If a '1' is found, it means we should continue our search to the left side of mid to find the leftmost '1', so we set right to mid. If a '0' is found, we move our search to the right side by setting left to mid + 1. The loop stops once left and right meet, which means we have either found the leftmost '1' for that row or there is no '1' in that row.

A key detail in this implementation is that after the binary search per row, an additional check is done on the left position. If BinaryMatrix.get(row, left) returns '1', then we potentially found a new leftmost '1', and we update the result res accordingly. We use res to store the current smallest index where a '1' was found across all rows processed until that point, initializing it with -1.

This step is crucial as it allows us to progressively update the position of the leftmost '1' column, and by the end of the row iterations, we will have the index of the overall leftmost column with a '1'. If res remains -1 by the end of the loops, it means there were no '1's in the binary matrix, so we return -1.

The algorithm efficiently leverages the sorted property of the rows and minimizes reads, ensuring we stay within the 1000_api_calls limit while still achieving a time complexity of O(logN), where N is the number of columns, multiplied by the number of rows M, yielding an overall time complexity of O(MlogN).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the binary matrix:

[
  [0, 0, 0, 1],
  [0, 1, 1, 1],
  [0, 0, 1, 1],
  [0, 0, 0, 0]
]

We need to find the leftmost column that contains a '1'. Here's how we approach the problem:

We start by getting the dimensions of the matrix. Let's assume dimensions are 4 rows and 4 columns.
We initialize our result (res) to -1, which would be the final answer if there's no '1' in the matrix.
We loop through each row and perform a binary search within that row:
- For the first row, we initialize left = 0 and right = 3 (since there are 4 columns, indices start from 0).
- We calculate the middle, mid = (left + right) / 2, which is initially 1. Since BinaryMatrix.get(0, mid) is 0, we now know that if a '1' exists in this row, it must be to the right. So we move left to mid + 1.
- We recalculate mid = (left + right) / 2, which is now 2. Again, BinaryMatrix.get(0, mid) is 0, so we move left to mid + 1.
- Now left is 3, and our loop terminates since left >= right.
- After the loop, we check BinaryMatrix.get(0, left), which is 1, meaning we've found a column with a '1'. We update res to left, which is 3, the current smallest index of a found '1'.
We repeat this for the remaining rows:
- For the second row, our binary search will quickly converge to left = 1, the first '1'. We update res to min(res, left), so now res becomes 1.
- The third row also leads to updating res to min(res, left) after binary search, but since the leftmost '1' is in column 2, res remains 1.
- The fourth row has no '1's, so it doesn't change res.
Finally, since we have gone through all rows, res holds the index of the leftmost column containing a '1', which in this example is 1.

This approach limits the number of calls to BinaryMatrix.get to 2-3 per row, which is well below the limit of 1000 and is efficient even for large matrices, with a final time complexity of O(MlogN).

Solution Implementation

1class Solution:
2    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
3        # Get the dimensions of the binary matrix
4        rows, cols = binaryMatrix.dimensions()
5        # Initialize result as -1 to represent no 1's found yet
6        result = -1
7        # Iterate over each row to find the leftmost column with a 1
8        for row in range(rows):
9            left, right = 0, cols - 1
10            # Perform a binary search to find the leftmost 1 in the current row
11            while left < right:
12                mid = (left + right) // 2  # Use integer division for Python 3
13                if binaryMatrix.get(row, mid) == 1:
14                    right = mid  # Move the right pointer to the middle if a 1 is found
15                else:
16                    left = mid + 1  # Move the left pointer past the middle otherwise
17          
18            # After exiting the loop, check if the current leftmost index contains a 1
19            if binaryMatrix.get(row, left) == 1:
20                # If a 1 is found and result is -1 (first 1 found), or if the current column
21                # is less than the previously recorded result, update result
22                result = left if result == -1 else min(result, left)
23          
24        # Return the result, which is the index of the leftmost 1 or -1 if no 1 is found
25        return result
26

1// Define the solution class implementing the algorithm to find the leftmost column with at least one '1' in a binary matrix.
2class Solution {
3
4    // Method to find the leftmost column index with a '1'.
5    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
6        // Retrieve the dimensions of the binary matrix.
7        List<Integer> dimensions = binaryMatrix.dimensions();
8        int rows = dimensions.get(0); // Number of rows in the binary matrix.
9        int cols = dimensions.get(1); // Number of columns in the binary matrix.
10      
11        // Initial result is set to -1 (indicating no '1' has been found yet).
12        int result = -1;
13      
14        // Iterate through each row to find the leftmost '1'.
15        for (int row = 0; row < rows; ++row) {
16            // Initialize pointers for the binary search.
17            int left = 0;
18            int right = cols - 1;
19          
20            // Perform binary search in the current row to find the '1'.
21            while (left < right) {
22                // Calculate middle index.
23                int mid = left + (right - left) / 2; // Avoids potential overflow.
24              
25                // Check the value at the middle index and narrow down the search range.
26                if (binaryMatrix.get(row, mid) == 1) {
27                    // '1' is found, shift towards the left (lower indices).
28                    right = mid;
29                } else {
30                    // '0' is found, shift towards the right (higher indices).
31                    left = mid + 1;
32                }
33            }
34          
35            // After the loop, 'left' is the position of the leftmost '1' or the first '0' after all '1's in this row.
36            if (binaryMatrix.get(row, left) == 1) {
37                // Update the result with the new found column with a '1'.
38                if (result == -1) { // If it's the first '1' found in any of the rows.
39                    result = left;
40                } else { // If it's not the first, we take the lesser (more left) of the two columns.
41                    result = Math.min(result, left);
42                }
43            }
44        }
45        // Return the result. If no '1' was found, -1 will be returned, indicating such.
46        return result;
47    }
48}
49

1class Solution {
2public:
3    // Function to find the leftmost column with a 1 in a binary matrix
4    int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
5        // Retrieve the dimensions of the binary matrix
6        vector<int> dimensions = binaryMatrix.dimensions();
7        int rows = dimensions[0]; // Number of rows
8        int cols = dimensions[1]; // Number of columns
9      
10        int result = -1; // Initialize result to -1 to indicate no 1 found
11      
12        // Iterate through each row to find the leftmost 1
13        for (int row = 0; row < rows; ++row) {
14            int left = 0;        // Starting index of the current row
15            int right = cols - 1; // Ending index of the current row
16          
17            // Binary search to find the leftmost 1 in the current row
18            while (left < right) {
19                // Find the middle index
20                int mid = (left + right) / 2; // The '>> 1' has been replaced with '/ 2' for clarity
21              
22                if (binaryMatrix.get(row, mid) == 1) {
23                    // If a 1 is found, narrow the search to the left half
24                    right = mid;
25                } else {
26                    // If a 0 is found, narrow the search to the right half
27                    left = mid + 1;
28                }
29            }
30          
31            // After binary search, check if we have found a 1 at the 'left' index
32            // and update the result accordingly
33            if (binaryMatrix.get(row, left) == 1) {
34                // If this is the first 1 found, or if the current index is smaller than previous one
35                if (result == -1) {
36                    result = left;  // update the result with the current index
37                } else {
38                    result = min(result, left); // update the result with the smaller index
39                }
40            }
41        }
42      
43        // Return the result
44        return result;
45    }
46};
47

1// Interface representing the BinaryMatrix's methods for TypeScript type checking
2interface BinaryMatrix {
3    get(row: number, col: number): number;
4    dimensions(): number[];
5}
6
7// Variable to hold the leftmost column with a 1 in a binary matrix
8let leftMostColumnResult: number = -1;
9
10// Function to find the leftmost column with a 1 in a binary matrix
11function leftMostColumnWithOne(binaryMatrix: BinaryMatrix): number {
12    // Retrieve the dimensions of the binary matrix
13    let dimensions: number[] = binaryMatrix.dimensions();
14    let rows: number = dimensions[0]; // Number of rows
15    let cols: number = dimensions[1]; // Number of columns
16  
17    leftMostColumnResult = -1; // Initialize the result to -1 to indicate no 1 has been found
18  
19    // Iterate through each row to find the leftmost 1
20    for (let row = 0; row < rows; ++row) {
21        let left = 0;        // Starting index of the current row
22        let right = cols - 1; // Ending index of the current row
23      
24        // Binary search to find the leftmost 1 in the current row
25        while (left < right) {
26            // Find the middle index
27            let mid = Math.floor((left + right) / 2); // Use floor to avoid decimal indices
28          
29            if (binaryMatrix.get(row, mid) === 1) {
30                // If a 1 is found, narrow the search to the left half
31                right = mid;
32            } else {
33                // If a 0 is found, narrow the search to the right half
34                left = mid + 1;
35            }
36        }
37      
38        // After binary search, check if we have found a 1 at the 'left' index
39        // and update the result accordingly
40        if (binaryMatrix.get(row, left) === 1) {
41            // If this is the first 1 found, or if the current index is smaller than the previously found one
42            if (leftMostColumnResult === -1) {
43                leftMostColumnResult = left;  // Update the result with the current index
44            } else {
45                leftMostColumnResult = Math.min(leftMostColumnResult, left); // Update the result with the smaller index
46            }
47        }
48    }
49  
50    // Return the result
51    return leftMostColumnResult;
52}
53
54// Example usage:
55// let matrix: BinaryMatrix = new SomeBinaryMatrixImplementation();
56// console.log(leftMostColumnWithOne(matrix));
57

Time and Space Complexity

Time Complexity

The provided code loops through each row of the binary matrix to find the leftmost column containing a 1. For each row, the code implements a binary search which has a logarithmic time complexity. Since the binary search is conducted for each of the rows, the total time complexity is O(rows * log(cols)).

Here's the breakdown of the time complexity:

We iterate over each row once: O(rows)
For each row, a binary search is conducted within cols, which takes O(log(cols))

Thus, the combined time complexity is O(rows * log(cols)).

Space Complexity

The space complexity is O(1) since we are only using a constant amount of extra space. The variables res, left, right, mid, and the loop counter row do not depend on the size of the input and use a fixed amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know