Diagonal Traversal

 eg. 

1     2     3     4

5     6     7     8

9    10   11   12

13  14   15   16

Output: 1 6 11 16 2 7 12 3 8 4 

Approach:
number of diagonals = arr.length
all the diagonals are starting from i=0,
till j=arr.length that will act as right wall

package jan24_2D_Array;

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

        int[][] arr = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };

        /*
         Time Complexity:
         Best Case: O(n^2) – All diagonals are visited once.
         Average Case: O(n^2) – Diagonal traversal over matrix elements.
         Worst Case: O(n^2) – Covers upper half of matrix diagonals.

         Space Complexity:
         Best/Average/Worst Case: O(1) – No extra space used, in-place processing.
        */

        
        for (int diagonal = 0; diagonal < arr.length; diagonal++) {
            for (int i = 0, j = diagonal; j < arr.length; i++, j++) {
                System.out.print(arr[i][j] + "\t");
            }
        }
    }
}

Case
Time Complexity
Explanation
Space Complexity
Explanation
Best
O(n²)
All diagonals are visited once
O(1)
No extra space used
Average
O(n²)
Diagonal traversal over matrix
O(1)
In-place processing
Worst
O(n²)
Covers upper half of matrix
O(1)
No additional memory used

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.