Exit Point

Given a binary matrix of size N x M, you enter the matrix at cell (0, 0) in the left to the right direction. Whenever encountering a 0  retain in the same direction if encountered a 1 change direction to the right of the current direction and change that 1 value to 0,  find out exit point from the Matrix.

Examples: 

Input: matrix = {{0, 1, 0},

                          {0, 1, 1},

                          {0, 0, 0}}
Output: 1 0
Explanation: 
Enter the matrix at 0, 0 -> then move towards 0, 1 ->  1 is encountered -> turn right towards 1, 1 -> again 1 is encountered -> turn right again towards 1, 0 -> now, the boundary of matrix will be crossed ->hence, exit point reached at 1, 0.

package jan22_2D_Array;

public class ExitPoint {
    public static void main(String[] args) {

        int[][] arr = {
                {0, 0, 1, 0},
                {1, 0, 0, 1},
                {0, 0, 0, 1},
                {1, 0, 1, 0}
        };

        /*
        East = 0 i.e. (i, j+1)
        South = 1 i.e. (i+1, j)
        West = 2 i.e. (i, j-1)
        North = 3 i.e. (i-1, j)
        */

        int direction = 0;
        int i = 0, j = 0;

        /*
         * Time Complexity: O(m * n) in the worst case (when all cells are visited)
         * Space Complexity: O(1), constant extra space used
         */

        while (true) {

            direction = (direction + arr[i][j]) % 4;

            // Move in the current direction
            if (direction == 0)
                j++;       // East
            else if (direction == 1)
                i++;       // South
            else if (direction == 2)
                j--;       // West
            else if (direction == 3)
                i--;       // North

            // Exit if out of bounds and step back once
            if (i < 0) {
                i++;
                break;
            } else if (j < 0) {
                j++;
                break;
            } else if (i == arr.length) {
                i--;
                break;
            } else if (j == arr[0].length) {
                j--;
                break;
            }
        }

        System.out.println(i + "," + j);
    }
}

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(m × n)	O(1)
Worst	O(m × n)	O(1)

Explanation:

• Best Case: Exits the matrix immediately (e.g., first cell directs out).

• Average/Worst Case: Traverses many or all cells before exiting.

• Space Complexity is always O(1) as only a few variables (i, j, direction) are used regardless of input size.