Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Strategy:
best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.
http://happycoding2010.blogspot.in/2015/11/leetcode-296-best-meeting-point.html
http://www.programcreek.com/2014/07/leetcode-best-meeting-point-java/

Matrix Transpose inplace

Inplace (Fixed space) M x N size matrix transpose
Given an M x N matrix, transpose the matrix without auxiliary memory.It is easy to transpose matrix using an auxiliary array. If the matrix is symmetric in size, we can transpose the matrix inplace by mirroring the 2D array across it’s diagonal (try yourself). How to transpose an arbitrary size matrix inplace? See the following matrix,

a b c       a d g j
d e f  ==>  b e h k
g h i       c f i l
j k l

http://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/

Find paths from corner cell to middle cell in maze

Given a square maze containing positive numbers, find all paths from a corner cell (any of the extreme four corners) to the middle cell. We can move exactly n steps from a cell in 4 directions i.e. North, East, West and South where n is value of the cell,

We can move to mat[i+n][j], mat[i-n][j], mat[i][j+n], and mat[i][j-n] from a cell mat[i][j] where n is value of mat[i][j].

Example

Input:  9 x 9 maze
[ 3, 5, 4, 4, 7, 3, 4, 6, 3 ]
[ 6, 7, 5, 6, 6, 2, 6, 6, 2 ]
[ 3, 3, 4, 3, 2, 5, 4, 7, 2 ]
[ 6, 5, 5, 1, 2, 3, 6, 5, 6 ]
[ 3, 3, 4, 3, 0, 1, 4, 3, 4 ]
[ 3, 5, 4, 3, 2, 2, 3, 3, 5 ]
[ 3, 5, 4, 3, 2, 6, 4, 4, 3 ]
[ 3, 5, 1, 3, 7, 5, 3, 6, 4 ]
[ 6, 2, 4, 3, 4, 5, 4, 5, 1 ]

Output:
(0, 0) -> (0, 3) -> (0, 7) -> 
(6, 7) -> (6, 3) -> (3, 3) -> 
(3, 4) -> (5, 4) -> (5, 2) -> 
(1, 2) -> (1, 7) -> (7, 7) ->
(7, 1) -> (2, 1) -> (2, 4) -> 
(4, 4) -> MID

http://www.geeksforgeeks.org/find-paths-from-corner-cell-to-middle-cell-in-maze/

Convert matrix to 1d array

A n*n matrix is given which is containing elements in which each row alone is sorted. column is not sorted. We have to convert it into a single dimensional array which will hold all the elements of the array in a sorted manner.

Print All Diagonals of a given matrix

Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix.

Exam­ple:

http://algorithms.tutorialhorizon.com/print-all-diagonals-of-a-given-matrix/

Count zeros in a row wise and column wise sorted matrix

