1. Description

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.

2. Runtime Distribution

3. Submission Details

4. Example

Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public boolean searchMatrix(int[][] matrix, int target)
{
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    int colLength = matrix[0].length;

    int i = matrix.length - 1;
    int j = 0;

    while (i >= 0 && j < colLength) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            i--;
        } else {
            j++;
        }
    }
    return false;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode0240 {
    public boolean searchMatrix(int[][] matrix, int target)
    {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int colLength = matrix[0].length;

        int i = matrix.length - 1;
        int j = 0;

        while (i >= 0 && j < colLength) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }

    public static void main(String[] args)
    {
        LeetCode0240 leetcode = new LeetCode0240();
        int[][] matrix = {
            { 1, 4, 7, 11, 15 },
            { 2, 5, 8, 12, 19 },
            { 3, 6, 9, 16, 22 },
            { 10, 13, 14, 17, 24 },
            { 18, 21, 23, 26, 30 }
        };
        System.out.println(leetcode.searchMatrix(matrix, 5));
    }
}

[/restab]
[/restabs]