Jobs

Interviews

Discussions

Leftmost Column with at Least a One

Medium

SAP

2 views

Topics:

ArraysBinary SearchTwo Pointers

Given a rows x cols binary matrix mat, find the leftmost column (0-indexed) with at least one 1 in it.

Return the index of the leftmost column with at least one 1 in it. If such a column does not exist, return -1.

You must solve the problem in O(rows + cols) or better.

Example 1:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Example 2:

Input: mat = [[0,0,0,0],[0,0,0,0],[0,0,0,0]]
Output: -1

Example 3:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is either 0 or 1.

Try coding it in LeetCode

Leftmost Column with at Least a One

Medium

SAP

2 views

Topics:

ArraysBinary SearchTwo Pointers

Given a rows x cols binary matrix mat, find the leftmost column (0-indexed) with at least one 1 in it.

Return the index of the leftmost column with at least one 1 in it. If such a column does not exist, return -1.

You must solve the problem in O(rows + cols) or better.

Example 1:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Example 2:

Input: mat = [[0,0,0,0],[0,0,0,0],[0,0,0,0]]
Output: -1

Example 3:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is either 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum size of either dimension? Is the matrix guaranteed to be rectangular?
What is the data type of the elements in the matrix? Are they guaranteed to be only 0 or 1, or could there be other values?
Is the matrix guaranteed to have at least one row and one column? What should I return if the matrix is empty?
If there are multiple columns with at least one '1', should I return the index of the leftmost one (the first one encountered from the left)?
If no column contains a '1', what should I return?

Brute Force Solution

Approach

The brute force approach is very simple: We examine each column from left to right. For each column, we check every single cell in that column to see if it contains a one.

Here's how the algorithm would work step-by-step:

Start by looking at the very first column.
Go through each cell in that column, one by one, from top to bottom.
If you find a cell with a one in it, you've found the leftmost column with at least one one. You're done!
If you go through the entire first column and don't find any ones, move to the next column to the right.
Repeat the process of checking each cell in the new column.
Continue moving column by column until you find a column with at least one one, or you reach the end with no ones. If you make it to the end with no ones, you know the answer is that no column has a one.

Code Implementation

def leftmost_column_with_one_brute_force(binary_matrix):
    number_of_rows = len(binary_matrix)
    number_of_columns = len(binary_matrix[0]) if number_of_rows > 0 else 0

    # Iterate through each column from left to right
    for column_index in range(number_of_columns):

        # Check each row in the current column for a one
        for row_index in range(number_of_rows):

            # If a one is found, return the current column index
            if binary_matrix[row_index][column_index] == 1:
                return column_index

    # No column with a one was found
    return -1

Big(O) Analysis

Time Complexity

O(m*n) – The brute force approach iterates through each column of the binary matrix, where n is the number of columns. For each column, it iterates through each row, where m is the number of rows, searching for a 1. In the worst-case scenario, we might need to examine all cells in the matrix before finding a 1 or determining that no column contains a 1. Therefore, the time complexity is proportional to m*n.

Space Complexity

O(1) – The brute force algorithm iterates through the columns and rows of the input matrix. It does not create any auxiliary data structures to store intermediate results or visited cells. The algorithm uses a constant amount of extra space, primarily for loop counters and potentially a variable to store whether a '1' has been found. Therefore, the space complexity is O(1), indicating constant auxiliary space usage regardless of the size of the input matrix.

Optimal Solution

Approach

We're looking for the leftmost column that has a '1' in it. The key is to start in a strategic spot and move in a way that eliminates large sections of the data with each step. This avoids checking every single cell in the table.

Here's how the algorithm would work step-by-step:

Start at the top right corner of the table.
If the current value is a '0', it means all the columns to the left in that row are also '0'. So, move one column to the left.
If the current value is a '1', it means we might have found the leftmost column with a '1'. Record the column number, and then move one row up, to check if there's an even earlier '1' in a column to the left.
Keep moving either left (if you see a '0') or up (if you see a '1'), updating the recorded leftmost column whenever you see a '1'.
When you reach the top of the table or the left edge of the table, the recorded column number will be the leftmost column containing a '1'.

Code Implementation

def find_leftmost_column_with_one(binary_matrix):
    rows = len(binary_matrix)
    cols = len(binary_matrix[0]) if rows > 0 else 0

    leftmost_column = -1
    row_index = 0
    column_index = cols - 1

    while row_index < rows and column_index >= 0:
        if binary_matrix[row_index][column_index] == 1:
            # Found a '1', so update leftmost and move up.
            leftmost_column = column_index

            row_index += 1
        else:
            # Current is '0', move to the left.
            column_index -= 1

    return leftmost_column

Big(O) Analysis

Time Complexity

O(m + n) – The algorithm starts at the top right corner of the m x n matrix. The key is that with each comparison, we either move one row up or one column to the left. We can move at most 'm' steps upwards (the height of the matrix) and at most 'n' steps to the left (the width of the matrix). Therefore, the maximum number of steps is m + n, making the time complexity O(m + n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only stores the current row and column indices and the leftmost column index found so far. These variables take up a fixed amount of memory regardless of the dimensions of the matrix. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null matrix input	Return -1 immediately as a null matrix does not have any columns.
Empty matrix (0 rows)	Return -1 since there are no columns to check if the matrix has 0 rows.
Matrix with 0 columns	Return -1 because if a matrix has zero columns it has no leftmost column containing a one.
Matrix with all zeros	Return -1 since there will be no leftmost column with at least a one.
Matrix where the leftmost column containing a one is the first column (index 0)	The algorithm should correctly identify and return 0.
Matrix where all rows have a 1 in the first column	The binary search should still function correctly, efficiently finding index 0.
Very large matrix (potential for integer overflow if calculating column indices naively)	Use appropriate data types and/or avoid explicit multiplication when possible to prevent overflow.
Matrix where all rows have a '1' but '1' appears in different columns for each row.	The algorithm should binary search each row to find the leftmost '1' and keep track of the minimum column index.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum size of either dimension? Is the matrix guaranteed to be rectangular?
What is the data type of the elements in the matrix? Are they guaranteed to be only 0 or 1, or could there be other values?
Is the matrix guaranteed to have at least one row and one column? What should I return if the matrix is empty?
If there are multiple columns with at least one '1', should I return the index of the leftmost one (the first one encountered from the left)?
If no column contains a '1', what should I return?

Brute Force Solution

Approach

The brute force approach is very simple: We examine each column from left to right. For each column, we check every single cell in that column to see if it contains a one.

Here's how the algorithm would work step-by-step:

Start by looking at the very first column.
Go through each cell in that column, one by one, from top to bottom.
If you find a cell with a one in it, you've found the leftmost column with at least one one. You're done!
If you go through the entire first column and don't find any ones, move to the next column to the right.
Repeat the process of checking each cell in the new column.
Continue moving column by column until you find a column with at least one one, or you reach the end with no ones. If you make it to the end with no ones, you know the answer is that no column has a one.

Code Implementation

def leftmost_column_with_one_brute_force(binary_matrix):
    number_of_rows = len(binary_matrix)
    number_of_columns = len(binary_matrix[0]) if number_of_rows > 0 else 0

    # Iterate through each column from left to right
    for column_index in range(number_of_columns):

        # Check each row in the current column for a one
        for row_index in range(number_of_rows):

            # If a one is found, return the current column index
            if binary_matrix[row_index][column_index] == 1:
                return column_index

    # No column with a one was found
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top right corner of the table.
If the current value is a '0', it means all the columns to the left in that row are also '0'. So, move one column to the left.
If the current value is a '1', it means we might have found the leftmost column with a '1'. Record the column number, and then move one row up, to check if there's an even earlier '1' in a column to the left.
Keep moving either left (if you see a '0') or up (if you see a '1'), updating the recorded leftmost column whenever you see a '1'.
When you reach the top of the table or the left edge of the table, the recorded column number will be the leftmost column containing a '1'.

Code Implementation

def find_leftmost_column_with_one(binary_matrix):
    rows = len(binary_matrix)
    cols = len(binary_matrix[0]) if rows > 0 else 0

    leftmost_column = -1
    row_index = 0
    column_index = cols - 1

    while row_index < rows and column_index >= 0:
        if binary_matrix[row_index][column_index] == 1:
            # Found a '1', so update leftmost and move up.
            leftmost_column = column_index

            row_index += 1
        else:
            # Current is '0', move to the left.
            column_index -= 1

    return leftmost_column

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null matrix input	Return -1 immediately as a null matrix does not have any columns.
Empty matrix (0 rows)	Return -1 since there are no columns to check if the matrix has 0 rows.
Matrix with 0 columns	Return -1 because if a matrix has zero columns it has no leftmost column containing a one.
Matrix with all zeros	Return -1 since there will be no leftmost column with at least a one.
Matrix where the leftmost column containing a one is the first column (index 0)	The algorithm should correctly identify and return 0.
Matrix where all rows have a 1 in the first column	The binary search should still function correctly, efficiently finding index 0.
Very large matrix (potential for integer overflow if calculating column indices naively)	Use appropriate data types and/or avoid explicit multiplication when possible to prevent overflow.
Matrix where all rows have a '1' but '1' appears in different columns for each row.	The algorithm should binary search each row to find the leftmost '1' and keep track of the minimum column index.