Exit Point in a Matrix

Intuition

A ray starts at the top-left cell and moves through the matrix according to local cell values. A cell with 1 forces a clockwise turn after stepping in the current direction; a cell with 0 keeps the previous direction. Each 1 is cleared to 0 when visited, so the walk eventually exits the grid. The answer is the last cell still inside the matrix before the ray leaves.

Algorithm

1Start at (0, 0) with direction index i = 0 and track the last in-bounds cell.
2While the current position is inside the matrix, save it as the tentative exit cell.
3If mat[row][col] is 0, move using the previous direction (i - 1) modulo 4.
4If mat[row][col] is 1, set it to 0, move in direction i, then set i = (i + 1) % 4.
5When the next step would leave the grid, return the saved exit cell coordinates.

Example Walkthrough

Input: mat = [[1,0,0,1],[0,0,1,0],[0,0,0,0]]

1.Begin at (0,0), which contains 1: mark it 0, move in direction 0, then turn clockwise.
2.On empty cells, continue straight using the previous direction until another 1 is hit.
3.Each visited 1 is cleared, so the path cannot loop forever on the same obstacle.
4.The last valid position before leaving the grid is recorded as the exit point.

Output: [1, 3]

Common Pitfalls

•Store the exit cell before attempting the move that goes out of bounds.
•On a 0 cell, use the previous direction (i - 1 + 4) % 4, not the current direction i.
•Mark 1-cells as 0 when visited so each obstacle affects the path only once.

Exit Point in a Matrix.java

Java

// Approach: Simulate ray movement from (0,0). On a 1, move in the current direction and turn
// clockwise; on a 0, keep the previous direction. The exit cell is the last in-bounds position.
// Time: O(n * m) Space: O(1)

import java.util.*;

class Solution {

    public List<Integer> exitPoint(int[][] mat) {
        int tempExitRow = -1;
        int tempExitCol = -1;

        int currRow = 0;
        int currCol = 0;

        int n = mat.length;
        int m = mat[0].length;

        int[][] clockDir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

        int i = 0;

        while (currRow >= 0 && currRow < n && currCol >= 0 && currCol < m) {
            tempExitRow = currRow;
            tempExitCol = currCol;

            if (mat[currRow][currCol] == 0) {
                int k = (i - 1 + 4) % 4;
                currRow += clockDir[k][0];
                currCol += clockDir[k][1];
            } else {
                mat[currRow][currCol] = 0;
                currRow += clockDir[i][0];
                currCol += clockDir[i][1];
                i = (i + 1) % 4;
            }
        }
        List<Integer> exitCell = new ArrayList<>();
        exitCell.add(tempExitRow);
        exitCell.add(tempExitCol);

        return exitCell;
    }
}

Was this solution helpful?