1428. Leftmost Column with at Least a One
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.
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Consider the binary matrix:
1[ 2 [0, 0, 0, 1], 3 [0, 1, 1, 1], 4 [0, 0, 1, 1], 5 [0, 0, 0, 0] 6]
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
andright = 3
(since there are 4 columns, indices start from 0). - We calculate the middle,
mid = (left + right) / 2
, which is initially1
. SinceBinaryMatrix.get(0, mid)
is0
, we now know that if a '1' exists in this row, it must be to the right. So we moveleft
tomid + 1
. - We recalculate
mid = (left + right) / 2
, which is now2
. Again,BinaryMatrix.get(0, mid)
is0
, so we moveleft
tomid + 1
. - Now
left
is3
, and our loop terminates sinceleft >= right
. - After the loop, we check
BinaryMatrix.get(0, left)
, which is1
, meaning we've found a column with a '1'. We updateres
toleft
, which is3
, the current smallest index of a found '1'.
- For the first row, we initialize
- We repeat this for the remaining rows:
- For the second row, our binary search will quickly converge to
left = 1
, the first '1'. We updateres
tomin(res, left)
, so nowres
becomes1
. - The third row also leads to updating
res
tomin(res, left)
after binary search, but since the leftmost '1' is in column2
,res
remains1
. - The fourth row has no '1's, so it doesn't change
res
.
- For the second row, our binary search will quickly converge to
- Finally, since we have gone through all rows,
res
holds the index of the leftmost column containing a '1', which in this example is1
.
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 takesO(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.
Which data structure is used to implement priority queue?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.