algoadvance

Leetcode 1030. Matrix Cells in Distance Order

Problem Statement

You are given four integers rows, cols, rCenter, and cCenter. There is a rows x cols matrix and you are sitting in the cell (rCenter, cCenter).

Return the matrix cells in the order of their distances from (rCenter, cCenter) — ordered from the smallest distance to the largest distance. Here, the distance between two cells (r1, c1) and (r2, c2) is defined as the Manhattan Distance: |r1 - r2| + |c1 - c2|.

Clarifying Questions

  1. What is the range of values for rows, cols, rCenter, and cCenter?
    • 1 <= rows, cols <= 100
    • 0 <= rCenter < rows
    • 0 <= cCenter < cols
  2. Can multiple cells have the same distance to (rCenter, cCenter)?
    • Yes, multiple cells can have the same distance to the center cell.
  3. How should cells with the same distance be ordered?
    • Any order works as long as cells are sorted by distance.

With these clarifications, let’s proceed to the solution.

Strategy

  1. Generate All Cells: Create a list of all cells with their coordinates.
  2. Calculate Distances: Compute the Manhattan Distance of each cell from (rCenter, cCenter).
  3. Sort Cells: Sort the list of cells based on their distances.
  4. Return the Result: Return the sorted list of cells.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> cells;
        
        // Generate all cells in the matrix
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                cells.push_back({r, c});
            }
        }
        
        // Sort cells based on Manhattan distance
        sort(cells.begin(), cells.end(), [&](const vector<int>& a, const vector<int>& b) {
            int distA = abs(a[0] - rCenter) + abs(a[1] - cCenter);
            int distB = abs(b[0] - rCenter) + abs(b[1] - cCenter);
            return distA < distB;
        });
        
        return cells;
    }
};

Time Complexity

Overall, the time complexity is dominated by the sorting step, so it is O((rows * cols) * log(rows * cols)).

Space Complexity

Thus, the space complexity is O(rows * cols).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI