SimuVedaAlgorithms Lab Open in the lab

Searching / Intermediate

Search a Sorted 2D Matrix Visualizer

Start at the top-right corner. Everything left of it in its row is smaller and everything below it in its column is bigger. Too big: step left and drop that column. Too small: step down and drop that row.

Start the Search a Sorted 2D Matrix simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(r + c)
Worst timeO(r + c)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Rows and columns are both sorted. Start at the top-right corner, row 0, column 3.
  2. Look at row 0, column 3: 7.
  3. 7 < 16, and everything to its left is even smaller. Drop row 0 and step down.
  4. Look at row 1, column 3: 20.
  5. 20 > 16, and everything below it is even bigger. Drop column 3 and step left.
  6. Look at row 1, column 2: 16.
  7. 16 is the target. Found in 3 steps.

Try it with your own input →

Search a sorted 2D matrix in Java, Python, C++, C and JavaScript

boolean searchMatrix(int[][] m, int t) {
  int r = 0, c = m[0].length - 1;
  while (r < m.length && c >= 0) {
    if (m[r][c] == t) return true;
    if (m[r][c] > t) c--;
    else r++;
  }
  return false;
}
def search_matrix(m, t):
    r, c = 0, len(m[0]) - 1
    while r < len(m) and c >= 0:
        if m[r][c] == t:
            return True
        if m[r][c] > t:
            c -= 1
        else:
            r += 1
    return False
bool searchMatrix(const vector<vector<int>>& m, int t) {
  int r = 0, c = (int)m[0].size() - 1;
  while (r < (int)m.size() && c >= 0) {
    if (m[r][c] == t) return true;
    if (m[r][c] > t) c--;
    else r++;
  }
  return false;
}
int searchMatrix(int rows, int cols, int m[rows][cols], int t) {
  int r = 0, c = cols - 1;
  while (r < rows && c >= 0) {
    if (m[r][c] == t) return 1;
    if (m[r][c] > t) c--;
    else r++;
  }
  return 0;
}
function searchMatrix(m, t) {
  let r = 0, c = m[0].length - 1;
  while (r < m.length && c >= 0) {
    if (m[r][c] === t) return true;
    if (m[r][c] > t) c--;
    else r++;
  }
  return false;
}

In an interview

LeetCode 240, Search a 2D Matrix II: rows and columns are both sorted. Find the target. (LeetCode 74 is the stricter version.)

Each step throws away a whole row or column, so it takes at most rows + columns steps. The bottom-left corner works too; the top-left does not, because both moves would make the value bigger.

More searching