Search an element in a row wise and column wise sorted Matrix

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

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

[
  [1,   4,  7],
  [2,   5,  8],
  [3,   6,  9],
]

Given above matrix:

• Target = 5 return true
• Target = 11 return false

 

Approach: We need to start with an element where we can clearly decide on which side we should go in case target is less than the current element or greater than the current element.

As given matrix is row wise sorted and column wise sorted. We can start either from Top-Right corner (0, n - 1) or Bottom-Left corner (m - 1, 0). I am taking Top-right corner(row = 0, col = n - 1). Let's see how it works; at every element, there could be three conditions:

1. Matrix[row][col] == target, we get our answer, return true.
2. Matrix[row][col] > target, col = col - 1 as we are looking for smaller value
3. Matrix[row][col] < target, row = row + 1 as we are looking for greater value

Implementation in C#:

        public bool SearchRowSortedAndColSortedMatrix(int[,] matrix, int target)

        {

            int row = 0, col = matrix.GetLength(1) - 1;

            while(row >= 0 && row < matrix.GetLength(0) && col >= 0 && col < matrix.GetLength(1))

            {

                if (matrix[row, col] == target)

                {

                    return true;

                }

                else if (matrix[row, col] > target)

                {

                    --col;

                }

                else

                {

                    ++row;

                }

            }

            return false;

        }

Complexity: O(m + n)