Given a N x N binary matrix (elements in matrix can be either 1 or 0) where each row and column of the matrix is sorted in ascending order, count number of 0s present in it.
Expected time complexity is O(N).
Examples:
Input: 
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 1]
[0, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
Output: 8
Input: 
[0, 0]
[0, 0]
Output: 4
Input: 
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
Output: 0
http://www.geeksforgeeks.org/count-zeros-in-a-row-wise-and-column-wise-sorted-matrix/

Graph Connectivity and Termilogies

Connectivity in a directed graph
http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

BiConnected Graph
http://www.geeksforgeeks.org/biconnectivity-in-a-graph/

Articulation Points (or Cut Vertices) in a Graph
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Bridges in a Graph
http://www.geeksforgeeks.org/bridge-in-a-graph/

Print unique rows in a given boolean matrix

Given a binary matrix, print all unique rows of the given matrix.
Input:
{0, 1, 0, 0, 1}
        {1, 0, 1, 1, 0}
        {0, 1, 0, 0, 1}
        {1, 1, 1, 0, 0}
Output:
0 1 0 0 1 
1 0 1 1 0 
1 1 1 0 0 
http://www.geeksforgeeks.org/print-unique-rows/

Fast Matrix Multiplication

Describe both the standard way, Strassen Algo & Coppersmith-Winograd Algo for Matrix Multiplication

http://en.wikipedia.org/wiki/Matrix_multiplication

http://en.wikipedia.org/wiki/Strassen_algorithm

http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm

Code for Simple Matrix Multiplication:

#include <stdio.h>

int main()

{

  int row1, col1, row2, col2, c, d, k, sum = 0;

  int first[10][10], second[10][10], multiply[10][10];

  printf("Enter the number of rows and columns of first matrix\col1");

  scanf("%d%d", &row1, &col1);

  printf("Enter the elements of first matrix\col1");

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

    for ( d = 0 ; d < col1 ; d++ )

      scanf("%d", &first[c][d]);

  printf("Enter the number of rows and columns of second matrix\col1");

  scanf("%d%d", &row2, &col2);

  if ( col1 != row2 )

    printf("Matrices with entered orders can't be multiplied with each other.\col1");

  else

  {

    printf("Enter the elements of second matrix\col1");

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

      for ( d = 0 ; d < col2 ; d++ )

        scanf("%d", &second[c][d]);

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

    {

      for ( d = 0 ; d < col2 ; d++ )

      {  

        multiply[c][d]=0;

        for ( k = 0 ; k < row2 ; k++ )

        {

          multiply[c][d]+= first[c][k]*second[k][d];

        }

      }

    }

    printf("Product of entered matrices:-\col1");

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

    {

      for ( d = 0 ; d < col2 ; d++ )

        printf("%d\t", multiply[c][d]);

      printf("\col1");

    }

  }

  getchar();

  getchar();

  return 0;

}

The running time of square matrix multiplication, if carried out naïvely, is . The running time for multiplying rectangular matrices (one m×p-matrix with one p×n-matrix) is O(mnp)

Strassen algorithm

Let A, B be two square matrices over a ring R. We want to calculate the matrix product C as

If the matrices A, B are not of type 2ⁿ x 2ⁿ we fill the missing rows and columns with zeros.

We partition A, B and C into equally sized block matrices

with

then

With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the C_i,j matrices, the same number of multiplications we need when using standard matrix multiplication.

Now comes the important part. We define new matrices

only using 7 multiplications (one for each M_k) instead of 8. We may now express the C_i,j in terms of M_k, like this:

We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of the ring R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding rows and columns.

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations

kth smallest element in a sorted matrix

Assume you have a integer matrix (m x n) sorted over column wise & row wise. WAP to find the kth smallest element from the matrix.
E.g.
int[][] a =
2, 5, 8, 10
4, 7, 9, 12
6, 15, 20, 22
So 5th smallest element is: 7

Minimum path sum from top to bottom in a Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

http://www.programcreek.com/2013/01/leetcode-triangle-java/

Find max sub-square whose border values are all 1

Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Maximum sub-matrix sum in a matrix

Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

Useful Links:
http://ronzii.wordpress.com/2012/03/16/kadanes-algorithm-2d/
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=385650#385650

Rat in a maze algorithm

A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

http://algorithms.tutorialhorizon.com/backtracking-rat-in-a-maze-puzzle/
http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

Code:BackTracking

#include<stdio.h>
#include<stdlib.h>

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

int main()
{
    int maze[N][N] =
    {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}

Find a string/pattern in a 2d character array

You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.

Example: Find “microsoft” in below matrix.

We can see the read color character, which form “Microsoft” in above 2D array.


Strategy:
Manually finding the solution of this problem is relatively intuitive, we just need to describe an algorithm for it. Ironically, describing the algorithm is not the easy part.

How do we do it manually? First we match the first element; if it matched we matched the 2nd element in the 8 neighbors of first match; do this process recursively; when last character of input pattern matches, return true.

During above process, you take care not to use any cell in 2D array twice. For this purpose, you mark every visited cell with some sign. If your pattern matching fails at some place, you start matching from the beginning (of pattern) in remaining cells. While returning, you unmark visited cells.

Lets convert above intuitive method in algorithm. Since we are doing similar checks every time for pattern matching, a recursive solution is what we need here.

In recursive solution, we need to check if the substring passed is matched in the given matrix or not. The condition is not to use the already used cell. For finding already used cell, we need to have another 2D array to the function (or we can use an unused bit in input array itself.) Also, we need the current position of input matrix, from where we need to start. Since we need to pass a lot more information than actually given, we should be having a wrapper function to initialize that extra information to be passed


Algorithm:

If you are past the last character in pattern
    Return true


If you got an used cell again
    Return falseIf you got past the 2D matrix  
    Return false


If searching for first element and cell doesn’t match
    findmatch with next cell in row-first order (or column first order)


otherwise if character matches
    mark this cell as used
    res = findmatch  with next position of pattern in 8 neighbors
    mark this cell as unused
    Return res


Otherwise
    Return false

Code:


#define MAX 100


bool findmatch_wrapper(char mat[MAX][MAX], char *pat, int nrow, int ncol)
{
    if (strlen(pat) > nrow*ncol)
        return false;
    
    int used[MAX][MAX] = {{0,},};


    return findmatch(mat, pat, used, 0, 0, nrow, ncol, 0);
}


//level: index till which pattern is matched
//x, y: current position in 2D array


bool findmatch(char mat[MAX][MAX], char *pat, int used[MAX][MAX], int x, int y, int nrow, int ncol, int level)
{
    if (level == strlen(pat)) //pattern matched
        return true;
        
    if (nrow == x || ncol == y)
        return false;
        
    if (used[x][y])
        return false;    
    
    if (mat[x][y] != pat[level] && level == 0)
    {
        if (x < (nrow - 1))
            return findmatch(mat, pat, used, x+1, y, nrow, ncol, level); //next element in same row
        else if (y < (ncol - 1))
            return findmatch(mat, pat, used, 0, y+1, nrow, ncol, level); //first element from same column
        else 
            return false;
    }    
    else if (mat[x][y] == pat[level])
    {
        bool res;
        //marking this cell as used
        used[x][y] = 1;       
             
        //finding subpattern in 8 neighbours     
        res = (x > 0                                    ? findmatch(mat, pat, used, x-1, y, nrow, ncol, level+1) :   false) ||
              (res = x < (nrow - 1)                     ? findmatch(mat, pat, used, x+1, y, nrow, ncol, level+1) :   false) ||
              (res = y > 0                              ? findmatch(mat, pat, used, x, y-1, nrow, ncol, level+1) :   false) ||
              (res = y < (ncol - 1)                     ? findmatch(mat, pat, used, x, y+1, nrow, ncol, level+1) :   false) ||
              (res = x < (nrow - 1) && (y < ncol -1)    ? findmatch(mat, pat, used, x+1, y+1, nrow, ncol, level+1) : false) ||
              (res = x < (nrow - 1) && y > 0            ? findmatch(mat, pat, used, x+1, y-1, nrow, ncol, level+1) : false) ||
              (res = x > 0 && y < (ncol - 1)            ? findmatch(mat, pat, used, x-1, y+1, nrow, ncol, level+1) : false) ||
              (res = x > 0 && y > 0                     ? findmatch(mat, pat, used, x-1, y-1, nrow, ncol, level+1) : false);


        //marking this cell as unused
        used[x][y] = 0;
        return res;
    }
    else
        return false;
}

Rectangular Blocks in Matrix

Find the number of rectangular blocks in a matrix where block is the one having same numbers

{1, 1, 1},
  {1, 1, 3},
  {4, 4, 5}

In the above Matrix answer should be 4 as given below

1,1,1

3

4,4

5

Row with minimum number of zeros

Row with the maximum number of 1s

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

Example :Input matrix

0 1 1 1

0 0 1 1

1 1 1 1  // this row has maximum 1s

0 0 0 0

Output: 2

http://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/

Row with minimum 0's

You have a matrix with 0 & 1 with rows being in sorted order. Find the row with minimum number of 1's

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 0 1 1 1

Solution:

1. Start from row1 till you keep getting a 0, as soon as you encounter a 1 go south and use the following table

1 -> 1 similar row
1 -> 0 better row make this is as candidate for answer


1. let's run through the algorithm from row1, col4 go south as row1, col4 is 1
2. transition is 1->1 so ignore second row and go south
3. 1 -> 1 similar row ignore row3 also
4. on same logic ignore row4 also so answer is row1

Let's take another matrix and run the same algo again

0 0 1 1 1
0 0 0 1 1
0 0 0 0 1

1. first transtion on row1, col3 is 1->0 so row is better
2. now run right on row2 till you get a 1 which is row3,col4 and now go south for which the transition is 1->0 making it a better row and since this is the last row hence the final answer

Time complexity analysis
1. best case-> 0(number of rows) it's a straight down south
2. worst case -> 2 (number of rows) wherein it's a zig zag motion 

Modify Boolean MATRIX

Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1.

Method 1:Using Extra Memory

1) Create two temporary arrays row[M] and col[N]. Initialize all values of row[] and col[] as 0.
2) Traverse the input matrix mat[M][N]. If you see an entry mat[i][j] as true, then mark row[i] and col[j] as true.
3) Traverse the input matrix mat[M][N] again. For each entry mat[i][j], check the values of row[i] and col[j]. If any of the two values (row[i] or col[j]) is true, then mark mat[i][j] as true.

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

Method 2:Using First row and First Column:
This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).
1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

http://www.programcreek.com/2012/12/leetcode-set-matrix-zeroes-java/
http://yucoding.blogspot.in/2013/04/leetcode-question-97-set-matrix-zeros.html

Code:
void flip(int M[][COL])
{
        int i, j, r, c, flagRow, flagCol;

        for( r = 0, flagCol = 0; r < ROW; ++r )
                flagCol |= M[r][0];

        for( c = 0, flagRow = 0; c < COL; ++c )
                flagRow |= M[0][c];

        for( r = 1; r < ROW; ++r )
                for( c = 1; c < COL; ++c )
                {
                        M[0][c] |= M[r][c];
                        M[r][0] |= M[r][c];
                }

        for( r = 1; r < ROW; ++r )
                for( c = 1; c < COL; ++c )
                        if( M[0][c] || M[r][0] )
                                M[r][c] = 1;

        if( flagRow )
                for( c = 0; c < COL; ++c )
                        M[0][c] = 1;
       
        if( flagCol )
                for( r = 0; r < ROW; ++r )
                        M[r][0] = 1;
        printM(M);
}
Time Complexity: O(M*N)
Auxiliary Space: O(1)

Method 3:No extra memory and with no overhead

#include <stdio.h>
#include <limits.h>
inline void clear(const int m, const int n, int a[][n], const int row, const int col)
{
    int k;
    for(k = 0; k < m; k++)

if(a[k][col] != 0)
           a[k][col] = INT_MAX;

    for(k = 0; k < n; k++)

        if(a[row][k] != 0)
           a[row][k] = INT_MAX;

}

