Jobs

Interviews

Discussions

Search a 2D Matrix

Medium

Bloomberg LP

0 views

Topics:

ArraysBinary Search

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

Search a 2D Matrix

Medium

Bloomberg LP

0 views

Topics:

ArraysBinary Search

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

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 constraints on the dimensions m and n of the matrix? Could either be zero?
What is the range of integer values within the matrix and for the target? Could they be negative?
Is it guaranteed that each row is sorted in non-decreasing order, and that the first integer of each row is greater than the last integer of the previous row?
If the matrix is empty (m=0 or n=0), what should I return?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

Imagine a grid of numbers and you need to find a specific target number. The brute force approach means we will look at every single number in the grid, one by one. We'll keep checking until we either find the target or run out of numbers to check.

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

Start by looking at the very first number in the grid.
Check if this number is the number we're looking for.
If it is, we're done! We found it.
If not, move to the next number in the grid, going row by row.
Keep checking each number to see if it matches our target number.
If we reach the end of the grid without finding the number, then the number is not in the grid.

Code Implementation

def search_matrix_brute_force(matrix, target):
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0])

    for row_index in range(number_of_rows):
        # Iterate through each row.

        for col_index in range(number_of_cols):
            # Iterate through each column in current row.

            if matrix[row_index][col_index] == target:
                #If target is found return True

                return True

    # If target not found in the matrix.
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The brute force approach iterates through each element of the 2D matrix. Let 'm' be the number of rows and 'n' be the number of columns in the matrix. In the worst-case scenario, we might have to examine every element to determine if the target exists or not. Therefore, the algorithm visits each of the m*n elements resulting in m*n operations, which simplifies to O(m*n).

Space Complexity

O(1) – The provided algorithm iterates through the 2D matrix, checking each element against the target value. It doesn't use any auxiliary data structures such as temporary arrays, hash maps, or sets to store intermediate results. The algorithm only utilizes a fixed number of variables for iteration, independent of the matrix size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The trick is to treat the 2D matrix like one long, sorted list, even though it's shaped like a rectangle. This lets us use a very efficient search method similar to how you'd find a word in a dictionary.

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

Imagine the matrix is a single sorted sequence of numbers. Figure out where the 'middle' number of the entire sequence would be located within the 2D matrix.
Compare the number you're searching for with the number you found in the 'middle'.
If the number you're searching for is smaller than the 'middle' number, you know it must be in the first half of the imaginary list. Discard the entire second half of the matrix from your search.
If the number you're searching for is larger than the 'middle' number, you know it must be in the second half of the imaginary list. Discard the entire first half of the matrix from your search.
Repeat this process of finding the middle and comparing, each time narrowing down the search area by half. Keep going until you either find the number or the search area becomes empty.
If the search area becomes empty, it means the number isn't in the matrix.

Code Implementation

def search_2d_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    left_pointer = 0
    right_pointer = number_of_rows * number_of_columns - 1

    while left_pointer <= right_pointer:
        middle_element = (left_pointer + right_pointer) // 2
        row_index = middle_element // number_of_columns
        column_index = middle_element % number_of_columns
        middle_value = matrix[row_index][column_index]

        # Adjust search space based on middle value
        if target == middle_value:
            return True

        # Narrow search to the left half
        elif target < middle_value:
            right_pointer = middle_element - 1

        # Narrow search to the right half
        else:
            left_pointer = middle_element + 1

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log(m*n)) – The algorithm performs a binary search on the 2D matrix, effectively treating it as a sorted 1D array of size m*n where m is the number of rows and n is the number of columns. Each iteration of the binary search halves the search space. Therefore, the number of iterations is logarithmic with respect to the total number of elements in the matrix (m*n). The time complexity is thus O(log(m*n)).

Space Complexity

O(1) – The described algorithm performs binary search directly within the 2D matrix. It only requires a few integer variables to keep track of the low and high boundaries of the search space, as well as the row and column indices to access elements. The number of variables used remains constant regardless of the matrix dimensions (rows and columns). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
matrix is null or empty	Return false immediately, as there are no elements to search.
matrix has zero rows or zero columns	Return false immediately, as there are no elements to search.
matrix contains only one row	Binary search this single row to find the target.
matrix contains only one column	Binary search the first element of each row to find the target.
target is smaller than the smallest element in the matrix	Return false since the matrix is sorted in non-decreasing order.
target is larger than the largest element in the matrix	Return false since the matrix is sorted and cannot contain the target.
Large matrix dimensions that could lead to integer overflow in calculations of indices	Use long integers or alternative formulas that avoid overflow for index calculations, if necessary.
target equals to the first element of a row	Algorithm should return true once the first element is the target value

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 constraints on the dimensions m and n of the matrix? Could either be zero?
What is the range of integer values within the matrix and for the target? Could they be negative?
Is it guaranteed that each row is sorted in non-decreasing order, and that the first integer of each row is greater than the last integer of the previous row?
If the matrix is empty (m=0 or n=0), what should I return?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

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

Start by looking at the very first number in the grid.
Check if this number is the number we're looking for.
If it is, we're done! We found it.
If not, move to the next number in the grid, going row by row.
Keep checking each number to see if it matches our target number.
If we reach the end of the grid without finding the number, then the number is not in the grid.

Code Implementation

def search_matrix_brute_force(matrix, target):
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0])

    for row_index in range(number_of_rows):
        # Iterate through each row.

        for col_index in range(number_of_cols):
            # Iterate through each column in current row.

            if matrix[row_index][col_index] == target:
                #If target is found return True

                return True

    # If target not found in the matrix.
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the matrix is a single sorted sequence of numbers. Figure out where the 'middle' number of the entire sequence would be located within the 2D matrix.
Compare the number you're searching for with the number you found in the 'middle'.
If the number you're searching for is smaller than the 'middle' number, you know it must be in the first half of the imaginary list. Discard the entire second half of the matrix from your search.
If the number you're searching for is larger than the 'middle' number, you know it must be in the second half of the imaginary list. Discard the entire first half of the matrix from your search.
Repeat this process of finding the middle and comparing, each time narrowing down the search area by half. Keep going until you either find the number or the search area becomes empty.
If the search area becomes empty, it means the number isn't in the matrix.

Code Implementation

def search_2d_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    left_pointer = 0
    right_pointer = number_of_rows * number_of_columns - 1

    while left_pointer <= right_pointer:
        middle_element = (left_pointer + right_pointer) // 2
        row_index = middle_element // number_of_columns
        column_index = middle_element % number_of_columns
        middle_value = matrix[row_index][column_index]

        # Adjust search space based on middle value
        if target == middle_value:
            return True

        # Narrow search to the left half
        elif target < middle_value:
            right_pointer = middle_element - 1

        # Narrow search to the right half
        else:
            left_pointer = middle_element + 1

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
matrix is null or empty	Return false immediately, as there are no elements to search.
matrix has zero rows or zero columns	Return false immediately, as there are no elements to search.
matrix contains only one row	Binary search this single row to find the target.
matrix contains only one column	Binary search the first element of each row to find the target.
target is smaller than the smallest element in the matrix	Return false since the matrix is sorted in non-decreasing order.
target is larger than the largest element in the matrix	Return false since the matrix is sorted and cannot contain the target.
Large matrix dimensions that could lead to integer overflow in calculations of indices	Use long integers or alternative formulas that avoid overflow for index calculations, if necessary.
target equals to the first element of a row	Algorithm should return true once the first element is the target value