[Sorting and Searching] interview questions #9

[rygh4775]

Sorted Matrix Search: Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

[tgi01054]

    public class Position{
        public int row;
        public int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public Position(Position old){
            this.row = old.row;
            this.col = old.col;
        }
    }

    Position findByPartition(int[][] matrix, int val, Position leftUpper, Position rightLower){

        // Check termination condition.
        if( leftUpper.row == rightLower.row && leftUpper.col == rightLower.col ){

            if( matrix[leftUpper.row][leftUpper.col] == val){
                return leftUpper;
            }else{
                return null;
            }
        }else if( leftUpper.row > rightLower.row){
            return null;
        }else if( leftUpper.col > rightLower.col){
            return null;
        }

        // Check whether value is equals to maximum in left upper area.
        int centerRow1 = (leftUpper.row + rightLower.row) / 2;
        int centerCol1 = (leftUpper.col + rightLower.col) / 2;
        if( matrix[centerRow1][centerCol1] == val){
            return new Position(centerRow1, centerCol1);
        }

        // Check whether value is equals to minimum in right lower area.
        int centerRow2 = centerRow1 + 1;
        int centerCol2 = centerCol1 + 1;

        int matrixRows = matrix.length;
        int matrixCols = matrix[0].length;
        if (centerRow2 + 1 > matrixRows) {
            return null;
        }
        if (centerCol2 + 1 > matrixCols) {
            return null;
        }

        if(matrix[centerRow2][centerCol2] == val){
            return new Position(centerRow2, centerCol2);
        }

        Position position = null;
        if( val < matrix[centerRow1][centerCol1]){
            // Find left upper area
            Position newLeftUpper = leftUpper;
            Position newRightLower = new Position(centerRow1,centerCol1);

            position = findByPartition(matrix, val, newLeftUpper, newRightLower);
        }else if (matrix[centerRow2][centerCol2] < val ){
            // Find right lower area
            Position newLeftUpper = new Position(centerRow2,centerCol2);
            Position newRightLower = rightLower;

            position = findByPartition(matrix, val, newLeftUpper, newRightLower);
        }

        if( position != null){
            return position;
        }

        // Find left lower area
        Position newLeftUpper = new Position(leftUpper);
        newLeftUpper.row = centerRow2;
        Position newRightLower = new Position(rightLower);
        newRightLower.col = centerCol1;

        position = findByPartition(matrix, val, newLeftUpper, newRightLower);
        if(position != null){
            return position;
        }

        // Find right upper area
        newLeftUpper = new Position(leftUpper);
        newLeftUpper.col = centerCol2;
        newRightLower = new Position(rightLower);
        rightLower.row = centerRow1;

        position = findByPartition(matrix, val, newLeftUpper, newRightLower);
        if(position != null){
            return position;
        }

        return null;
    }

    Position find(int[][] matrix, int val){
        Position leftUpper = new Position(0,0);
        Position rightLower = new Position(matrix.length - 1, matrix[0].length - 1);

        return findByPartition(matrix, val, leftUpper, rightLower);
    }