Jobs

Interviews

Discussions

Matrix Cells in Distance Order

Easy

Asked by:

3 views

Topics:

Arrays

You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.

The distance between two cells (r₁, c₁) and (r₂, c₂) is |r₁ - r₂| + |c₁ - c₂|.

Example 1:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Constraints:

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

Try coding it in LeetCode

Matrix Cells in Distance Order

Easy

Asked by:

3 views

Topics:

Arrays

You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

The distance between two cells (r₁, c₁) and (r₂, c₂) is |r₁ - r₂| + |c₁ - c₂|.

Example 1:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Constraints:

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

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 maximum possible values for `rows` and `cols`? This will help me understand the scale of the matrix.
Can `rowCenter` and `colCenter` ever be outside the bounds of the matrix (i.e., less than 0 or greater than or equal to `rows` or `cols`, respectively)?
Is the order of cells with the same Manhattan distance important? If multiple cells have the same distance, can they be in any order?
Could `rows` or `cols` be zero?
What data type should be used for the return value? Should I return a 2D array of integers (int[][]) representing the coordinates?

Brute Force Solution

Approach

We want to list all the squares in a grid based on how far they are from a starting point. The brute force way means we'll just look at every square, calculate its distance, and then sort them all.

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

Go through each square in the grid, one at a time.
For each square, figure out how far it is from the starting square using a simple distance formula.
Keep a list of each square and its corresponding distance.
Once you've checked every square in the grid, sort the entire list based on those distances from smallest to largest.
The sorted list is the final answer, showing all squares from nearest to farthest from the starting square.

Code Implementation

def matrix_cells_in_distance_order_brute_force(
    number_of_rows, number_of_columns, starting_row, starting_column):

    cell_distances = []

    # Iterate through all cells
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):

            # Calculate Manhattan distance to starting point
            distance = abs(row_index - starting_row) + \
                       abs(column_index - starting_column)
            
            cell_distances.append(([row_index, column_index], distance))

    # Sort cells based on distances
    cell_distances.sort(key=lambda item: item[1])

    # Extract cells from sorted list
    result = [cell for cell, _ in cell_distances]

    return result

Big(O) Analysis

Time Complexity

O(R * C * log(R * C)) – The algorithm iterates through each cell in the R x C matrix to calculate the Manhattan distance from (r0, c0). This takes O(R * C) time. Then, it sorts the cells based on their distances. Sorting R * C elements using a comparison-based sorting algorithm takes O(R * C * log(R * C)) time. The overall time complexity is dominated by the sorting step, resulting in O(R * C * log(R * C)).

Space Complexity

O(R * C) – The brute force solution, as described, creates a list containing all cells in the grid along with their calculated distances from the starting cell. Since we iterate through each square in the grid (R rows and C columns), this list stores R * C elements. We sort this list, but the sorting is done in place, so it does not increase the auxiliary space. Therefore, the dominant auxiliary space is the list used to store cells and distances, resulting in a space complexity of O(R * C), where R is the number of rows and C is the number of columns.

Optimal Solution

Approach

The most efficient way to sort the matrix cells by distance is to use a process similar to how ripples expand in water. We start from the center and expand outwards in layers, adding cells to our ordered list as we encounter them.

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

Imagine the center cell as the starting point of expanding circles.
Create a way to visit cells in order of their distance from the center. Think of expanding in squares or diamonds around the center, rather than true circles.
As you expand, check if each cell you encounter is within the boundaries of the matrix.
If a cell is valid (within the matrix), add it to a list.
Continue expanding outwards until you have visited every cell in the matrix. The list will now contain all cells sorted by their distance from the center.

Code Implementation

def matrix_cells_in_distance_order(number_of_rows, number_of_columns, row_center, column_center):
    result = []
    maximum_distance = max(row_center, number_of_rows - 1 - row_center) + max(column_center, number_of_columns - 1 - column_center)

    # Iterate through all possible distances from the center.
    for current_distance in range(maximum_distance + 1):
        # Iterate through all cells to find those at the current distance.
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                if abs(row_index - row_center) + abs(column_index - column_center) == current_distance:

                    # Only add cells that match the current distance.
                    result.append([row_index, column_index])

    return result

def matrix_cells_in_distance_order_optimal(number_of_rows, number_of_columns, row_center, column_center):
    result_list = []
    visited = set()
    queue = [(row_center, column_center)]
    visited.add((row_center, column_center))

    # Breadth-first search to expand outwards from the center.
    while queue:
        row_index, column_index = queue.pop(0)
        result_list.append([row_index, column_index])

        # Explore adjacent cells in all four directions
        for delta_row, delta_column in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_row_index = row_index + delta_row
            new_column_index = column_index + delta_column

            # Ensures we only process cells within the matrix.
            if 0 <= new_row_index < number_of_rows and 0 <= new_column_index < number_of_columns and (new_row_index, new_column_index) not in visited:

                # Add valid and unvisited neighbours to the queue
                queue.append((new_row_index, new_column_index))
                visited.add((new_row_index, new_column_index))

    return result_list

def matrix_cells_in_distance_order_alt(number_of_rows, number_of_columns, row_center, column_center):
    cells = []
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            cells.append([row_index, column_index])

    # Sort based on Manhattan distance from the center.
    cells.sort(key=lambda cell: abs(cell[0] - row_center) + abs(cell[1] - column_center))

    return cells

def matrix_cells_in_distance_order_gen(number_of_rows, number_of_columns, row_center, column_center):
    all_cells = [(row, column) for row in range(number_of_rows) for column in range(number_of_columns)]

    # Sort cells based on Manhattan distance from the center.
    all_cells.sort(key=lambda cell: abs(cell[0] - row_center) + abs(cell[1] - column_center))

    return all_cells

def matrix_cells_in_distance_order_diamond(number_of_rows, number_of_columns, row_center, column_center):
    result = []
    for distance in range(number_of_rows + number_of_columns):
        for i in range(-distance, distance + 1):
            row_coordinate = row_center + i
            column_coordinate = column_center + distance - abs(i)

            # Check if cell is within the matrix bounds
            if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:
                result.append([row_coordinate, column_coordinate])

            # To avoid duplicates for overlapping diamonds.
            if distance != 0:
                row_coordinate = row_center + i
                column_coordinate = column_center - distance + abs(i)
                if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:

                    # Add cell to results
                    result.append([row_coordinate, column_coordinate])
    return result

def matrix_cells_in_distance_order_expanding_ripples(number_of_rows, number_of_columns, row_center, column_center):
    result_list = []
    maximum_distance = max(row_center, number_of_rows - 1 - row_center) + max(column_center, number_of_columns - 1 - column_center)

    # Expands outwards from the center, processing cells at each distance
    for current_distance in range(maximum_distance + 1):
        for row_delta in range(-current_distance, current_distance + 1):
            column_delta = current_distance - abs(row_delta)
            
            for col_multiplier in [-1, 1]:
                row_coordinate = row_center + row_delta
                column_coordinate = column_center + column_delta * col_multiplier

                # Ensure the cell is within the matrix boundaries
                if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:

                    # Add cell to result
                    result_list.append([row_coordinate, column_coordinate])

    return result_list

def matrix_cells_in_distance_order_optimized(number_of_rows, number_of_columns, row_center, column_center):
    maximum_distance = number_of_rows + number_of_columns
    bucket_list = [[] for _ in range(maximum_distance)]

    # Place each cell into its corresponding bucket based on distance.
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            distance = abs(row_index - row_center) + abs(column_index - column_center)
            bucket_list[distance].append([row_index, column_index])

    result_list = []

    # Concatenate the buckets to get the sorted result
    for bucket in bucket_list:
        result_list.extend(bucket)
    return result_list

def matrix_cells_in_distance_order(rows, cols, rCenter, cCenter):
    # Calculate maximum possible distance
    max_dist = rows + cols
    buckets = [[] for _ in range(max_dist)]

    # Populate buckets based on Manhattan distance.
    for r in range(rows):
        for c in range(cols):
            dist = abs(r - rCenter) + abs(c - cCenter)
            buckets[dist].append([r, c])

    result = []
    # Concatenate buckets to get result in distance order.
    for bucket in buckets:
        result.extend(bucket)

    return result

Big(O) Analysis

Time Complexity

O(R * C) – The algorithm visits cells in expanding layers from the center until all R * C cells of the matrix are visited. Although the expansion conceptually resembles checking cells within increasing distances, the core operation involves iterating through potential cell coordinates within a bounding box around the center. The bounding box expands until it encompasses the entire matrix. In the worst case, we examine a number of cell positions roughly proportional to the total number of cells in the matrix, represented by R * C, where R is the number of rows and C is the number of columns. Therefore, the time complexity is O(R * C).

Space Complexity

O(R * C) – The algorithm creates a list to store the matrix cells in distance order. In the worst case, this list will contain all the cells in the matrix. Therefore, the space required for this list is proportional to the number of rows (R) multiplied by the number of columns (C). Since the algorithm visits each cell in the matrix, we are keeping track of each cell in our result list.

Edge Cases

Case	How to Handle
rows or cols is zero	Return an empty list as a matrix with zero rows or columns is invalid.
rows or cols is one	The algorithm should function correctly for matrices with a single row or column.
rowCenter or colCenter is out of bounds (negative or exceeding dimensions)	Clamp rowCenter and colCenter to valid ranges within the matrix dimensions.
Large rows and cols leading to potential integer overflow in distance calculation	Use a data type large enough to hold the Manhattan distance without overflow (e.g., long).
All cells are equidistant from the center (e.g., center at corner, square matrix)	The sorting algorithm must handle cases with many identical distances correctly (should maintain some deterministic order).
rows and cols are very large potentially leading to memory constraints when creating the list of cells	Consider an iterative approach that generates cells on demand instead of storing all cells initially to avoid O(rows*cols) memory use.
rows and cols are equal to 1	Return a list containing only the center cell (rowCenter, colCenter).
rowCenter and colCenter represent a cell at the boundary of the matrix	The algorithm should correctly calculate distances even when the center cell is at the edge.

rows or cols is zero

How to Handle:

Return an empty list as a matrix with zero rows or columns is invalid.

rows or cols is one

How to Handle:

The algorithm should function correctly for matrices with a single row or column.

rowCenter or colCenter is out of bounds (negative or exceeding dimensions)

How to Handle:

Clamp rowCenter and colCenter to valid ranges within the matrix dimensions.

Large rows and cols leading to potential integer overflow in distance calculation

How to Handle:

Use a data type large enough to hold the Manhattan distance without overflow (e.g., long).

All cells are equidistant from the center (e.g., center at corner, square matrix)

How to Handle:

The sorting algorithm must handle cases with many identical distances correctly (should maintain some deterministic order).

rows and cols are very large potentially leading to memory constraints when creating the list of cells

How to Handle:

Consider an iterative approach that generates cells on demand instead of storing all cells initially to avoid O(rows*cols) memory use.

rows and cols are equal to 1

How to Handle:

Return a list containing only the center cell (rowCenter, colCenter).

rowCenter and colCenter represent a cell at the boundary of the matrix

How to Handle:

The algorithm should correctly calculate distances even when the center cell is at the edge.

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 maximum possible values for `rows` and `cols`? This will help me understand the scale of the matrix.
Can `rowCenter` and `colCenter` ever be outside the bounds of the matrix (i.e., less than 0 or greater than or equal to `rows` or `cols`, respectively)?
Is the order of cells with the same Manhattan distance important? If multiple cells have the same distance, can they be in any order?
Could `rows` or `cols` be zero?
What data type should be used for the return value? Should I return a 2D array of integers (int[][]) representing the coordinates?

Brute Force Solution

Approach

We want to list all the squares in a grid based on how far they are from a starting point. The brute force way means we'll just look at every square, calculate its distance, and then sort them all.

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

