Jobs

Interviews

Discussions

Find a Peak Element II

Medium

Google

1 view

Topics:

ArraysBinary Search

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].

You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.

For example:

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

How would you efficiently find a peak element in the given 2D matrix?

Find a Peak Element II

Medium

Google

1 view

Topics:

ArraysBinary Search

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].

You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.

For example:

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

How would you efficiently find a peak element in the given 2D matrix?

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 (number of rows and columns) of the matrix, and what are the upper bounds for those dimensions?
What is the range of integer values that can be present in the matrix? Can they be negative?
If there are multiple peak elements, is it acceptable to return the coordinates of any one of them?
Is a matrix guaranteed to have at least one row and one column (i.e., can it be empty)?
Is a peak element defined as strictly greater than its immediate neighbors (up, down, left, right), or can it be greater than or equal?

Brute Force Solution

Approach

The brute force approach involves checking every single element in the grid to see if it's a peak. We compare each element with all of its neighbors to determine if it's greater than or equal to them.

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

Look at the very first element in the grid.
Compare this element to all its neighbors (up, down, left, right).
If the element is greater than or equal to all of its neighbors, then it's a peak, and we're done.
If not, move on to the next element in the grid.
Repeat this process for every element in the grid.
If we go through the entire grid and find no peak, it means we made a mistake in our assumptions about the grid structure (though this shouldn't happen given the problem constraints).

Code Implementation

def find_peak_element_ii_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            current_element = matrix[row_index][column_index]

            # Check neighbors: up, down, left, right
            up = matrix[row_index - 1][column_index] if row_index > 0 else -1

            down = matrix[row_index + 1][column_index] if row_index < number_of_rows - 1 else -1

            left = matrix[row_index][column_index - 1] if column_index > 0 else -1

            right = matrix[row_index][column_index + 1] if column_index < number_of_columns - 1 else -1

            # Need to handle edge cases where neighbors don't exist
            is_peak = True

            if up != -1 and current_element < up:
                is_peak = False

            if down != -1 and current_element < down:
                is_peak = False

            if left != -1 and current_element < left:
                is_peak = False

            if right != -1 and current_element < right:
                is_peak = False

            # If it's a peak, return its coordinates
            if is_peak:
                return [row_index, column_index]

    return []

Big(O) Analysis

Time Complexity

O(m*n) – The brute force approach iterates through each element in the m x n grid. For each element, a constant number of comparisons (up to 4) are performed with its neighbors to determine if it is a peak. Since we examine all m*n elements in the grid, the overall time complexity is O(m*n).

Space Complexity

O(1) – The brute force algorithm iterates through the input grid, comparing each element with its neighbors. The plain English explanation doesn't mention the creation of any auxiliary data structures like lists, maps, or arrays to store intermediate results or track visited cells. The algorithm only uses a fixed number of variables to store the row and column indices during iteration, regardless of the grid's dimensions. Thus, the space complexity remains constant, independent of the input size N (where N represents the total number of elements in the grid).

Optimal Solution

Approach

The core idea is to repeatedly narrow down the search area until we find a peak. We accomplish this by focusing on rows and columns with the greatest potential to contain a peak element.

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

Find the largest element in the middle column of the grid.
Check if this element is bigger than its neighbors in the rows to its left and right. If it is, then we have found a peak element, and we are done.
If the element is not a peak, compare the element to its neighbor in the row (left or right) with a larger value.
Discard the half of the grid that does not contain the bigger neighbor. This means that we consider the bigger neighbor as part of a smaller grid where the peak element exists.
Repeat these steps in the smaller grid (find the largest element in the middle column, check if it's a peak, and discard half of the grid) until a peak is found.

Code Implementation

def find_peak_grid(matrix):
    row_count = len(matrix)
    column_count = len(matrix[0])

    left_boundary = 0
    right_boundary = column_count - 1

    while left_boundary <= right_boundary:
        middle_column = (left_boundary + right_boundary) // 2

        #Find the row index with the largest element in the middle column
        max_row_index = 0
        for row_index in range(1, row_count):
            if matrix[row_index][middle_column] > matrix[max_row_index][middle_column]:
                max_row_index = row_index

        #Check if the largest element is a peak
        is_left_bigger = middle_column > 0 and matrix[max_row_index][middle_column - 1] > matrix[max_row_index][middle_column]
        is_right_bigger = middle_column < column_count - 1 and matrix[max_row_index][middle_column + 1] > matrix[max_row_index][middle_column]

        # If the current element is a peak, return the location
        if not is_left_bigger and not is_right_bigger:
            return [max_row_index, middle_column]

        #Eliminate half of the matrix where the peak cannot exist
        if is_left_bigger:
            right_boundary = middle_column - 1

        #Eliminate half of the matrix where the peak cannot exist
        else:
            left_boundary = middle_column + 1

    return None

Big(O) Analysis

Time Complexity

O(m log n) – The algorithm iteratively reduces the search space by half in each step based on either rows or columns. Assuming m rows and n columns, the algorithm repeatedly finds the maximum in the middle column which takes O(m) time. Then it compares the element with its neighbors, and discards half of the columns. This halving happens log n times (binary search on columns). Therefore, the overall time complexity is approximately O(m log n) because in each of the log n iterations (based on the number of columns), we are iterating through all m rows to find the maximum.

Space Complexity

O(1) – The algorithm described operates primarily on the input grid in place. It involves finding the largest element in the middle column and comparing it to its neighbors. These operations utilize a few variables for indexing and comparison, which take up a constant amount of space regardless of the input grid's dimensions (rows and columns). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty matrix	Return null or throw an IllegalArgumentException, as a peak cannot exist in an empty matrix.
Matrix with only one row or one column	Iterate through the single row or column to find the maximum element, which is the peak.
Matrix with only one element	Return the coordinates of that single element as the peak.
All elements in the matrix are the same	Any element can be considered a peak, so return the coordinates of the first element.
Large matrix (performance considerations)	Binary search approach on rows or columns ensures logarithmic time complexity for large matrices.
Matrix with negative numbers	The algorithm compares values, so negative numbers do not affect the correctness of the peak finding logic.
Multiple peak elements exist	The algorithm is designed to find and return any one valid peak element, not necessarily all of them.
Integer overflow when comparing values	Using the correct comparison operators avoids potential integer overflow issues.

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 (number of rows and columns) of the matrix, and what are the upper bounds for those dimensions?
What is the range of integer values that can be present in the matrix? Can they be negative?
If there are multiple peak elements, is it acceptable to return the coordinates of any one of them?
Is a matrix guaranteed to have at least one row and one column (i.e., can it be empty)?
Is a peak element defined as strictly greater than its immediate neighbors (up, down, left, right), or can it be greater than or equal?

Brute Force Solution

Approach

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

Look at the very first element in the grid.
Compare this element to all its neighbors (up, down, left, right).
If the element is greater than or equal to all of its neighbors, then it's a peak, and we're done.
If not, move on to the next element in the grid.
Repeat this process for every element in the grid.
If we go through the entire grid and find no peak, it means we made a mistake in our assumptions about the grid structure (though this shouldn't happen given the problem constraints).

Code Implementation

def find_peak_element_ii_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            current_element = matrix[row_index][column_index]

            # Check neighbors: up, down, left, right
            up = matrix[row_index - 1][column_index] if row_index > 0 else -1

            down = matrix[row_index + 1][column_index] if row_index < number_of_rows - 1 else -1

            left = matrix[row_index][column_index - 1] if column_index > 0 else -1

            right = matrix[row_index][column_index + 1] if column_index < number_of_columns - 1 else -1

            # Need to handle edge cases where neighbors don't exist
            is_peak = True

            if up != -1 and current_element < up:
                is_peak = False

            if down != -1 and current_element < down:
                is_peak = False

            if left != -1 and current_element < left:
                is_peak = False

            if right != -1 and current_element < right:
                is_peak = False

            # If it's a peak, return its coordinates
            if is_peak:
                return [row_index, column_index]

    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to repeatedly narrow down the search area until we find a peak. We accomplish this by focusing on rows and columns with the greatest potential to contain a peak element.

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

Find the largest element in the middle column of the grid.
Check if this element is bigger than its neighbors in the rows to its left and right. If it is, then we have found a peak element, and we are done.
If the element is not a peak, compare the element to its neighbor in the row (left or right) with a larger value.
Discard the half of the grid that does not contain the bigger neighbor. This means that we consider the bigger neighbor as part of a smaller grid where the peak element exists.
Repeat these steps in the smaller grid (find the largest element in the middle column, check if it's a peak, and discard half of the grid) until a peak is found.

Code Implementation

def find_peak_grid(matrix):
    row_count = len(matrix)
    column_count = len(matrix[0])

    left_boundary = 0
    right_boundary = column_count - 1

    while left_boundary <= right_boundary:
        middle_column = (left_boundary + right_boundary) // 2

        #Find the row index with the largest element in the middle column
        max_row_index = 0
        for row_index in range(1, row_count):
            if matrix[row_index][middle_column] > matrix[max_row_index][middle_column]:
                max_row_index = row_index

        #Check if the largest element is a peak
        is_left_bigger = middle_column > 0 and matrix[max_row_index][middle_column - 1] > matrix[max_row_index][middle_column]
        is_right_bigger = middle_column < column_count - 1 and matrix[max_row_index][middle_column + 1] > matrix[max_row_index][middle_column]

        # If the current element is a peak, return the location
        if not is_left_bigger and not is_right_bigger:
            return [max_row_index, middle_column]

        #Eliminate half of the matrix where the peak cannot exist
        if is_left_bigger:
            right_boundary = middle_column - 1

        #Eliminate half of the matrix where the peak cannot exist
        else:
            left_boundary = middle_column + 1

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return null or throw an IllegalArgumentException, as a peak cannot exist in an empty matrix.
Matrix with only one row or one column	Iterate through the single row or column to find the maximum element, which is the peak.
Matrix with only one element	Return the coordinates of that single element as the peak.
All elements in the matrix are the same	Any element can be considered a peak, so return the coordinates of the first element.
Large matrix (performance considerations)	Binary search approach on rows or columns ensures logarithmic time complexity for large matrices.
Matrix with negative numbers	The algorithm compares values, so negative numbers do not affect the correctness of the peak finding logic.
Multiple peak elements exist	The algorithm is designed to find and return any one valid peak element, not necessarily all of them.
Integer overflow when comparing values	Using the correct comparison operators avoids potential integer overflow issues.