50 DSA-Questions: #12, #13

#12. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.

public class Exercise12 {
    private final Integer[][] MATRIX = {{1,2,3},{4,5,6},{7,8,9}}; //  [1,2,3,6,9,8,7,4,5]
    // private final Integer[][] MATRIX = {{1,2,3,4},{5,6,7,8},{9,10,11,12}}; // [1,2,3,4,8,12,11,10,9,5,6,7]
    // private final Integer[][] MATRIX = {{1,2,3,4, 5},{6,7,8,9,0},{9,8,7,6,5}, {4,3,2,1,0}, {9,1,2,3,4}};

    private enum DIRECTION {LEFT_TO_RIGHT, TOP_TO_BOTTOM, RIGHT_TO_LEFT, BOTTOM_TO_TOP};

    private void run(int i, int j, DIRECTION direction, int cycle) {
        switch (direction) {
            case LEFT_TO_RIGHT:
                if (j >= MATRIX[0].length-cycle) {
                    return;
                }
                for (int jj=j; jj<MATRIX[0].length-cycle; jj++) {
                    System.out.print(MATRIX[i][jj] + " ");
                }
                System.out.println();
                run(i+1,MATRIX[0].length - cycle - 1, DIRECTION.TOP_TO_BOTTOM, cycle);
                break;
            case TOP_TO_BOTTOM:
                if (i >= MATRIX.length-cycle) {
                    return;
                }
                for (int ii=i; ii<MATRIX.length-cycle; ii++) {
                    System.out.print(MATRIX[ii][j] + " ");
                }
                System.out.println();
                run(MATRIX.length - cycle - 1, j-1, DIRECTION.RIGHT_TO_LEFT, cycle);
                break;
            case RIGHT_TO_LEFT:
                for (int jj=j; jj>=cycle; jj--) {
                    System.out.print(MATRIX[i][jj] + " ");
                }
                System.out.println();
                run(i-1, cycle, DIRECTION.BOTTOM_TO_TOP, cycle);
                break;
            case BOTTOM_TO_TOP:
                for (int ii=i; ii>cycle; ii--) {
                    System.out.print(MATRIX[ii][j] + " ");
                }
                System.out.println();
                run(cycle + 1,j+1, DIRECTION.LEFT_TO_RIGHT, cycle + 1);
                break;
        }
    }

    private void solve() {
        run(0, 0, DIRECTION.LEFT_TO_RIGHT, 0);
    }

    public static void main(String args[]) {
        new Exercise12().solve();
    }
}

#13. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

public class Exercise13 {
    private final int MARKER = 1000000; // marks that Mij has been updated
    // private final int[][] MATRIX = {{1,2,3},{4,5,6},{7,8,9}}; // n x n, -1000 <= matrix[i][j] <= 1000
    // private final Integer[][] MATRIX = {{1,2,3,4, 5},{6,7,8,9,0},{9,8,7,6,5}, {4,3,2,1,0}, {9,1,2,3,4}};
    // private final Integer[][] MATRIX = {{1,2,-3,-4},{0,7,8,-9},{9,8,-7,6}, {4,0,2,-1}};
    private final Integer[][] MATRIX = {{1000,2},{-1000,7}};
    private int MAX_VALUE = 1001;

    private int getCorrespondingElement90Cw(int i, int j) {
        return MATRIX[MATRIX.length-1-j][i];
    }

    private int getCorrespondingElement90Ccw(int i, int j) {
        return MATRIX[j][MATRIX.length-1-i];
    }

    private int getCorrespondingElement180(int i, int j) {
        return MATRIX[MATRIX.length-1-i][MATRIX.length-1-j];
    }

    private void solveOnlyDisplay() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(getCorrespondingElement90Cw(i,j) + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void addToOriginalMatrix(int valueToAdd) {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                MATRIX[i][j] = MATRIX[i][j] + valueToAdd;
            }
        }
    }

    private int getMatrixMin() {
        int minElem = MAX_VALUE;
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                if (MATRIX[i][j] < minElem) {
                    minElem = MATRIX[i][j];
                }
            }
        }
        return minElem;
    }

    private void display() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void solveWithSaving() {
        assert(MATRIX.length == MATRIX[0].length);
        int minValue = getMatrixMin();
        if (minValue < 0) {
            addToOriginalMatrix(- minValue); // make all values positive
            MAX_VALUE -= minValue; // update max possible 
        }

        // in place saving 90 degrees clockwise matrix rotation

        // extra loading matrix: Mij = MARKER + Mij * MAX_VALUE + Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                int rotatedMij = getCorrespondingElement90Cw(i,j);
                if (rotatedMij >= MARKER) {
                    int originalRotatedElement = (rotatedMij - MARKER) / MAX_VALUE;
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + originalRotatedElement;
                } else {
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + rotatedMij;
                }
            }
        }

        // cleanup to get only Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                MATRIX[i][j] = (MATRIX[i][j] - MARKER) % MAX_VALUE;
            }
        }

        if (minValue < 0) {
            addToOriginalMatrix(minValue); // restore original values in matrix
        }

        display();
    }

    public static void main(String args[]) {
        new Exercise13().solveOnlyDisplay();
        new Exercise13().solveWithSaving();
    }
}