We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Matrix Cells in Distance Order

Number: 1094

Difficulty: Easy

Paid? No

Companies: Yahoo

Problem Description

Given a matrix with dimensions rows x cols and a center cell (rCenter, cCenter), return the coordinates of all cells sorted by their Manhattan distance (|r1 - rCenter| + |c1 - cCenter|) from the center cell. The order must start from the smallest distance and go to the largest.

Key Insights

  • Calculate the Manhattan distance for each cell from the given center.
  • Store each cell along with its distance.
  • Sort the cells based on the calculated distance.
  • The brute force approach is acceptable given the constraints (matrix dimensions up to 100x100).

Space and Time Complexity

Time Complexity: O(rows * cols * log(rows * cols)) due to sorting all cells. Space Complexity: O(rows * cols) to store the coordinates of each cell.

Solution

We iterate through every cell in the matrix and compute its Manhattan distance from the given center (rCenter, cCenter). We then store each cell’s coordinates along with its computed distance in a list. Once we have the complete list, we sort it using the distance as the key. Finally, we extract and return only the cell coordinates in the sorted order. This approach leverages simple iteration, distance computation, and sorting.

Code Solutions

# Function to get cells sorted by distance from (rCenter, cCenter)
def allCellsDistOrder(rows, cols, rCenter, cCenter):
    cells = []
    # Iterate through each cell in the matrix
    for row in range(rows):
        for col in range(cols):
            # Calculate Manhattan distance for current cell
            dist = abs(row - rCenter) + abs(col - cCenter)
            # Append cell coordinates with computed distance
            cells.append((dist, row, col))
    
    # Sort cells by the Manhattan distance
    cells.sort(key=lambda x: x[0])
    
    # Extract sorted cell coordinates (ignoring the distance)
    return [[row, col] for (dist, row, col) in cells]

# Example usage:
print(allCellsDistOrder(2, 3, 1, 2))
← Back to All Questions