inline void print(const int m, const int n, int a[][n])
{
    int i, j;
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
            printf("%d ", a[i][j]);

        printf("\n");
    }
}

void setRowCol(const int m, const int n, int a[][n])
{
    int i = 0, j = 0, k;

    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(a[i][j] == 0)
            {
                clear(m, n, a, i, j);

            }

    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(a[i][j] == INT_MAX)
            {
                a[i][j] = 0;
            }
}

int main()
{
    int a[][3] = { {2, 0, 4},
                  {1 ,2, 3},
                  {3, 5, 0},
                  {4, 5, 6}
                };
    setRowCol(4, 3, a);
    print(4, 3, a);
}

Count number of paths in a Matrix with or without Constraints

Question 1:Count All Paths
Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths. Modify the solution to include constraints that from each cell you can either move only to right or down. Also extend both algo. to print all paths.

Alternatively [ Robot on MxN Grid],
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?
Or
Given two positions in a 2-D matrix, say (x1, y1) and (x2, y2) where x2>=x1 and y2>=y1. Find the total number of distinct paths between (x1, y1) and (x2, y2). You can only move in right direction i.e. positive x direction (+1, 0) or in up direction i.e. positive y direction (0, +1) from any given position.
Example: If the given coordinates are  (3,3)  and (5,5), the number of distinct paths are 6 :  one going through 3,5 ; one going through 5,3 and four going through 4,4.

Count:
Diagonal Paths Allowed
http://algorithms.tutorialhorizon.com/count-all-paths-from-top-left-to-bottom-right-in-two-dimensional-array-including-diagonal-paths/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
Diagonal Paths not allowed
http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

Question 2:Unique Paths
http://articles.leetcode.com/unique-paths
http://www.programcreek.com/2014/05/leetcode-unique-paths-java/
http://www.programcreek.com/2014/05/leetcode-unique-paths-ii-java/

Variation 1: Robot Travel with obstructions

Count all paths in 2D Matrix with Obstructions in it

http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-in-2d-matrix-with-obstructions-in-it/

Longest Possible Route in a Matrix with Hurdles
http://www.geeksforgeeks.org/longest-possible-route-in-a-matrix-with-hurdles/

Print:
1. http://www.geeksforgeeks.org/print-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
2. http://algorithms.tutorialhorizon.com/print-all-paths-from-top-left-to-bottom-right-in-two-dimensional-array/

3. Given m x n matrix print all the possible paths top to down.

Example
1 2 3
4 5 6
7 8 9

path for root(0,0) 1
1-4-7
1-4-8
1-5-7
1-5-8
1-5-9

similarly path for 2(0,1)
2-4-7
2-4-8
2-5-7
2-5-8
2-5-9
2-6-8
2-6-9

note- root 1 can go to middle down or right down since there is no left index available. if root element has left middle and right it can go to all those paths like 2 or 5.

follow up : Provide the path which has maximum path sum.

Minimum Cost path matrix
Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell.
http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-cost-path-problem/

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

Robot Combinatoric Solution:

long factorial(int n)
{
   int c;
   long result = 1;
   for( c = 1 ; c <= n ; c++ )
      result = result*c;
   return ( result );
}
long C(int n, int r)
{
   long result;
   result = factorial(n)/(factorial(r)*factorial(n-r));

   return result;

}
int countPaths(int x1, int y1, int x2, int y2) {

   int n = abs(x2-x1);
   int m = abs(y2-y1);
   return C(m+n,n);

}

Print all elements in sorted order / Search elements from row and column wise sorted matrix

Print a Bidimensional sorted Matrix
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of matrix in sorted order.
Example: Input: mat[][]  =  { {10, 20, 30, 40},
                     {15, 25, 35, 45},
                     {27, 29, 37, 48},
                     {32, 33, 39, 50},
                   };

Output: Elements of matrix in sorted order
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
http://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/

Search in Bidimensional sorted Matrix
You are provided a n*n square matrix which has elements as both row and column sorted.
Device an algorithm which can search an element in this array within O(n) time.

Example:
There is a bi-dimensional array. All the rows and columns of this array are sorted in ascending order. Example -

3	32	34	39
4	35	38	40
6	56	57	77
45	78	88	90

Method 1: Binary Search & Diagonal Binary Search O(nlogn) & O(logn!)
http://articles.leetcode.com/searching-2d-sorted-matrix/

Method 2: Step-wise Linear Search: O(n)
http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/
http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii/
http://www.programcreek.com/2014/04/leetcode-search-a-2d-matrix-ii-java/

Method 3: Quad parition and Binary Partition [ Best Method ]
http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii/
http://articles.leetcode.com/searching-2d-sorted-matrix-part-iii/

Variation:
http://www.programcreek.com/2013/01/leetcode-search-a-2d-matrix-java/

Strategy:

Start from top-right.

• If search key is lesser than current element, move towards left.
• If search key is greater, move towards down.
• Keep doing the same thing until you reach the element.
• If you reach first column/last row and couldn’t move further, we can conclude the search key is not present in the array.

In worst case, search key will be bottom-left element and will need 2n comparisons. Hence, overall complexity is O(n).

Alternatively,
Imagine that the matrix is sorted in ascending order for both row and column.
Code:
#include<stdio.h>
#include<stdlib.h>
int find(int arr[][5], int size, int num)
{
    int row=size-1;
    int col=0;
    while((row > 0) && (col < size))
    {
        if(arr[row][col] == num)
            return 1;
        else if(arr[row][col] < num)
            col++;
        else
            row--;
    }

    return 0;
}

int main()
{
    int arr[5][5] = {15, 25, 35, 45, 55,
             16, 26, 36, 46, 56,
             17, 27, 37, 47, 57,
             18, 28, 38, 48, 58,
             19, 29, 39, 49, 59};
    int row=0;
    int col=0;
    if(find(arr, 5, 48))
        printf("FOUND!!\n");
    else
        printf("NOT FOUND!!\n");
    getchar();
    return 0;
}