LeetCode - Search a 2D Matrix (Java)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has properties:

1) Integers in each row are sorted from left to right. 2) The first integer of each row is greater than the last integer of the previous row.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) 
            return false;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int start = 0;
        int end = m*n-1;
 
        while(start<=end){
            int mid=(start+end)/2;
            int midX=mid/n;
            int midY=mid%n;
 
            if(matrix[midX][midY]==target) 
                return true;
 
            if(matrix[midX][midY]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
 
        return false;
    }
}

http://www.geeksforgeeks.org/inplace-rotate-square-matrix-by-90-degrees/

Given an square matrix, turn it by 90 degrees in anti-clockwise direction without using any extra space.

First Cycle (Involves Red Elements)
 1  2  3 4 
 5  6  7  8 
 9 10 11 12 
 13 14 15 16 

 
Moving first group of four elements (First
elements of 1st row, last row, 1st column 
and last column) of first cycle in counter
clockwise. 
 4  2  3 16
 5  6  7 8 
 9 10 11 12 
 1 14  15 13 
 
Moving next group of four elements of 
first cycle in counter clockwise 
 4  8  3 16 
 5  6  7  15  
 2  10 11 12 
 1  14  9 13 

Moving final group of four elements of 
first cycle in counter clockwise 
 4  8 12 16 
 3  6  7 15 
 2 10 11 14 
 1  5  9 13 


Second Cycle (Involves Blue Elements)
 4  8 12 16 
 3  6 7  15 
 2  10 11 14 
 1  5  9 13 

Fixing second cycle
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13

void rotateMatrix(int mat[][N])

{

    // Consider all squares one by one

    for (int x = 0; x < N / 2; x++)

    {

        // Consider elements in group of 4 in

        // current square

        for (int y = x; y < N-x-1; y++)

        {

            // store current cell in temp variable

            int temp = mat[x][y];

            // move values from right to top

            mat[x][y] = mat[y][N-1-x];

            // move values from bottom to right

            mat[y][N-1-x] = mat[N-1-x][N-1-y];

            // move values from left to bottom

            mat[N-1-x][N-1-y] = mat[N-1-y][x];

            // assign temp to left

            mat[N-1-y][x] = temp;

        }

    }

}

http://www.geeksforgeeks.org/rotate-matrix-90-degree-without-using-extra-space-set-2/

1. Find transpose of matrix.
2. Reverse columns of the transpose.

// After transpose we swap elements of column

// one by one for finding left rotation of matrix

// by 90 degree

void reverseColumns(int arr[R][C])

{

    for (int i=0; i<C; i++)

        for (int j=0,  k=C-1; j<k; j++,k--)

            swap(arr[j][i], arr[k][i]);

}

// Function for do transpose of matrix

void transpose(int arr[R][C])

{

    for (int i=0; i<R; i++)

        for (int j=i; j<C; j++)

            swap(arr[i][j], arr[j][i]);

} 

// Function to anticlockwise rotate matrix

// by 90 degree

void rotate90(int arr[R][C])

{

    transpose(arr);

    reverseColumns(arr);

}

The above steps/program do left (or anticlockwise) rotation, how to right (or clockwise) rotate?
To right rotate, we do following steps.

1. Find transpose of matrix.
2. Reverse rows of the transpose.

http://www.geeksforgeeks.org/turn-an-image-by-90-degree/

    pDestination =

           (unsigned int *)malloc(sizeof(int)*m*n); 

    rotate(pSource, pDestination, m, n);

void rotate(unsigned int *pS, unsigned int *pD,

            unsigned int row, unsigned int col)

{

    unsigned int r, c;

    for (r = 0; r < row; r++)

    {

        for (c = 0; c < col; c++)

        {

            *(pD + c * row + (row - r - 1)) =

                            *(pS + r * col + c);

        }

    }

}

Read full article from LeetCode – Search a 2D Matrix (Java)