algoadvance

Leetcode 1030. Matrix Cells in Distance Order

Problem Statement

Given the integers R and C denoting the dimensions of a matrix, and the integers r0 and c0 denoting the coordinates of a cell in the matrix, return the coordinates of all cells in the matrix, sorted by their distance from (r0, c0). The distance between two cells (r1, c1) and (r2, c2) is calculated as |r1 - r2| + |c1 - c2| (Manhattan Distance).

Clarifying Questions

  1. Input Constraints:
    • 1 <= R, C <= 100
    • 0 <= r0 < R
    • 0 <= c0 < C
  2. Output Format:
    • A list of lists, where each inner list contains two integers indicating the coordinates [row, col].
  3. Expected Output:
    • All cells in the matrix presented in ascending order of their distance from (r0, c0).

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MatrixCellsInDistanceOrder {

    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] result = new int[R * C][2];
        int index = 0;
        
        // Collect all the cells in the matrix
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                result[index++] = new int[]{r, c};
            }
        }
        
        // Sort the cells based on their distance from (r0, c0)
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                int dist1 = Math.abs(a[0] - r0) + Math.abs(a[1] - c0);
                int dist2 = Math.abs(b[0] - r0) + Math.abs(b[1] - c0);
                return Integer.compare(dist1, dist2);
            }
        });
        
        return result;
    }

    public static void main(String[] args) {
        MatrixCellsInDistanceOrder solution = new MatrixCellsInDistanceOrder();
        int[][] result = solution.allCellsDistOrder(2, 3, 1, 2);
        
        for (int[] cell : result) {
            System.out.println(Arrays.toString(cell));
        }
    }
}

Strategy

  1. Matrix Generation:
    • Create an R x C matrix and populate it with the indices of all the cells. This is done using nested loops where each cell’s coordinates are stored in an int[][].
  2. Sorting:
    • Use a custom comparator to sort the cells based on their Manhattan distance from the given (r0, c0) coordinates. The Manhattan distance is calculated using the formula |r1 - r0| + |c1 - c0| for each cell.
  3. Return the Result:
    • Return the sorted array of coordinates.

Time Complexity

Hence, the overall time complexity is O((R * C) log(R * C)) when considering both matrix generation and sorting steps.

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