Go through each square in the grid, one at a time.
For each square, figure out how far it is from the starting square using a simple distance formula.
Keep a list of each square and its corresponding distance.
Once you've checked every square in the grid, sort the entire list based on those distances from smallest to largest.
The sorted list is the final answer, showing all squares from nearest to farthest from the starting square.

Code Implementation

def matrix_cells_in_distance_order_brute_force(
    number_of_rows, number_of_columns, starting_row, starting_column):

    cell_distances = []

    # Iterate through all cells
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):

            # Calculate Manhattan distance to starting point
            distance = abs(row_index - starting_row) + \
                       abs(column_index - starting_column)
            
            cell_distances.append(([row_index, column_index], distance))

    # Sort cells based on distances
    cell_distances.sort(key=lambda item: item[1])

    # Extract cells from sorted list
    result = [cell for cell, _ in cell_distances]

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the center cell as the starting point of expanding circles.
Create a way to visit cells in order of their distance from the center. Think of expanding in squares or diamonds around the center, rather than true circles.
As you expand, check if each cell you encounter is within the boundaries of the matrix.
If a cell is valid (within the matrix), add it to a list.
Continue expanding outwards until you have visited every cell in the matrix. The list will now contain all cells sorted by their distance from the center.

Code Implementation

def matrix_cells_in_distance_order(number_of_rows, number_of_columns, row_center, column_center):
    result = []
    maximum_distance = max(row_center, number_of_rows - 1 - row_center) + max(column_center, number_of_columns - 1 - column_center)

    # Iterate through all possible distances from the center.
    for current_distance in range(maximum_distance + 1):
        # Iterate through all cells to find those at the current distance.
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                if abs(row_index - row_center) + abs(column_index - column_center) == current_distance:

                    # Only add cells that match the current distance.
                    result.append([row_index, column_index])

    return result

def matrix_cells_in_distance_order_optimal(number_of_rows, number_of_columns, row_center, column_center):
    result_list = []
    visited = set()
    queue = [(row_center, column_center)]
    visited.add((row_center, column_center))

    # Breadth-first search to expand outwards from the center.
    while queue:
        row_index, column_index = queue.pop(0)
        result_list.append([row_index, column_index])

        # Explore adjacent cells in all four directions
        for delta_row, delta_column in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_row_index = row_index + delta_row
            new_column_index = column_index + delta_column

            # Ensures we only process cells within the matrix.
            if 0 <= new_row_index < number_of_rows and 0 <= new_column_index < number_of_columns and (new_row_index, new_column_index) not in visited:

                # Add valid and unvisited neighbours to the queue
                queue.append((new_row_index, new_column_index))
                visited.add((new_row_index, new_column_index))

    return result_list

def matrix_cells_in_distance_order_alt(number_of_rows, number_of_columns, row_center, column_center):
    cells = []
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            cells.append([row_index, column_index])

    # Sort based on Manhattan distance from the center.
    cells.sort(key=lambda cell: abs(cell[0] - row_center) + abs(cell[1] - column_center))

    return cells

def matrix_cells_in_distance_order_gen(number_of_rows, number_of_columns, row_center, column_center):
    all_cells = [(row, column) for row in range(number_of_rows) for column in range(number_of_columns)]

    # Sort cells based on Manhattan distance from the center.
    all_cells.sort(key=lambda cell: abs(cell[0] - row_center) + abs(cell[1] - column_center))

    return all_cells

def matrix_cells_in_distance_order_diamond(number_of_rows, number_of_columns, row_center, column_center):
    result = []
    for distance in range(number_of_rows + number_of_columns):
        for i in range(-distance, distance + 1):
            row_coordinate = row_center + i
            column_coordinate = column_center + distance - abs(i)

            # Check if cell is within the matrix bounds
            if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:
                result.append([row_coordinate, column_coordinate])

            # To avoid duplicates for overlapping diamonds.
            if distance != 0:
                row_coordinate = row_center + i
                column_coordinate = column_center - distance + abs(i)
                if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:

                    # Add cell to results
                    result.append([row_coordinate, column_coordinate])
    return result

def matrix_cells_in_distance_order_expanding_ripples(number_of_rows, number_of_columns, row_center, column_center):
    result_list = []
    maximum_distance = max(row_center, number_of_rows - 1 - row_center) + max(column_center, number_of_columns - 1 - column_center)

    # Expands outwards from the center, processing cells at each distance
    for current_distance in range(maximum_distance + 1):
        for row_delta in range(-current_distance, current_distance + 1):
            column_delta = current_distance - abs(row_delta)
            
            for col_multiplier in [-1, 1]:
                row_coordinate = row_center + row_delta
                column_coordinate = column_center + column_delta * col_multiplier

                # Ensure the cell is within the matrix boundaries
                if 0 <= row_coordinate < number_of_rows and 0 <= column_coordinate < number_of_columns:

                    # Add cell to result
                    result_list.append([row_coordinate, column_coordinate])

    return result_list

def matrix_cells_in_distance_order_optimized(number_of_rows, number_of_columns, row_center, column_center):
    maximum_distance = number_of_rows + number_of_columns
    bucket_list = [[] for _ in range(maximum_distance)]

    # Place each cell into its corresponding bucket based on distance.
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            distance = abs(row_index - row_center) + abs(column_index - column_center)
            bucket_list[distance].append([row_index, column_index])

    result_list = []

    # Concatenate the buckets to get the sorted result
    for bucket in bucket_list:
        result_list.extend(bucket)
    return result_list

def matrix_cells_in_distance_order(rows, cols, rCenter, cCenter):
    # Calculate maximum possible distance
    max_dist = rows + cols
    buckets = [[] for _ in range(max_dist)]

    # Populate buckets based on Manhattan distance.
    for r in range(rows):
        for c in range(cols):
            dist = abs(r - rCenter) + abs(c - cCenter)
            buckets[dist].append([r, c])

    result = []
    # Concatenate buckets to get result in distance order.
    for bucket in buckets:
        result.extend(bucket)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
rows or cols is zero	Return an empty list as a matrix with zero rows or columns is invalid.
rows or cols is one	The algorithm should function correctly for matrices with a single row or column.
rowCenter or colCenter is out of bounds (negative or exceeding dimensions)	Clamp rowCenter and colCenter to valid ranges within the matrix dimensions.
Large rows and cols leading to potential integer overflow in distance calculation	Use a data type large enough to hold the Manhattan distance without overflow (e.g., long).
All cells are equidistant from the center (e.g., center at corner, square matrix)	The sorting algorithm must handle cases with many identical distances correctly (should maintain some deterministic order).
rows and cols are very large potentially leading to memory constraints when creating the list of cells	Consider an iterative approach that generates cells on demand instead of storing all cells initially to avoid O(rows*cols) memory use.
rows and cols are equal to 1	Return a list containing only the center cell (rowCenter, colCenter).
rowCenter and colCenter represent a cell at the boundary of the matrix	The algorithm should correctly calculate distances even when the center cell is at the edge.

rows or cols is zero

How to Handle:

Return an empty list as a matrix with zero rows or columns is invalid.

rows or cols is one

How to Handle:

The algorithm should function correctly for matrices with a single row or column.

rowCenter or colCenter is out of bounds (negative or exceeding dimensions)

How to Handle:

Clamp rowCenter and colCenter to valid ranges within the matrix dimensions.

Large rows and cols leading to potential integer overflow in distance calculation

How to Handle:

Use a data type large enough to hold the Manhattan distance without overflow (e.g., long).

All cells are equidistant from the center (e.g., center at corner, square matrix)

How to Handle:

The sorting algorithm must handle cases with many identical distances correctly (should maintain some deterministic order).

rows and cols are very large potentially leading to memory constraints when creating the list of cells

How to Handle:

Consider an iterative approach that generates cells on demand instead of storing all cells initially to avoid O(rows*cols) memory use.

rows and cols are equal to 1

How to Handle:

Return a list containing only the center cell (rowCenter, colCenter).

rowCenter and colCenter represent a cell at the boundary of the matrix

How to Handle:

The algorithm should correctly calculate distances even when the center cell is at the edge.