Matrix

package testrun;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Matrix {

    public static void rotateClockWise(int[][] mat) {
        int lastRow = mat.length;
        int lastCol = mat[0].length;
        int startRow = 0;
        int startCol = 0;
        while (startRow < lastRow && startCol < lastCol) {
            if (startRow + 1 == lastRow || startCol + 1 == lastCol) {
                break;
            }
            int prev = mat[startRow + 1][startCol];
            for (int i = startCol; i < lastCol; i++) {
                int current = mat[startRow][i];
                mat[startRow][i] = prev;
                prev = current;
            }
            startRow++;
            for (int i = startRow; i < lastRow; i++) {
                int current = mat[i][lastCol - 1];
                mat[i][lastCol - 1] = prev;
                prev = current;
            }
            lastCol--;

            if (startRow < lastRow) {
                for (int i = lastCol - 1; i >= startCol; --i) {
                    int current = mat[lastRow - 1][1];
                    mat[lastRow - 1][1] = prev;
                    prev = current;
                }
            }
            lastRow--;

            if (startCol < lastCol) {
                for (int i = lastRow - 1; i >= startRow; --i) {
                    int current = mat[i][startCol];
                    mat[i][startCol] = prev;
                    prev = current;
                }
            }
            startCol++;
        }

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++)
                System.out.print(mat[i][j] + " ");
            System.out.print("\n");
        }
    }

    public static void printSpiral(int[][] mat) {
        int lastRow = mat.length;
        int lastCol = mat[0].length;
        int startRow = 0;
        int startCol = 0;
        while (startRow < lastRow && startCol < lastCol) {
            for (int i = startCol; i < lastCol; i++) {
                System.out.print(mat[startRow][i] + " ");
            }
            startRow++;

            for (int i = startRow; i < lastRow; i++) {
                System.out.print(mat[i][lastCol - 1] + " ");
            }
            lastCol--;

            if (startRow < lastRow) {
                for (int i = lastCol - 1; i >= startCol; --i) {
                    System.out.print(mat[lastRow - 1][i] + " ");
                }
                lastRow--;
            }

            if (startCol < lastCol) {
                for (int i = lastRow - 1; i >= startRow; --i) {
                    System.out.print(mat[i][startCol] + " ");
                }
                startCol++;
            }
        }
    }

    // https://www.geeksforgeeks.org/inplace-rotate-square-matrix-by-90-degrees/
    public static void rotate90(int mat[][]) {
        int N = mat.length;
        // find transpose of matrix,row->col,col->row
        printMatrix(mat);
        System.out.println();
        transposeMatrix(mat, N);
        System.out.println("After transpose");
        printMatrix(mat);
        System.out.println("");
        reverseEveryColumn(mat);
        System.out.println("After reverse every column");
        printMatrix(mat);
        System.out.println();
    }

    public static void rotate180(int mat[][]) {
        int N = mat.length;
        // find transpose of matrix,row->col,col->row
        printMatrix(mat);
        System.out.println();
        transposeMatrix(mat, N);
        reverseEveryColumn(mat);
        transposeMatrix(mat, N);
        reverseEveryColumn(mat);

        printMatrix(mat);
        System.out.println();
    }

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

    private static void reverseEveryColumn(int[][] mat) {
        for (int i = 0; i < mat[0].length; i++) {
            for (int j = 0, k = mat[0].length - 1; j < k; j++, k--) {
                int temp = mat[j][i];
                mat[j][i] = mat[k][i];
                mat[k][i] = temp;
            }
        }
    }

    private static void transposeMatrix(int[][] mat, int N) {
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
    }

    private static int count;

    public static int printMaxSubSquare(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        int solution[][] = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            solution[i][0] = mat[i][0];
        }
        for (int i = 0; i < cols; i++) {
            solution[0][i] = mat[0][i];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (mat[i][j] == 1) {
                    solution[i][j] = Math.min(solution[i - 1][j], Math.min(solution[i][j - 1], solution[i - 1][j - 1])) + 1;
                } else {
                    solution[i][j] = 0;
                }
            }
        }
        int maxSub = solution[0][0];
        int maxX = 0, maxY = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (solution[i][j] > maxSub) {
                    maxX = i;
                    maxY = j;
                    maxSub = solution[i][j];
                }
            }
        }
        System.out.println("maxX:" + maxX);
        System.out.println("maxY:" + maxY);
        System.out.println("maxSub:" + maxSub);
        for (int i = maxX; i > maxX - maxSub; i--) {
            for (int j = maxY; j > maxY - maxSub; j--) {
                System.out.print(mat[i][j] + " ");
            }
            System.out.println();
        }

        return maxSub;
    }

    // https://www.geeksforgeeks.org/a-boolean-matrix-question/

    public static void markAllOneRowAndColumns(int[][] mat) {

        if (mat == null || mat.length == 0) {
            return;
        }
        // print before manipulation
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                System.out.print(mat[i][j]);
            }
            System.out.println("");
        }
        int rows = mat.length;
        int cols = mat[0].length;
        boolean isFirstRoeHasOne = false;
        boolean isFirstColumnHasOne = false;

        // updating the first row and col if 1
        // is encountered
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 && mat[i][j] == 1)
                    isFirstRoeHasOne = true;

                if (j == 0 && mat[i][j] == 1)
                    isFirstColumnHasOne = true;

                if (mat[i][j] == 1) {
                    mat[0][j] = 1;
                    mat[i][0] = 1;
                }
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (mat[0][j] == 1 || mat[i][0] == 1) {
                    mat[i][j] = 1;
                }
            }
        }

        if (isFirstRoeHasOne == true) {
            for (int i = 0; i < cols; i++) {
                mat[0][i] = 1;
            }
        }

        if (isFirstColumnHasOne == true) {
            for (int i = 0; i < rows; i++) {
                mat[i][0] = 1;
            }
        }
        // print after manipulation
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                System.out.print(mat[i][j]);
            }
            System.out.println("");
        }

    }

    // https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/

    public static void largestRegion(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return;
        }
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                System.out.print(mat[i][j]);
            }
            System.out.println("");
        }
        int rows = mat.length;
        int cols = mat[0].length;
        boolean[][] isVisited = new boolean[rows][cols];

        int maxResult = -1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 1 && !isVisited[i][j]) {
                    count = 1;
                    DFS(i, j, mat, isVisited);
                    maxResult = Math.max(maxResult, count);
                }
            }
        }
        System.out.println("largest region size:" + maxResult);
    }

    public static void DFS(int row, int col, int[][] mat, boolean[][] isVisited) {
        int[] neighbourRows = new int[] { -1, -1, 0, 1, 0, 1, -1, 1 };
        int[] neightbourCols = new int[] { -1, 0, -1, 0, 1, 1, 1, -1 };
        int rows = mat.length;
        int cols = mat[0].length;
        isVisited[row][col] = true;
        for (int k = 0; k < 8; k++) {
            if (isSafeToMoveInMatrixDFS(row + neighbourRows[k], rows, col + neightbourCols[k], cols, isVisited, mat)) {
                count++;
                DFS(row + neighbourRows[k], row + neighbourRows[k], mat, isVisited);
            }
        }
    }

    public static boolean isSafeToMoveInMatrixDFS(int curRow, int maxRow, int curCol, int maxCol,
            boolean[][] isVisited, int[][] mat) {
        return (curRow >= 0 && curRow < maxRow && curCol >= 0 && curCol < maxCol && mat[curRow][curCol] == 1 && !isVisited[curRow][curCol]);
    }

    public static void main(String[] args) {
        // int M[][] = { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 }, { 0, 1, 1, 1, 0
        // }, { 1, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1 },
        // { 0, 0, 0, 0, 0 } };
        // printMaxSubSquare(M);

        // int mat[][] = { { 1, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 0, 0, 0 } };
        // markAllOneRowAndColumns(mat);
        // int a[][] = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13,
        // 14, 15, 16, 17, 18 } };
        // printSpiral(a);

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

        rotate180(arr);
    }

    public static int getpossiblePathInMatFromLeftTopToRightBottom(int[][] mat) {

        int m = mat.length;
        int n = mat[0].length;
        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 0) {
                mat[i][0] = 1;
            }
            break;
        }
        for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                mat[0][j] = 1;
            }
            break;
        }
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (mat[i][j] == -1) {
                    continue;
                }
                if (mat[i - 1][j] > 0) {
                    mat[i][j] += mat[i - 1][j];
                }
                if (mat[i][j - 1] > 0) {
                    mat[i][j] += mat[i][j - 1];
                }
            }
        }

        return mat[m - 1][n - 1];

    }

    public static class Node {
        int x;
        int y;
        int val;

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public Node(int x, int y, int val) {
            super();
            this.x = x;
            this.y = y;
            this.val = val;
        }

    }

    public static void KthLargestElem() {
        // matrix is sorted find kth largest,Soltion is klogn
        int mat[][] = { { 1, 5, 9 }, { 10, 11, 13 }, { 12, 13, 15 } };

        // create a max heap
        PriorityQueue<Node> minHeap = new PriorityQueue<Node>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.val - o1.val;
            }
        });
        // take required K
        int k = 7;
        // insert last column in max heap;
        for (int i = 0; i < mat.length; i++) {
            minHeap.offer(new Node(i, mat.length - 1, mat[i][mat.length - 1]));
        }

        // replace in max heap from previous column k times
        while (!minHeap.isEmpty()) {
            Node node = minHeap.poll();
            if (k == 1) {
                // output
                System.out.print(node.val);
            }

            if (node.y - 1 >= 0) {
                minHeap.offer(new Node(node.x, node.y - 1, mat[node.x][node.y - 1]));
            }
            k--;
        }

    }

    public static boolean isSafeToMove(int[][] mat, int x, int y) {
        return x >= 0 && x < mat.length && y >= 0 && y < mat[0].length && mat[x][y] > 0;
    }

    public static void ratMazeProblem(int[][] mat) {
        int[][] sol = new int[mat.length][mat[0].length];
        if (isPossiblePathForRat(mat, sol, 0, 0)) {
            // print sol
        }
    }

    public static boolean isPossiblePathForRat(int[][] mat, int[][] sol, int x, int y) {
        if (x == mat.length - 1 && y == mat[0].length - 1) {
            sol[x][y] = 1;
            return true;
        }
        if (isSafeToMove(mat, x, y)) {
            sol[x][y] = 1;
            if (isPossiblePathForRat(mat, sol, x + 1, y)) {
                return true;
            }

            if (isPossiblePathForRat(mat, sol, x, y + 1)) {
                return true;
            }
            sol[x][y] = 0;
        }

        return false;
    }

    public static void searchWord(char[][] matrix, String word, int curIndexAtWord, StringBuilder buf, int curRow,
            int curCol, int prevRow, int prevCol) {
        int rowNum[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int colNum[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
        int ROW = matrix.length;
        int COL = matrix[0].length;
        if (curIndexAtWord > word.length()) {
            return;
        }
        if (word.charAt(curIndexAtWord) != matrix[curRow][curCol]) {
            return;
        }

        buf.append(word.charAt(curIndexAtWord) + " at (" + curRow + "," + curCol + ")");
        if (curIndexAtWord == word.length() - 1) {
            System.out.println("Path found: " + buf.toString());
            return;
        }

        for (int k = 0; k < 8; ++k) {
            if (isvalid(curRow + rowNum[k], curCol + colNum[k], prevRow, prevCol, ROW, COL)) {
                searchWord(matrix, word, curIndexAtWord + 1, buf, curRow + rowNum[k], curCol + colNum[k], curRow,
                        curCol);
            }
        }

    }

    static boolean isvalid(int row, int col, int prevRow, int prevCol, int ROW, int COL) {
        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && !(row == prevRow && col == prevCol);
    }

    public static void findoccurenceOFwordInMatrix(char[][] matrix, String word) {
        if (matrix == null || word == null || matrix.length == 0 || word.isEmpty()) {
            return;
        }
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                StringBuilder buf = new StringBuilder();
                if (matrix[row][col] == word.charAt(0)) {
                    searchWord(matrix, word, 0, buf, row, col, -1, -1);
                }
            }
        }

    }

    public static void maxSubSubmatrix(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;

        int[] currentResult;
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int top = 0;
        int right = 0;
        int bottom = 0;

        for (int lefCol = 0; lefCol < cols; lefCol++) {
            int temp[] = new int[rows];
            for (int rightCol = lefCol; rightCol < cols; rightCol++) {
                for (int i = 0; i < rows; i++) {
                    temp[i] += mat[i][rightCol];
                }
                currentResult = kadaneAlgo(temp);

                if (currentResult[0] > maxSum) {
                    currentResult[0] = maxSum;
                    left = lefCol;
                    top = currentResult[1];
                    bottom = currentResult[2];
                    right = rightCol;
                }

            }
        }
        System.out.println("MaxSum: " + maxSum + ", range: [(" + left + ", " + top + ")(" + right + ", " + bottom
                + ")]");

    }

    public static int[] kadaneAlgo(int[] arr) {
        int[] result = new int[] { 0, -1, -1 };
        int curSum = 0;
        int startIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            curSum += arr[i];
            if (curSum < 0) {
                curSum = 0;
                startIndex = i + 1;
            } else if (curSum > result[0]) {
                result[0] = curSum;
                result[1] = startIndex;
                result[2] = i;
            }

        }
        if (result[2] == -1) {
            result[0] = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > result[0]) {
                    result[0] = arr[i];
                    result[1] = i;
                    result[2] = i;
                }
            }
        }
        return result;
    }

}