NewThe Learning module is now liveSee what's new

You have an unbounded 2D matrix where each position can either be empty or hold a point. You need to implement three functions:

  • void addPoint(int row, int col) to place a point at the given coordinates
  • boolean isConnected(int[] point1, int[] point2) to check if two points can reach each other
  • int getMinSteps(int[] start, int[] end) to find the shortest path between two points

A move from one point to another is considered valid if both points lie in the same row or the same column, and each valid move costs exactly one step. If it is impossible to find a path, return -1.

Constraints: You can assume integer coordinates for the matrix and no upper limit to how many points can be added. All points exist in an unbounded 2D space, and each coordinate pair is unique.

Example

Input: ["UnboundMatrix", "addPoint", "addPoint", "addPoint", "isConnected", "isConnected", "isConnected", "getMinSteps", "getMinSteps", "getMinSteps"] [[ ], [0, 2], [1, 2], [1, 4], [[0, 2], [1, 4]], [[1, 2], [1, 4]], [[0, 0], [1, 4]], [[0, 2], [1, 4]], [[1, 2], [1, 4]], [[0, 0], [1, 4]]]

Output: [nul, null, null, null, true, true, false, 2, 1, -1]

Explanation:

x/y01234
0--X--
1--X-X
2-----
  • UnboundMatrix matrix = new UnboundMatrix();
  • matrix.addPoint(0, 2); // Add a point at (0, 2).
  • matrix.addPoint(1, 2); // Add a point at (1, 2).
  • matrix.addPoint(1, 4); // Add a point at (1, 4).
  • matrix.isConnected([0, 2], [1, 4]); // Returns true. Points (0, 2) and (1, 4) are connected via (1, 2).
  • matrix.isConnected([1, 2], [1, 4]); // Returns true. Points (1, 2) and (1, 4) are directly connected.
  • matrix.isConnected([0, 0], [1, 4]); // Returns false. No path connects (0, 0) to (1, 4).
  • matrix.getMinSteps([0, 2], [1, 4]); // Returns 2. Path: (0, 2) → (1, 2) → (1, 4).
  • matrix.getMinSteps([1, 2], [1, 4]); // Returns 1. Path: (1, 2) → (1, 4).
  • matrix.getMinSteps([0, 0], [1, 4]); // Returns -1. No valid path exists from (0, 0) to (1, 4)

Accepted
764/2.1k
Acceptance Rate36.0%
Test Cases
Input
Output
Expected