240. Search a 2D Matrix II

Difficulty:
Related Topics:
Similar Questions:

Problem

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

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]
]

Example 1:

Input: matrix, target = 5
Output: true

Example 2:

Input: matrix, target = 20
Output: false

Solution

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  var n = matrix.length;
  var m = (matrix[0] || []).length;
  var x = m - 1;
  var y = 0;
  var tmp = 0;
  while (x >= 0 && y < n) {
    tmp = matrix[y][x];
    if (target === tmp) {
      return true;
    } else if (target > tmp) {
      y++;
    } else {
      x--;
    }
  }
  return false;
};

Explain:

nope.

Complexity: