Question
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,
Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]
Origin from: LeetCode
Solution
// Time complexity: O(n+m) function findElement(arr, num) { var m = arr.length, n = arr[0].length, row = 0, col = n - 1; if (num < arr[0][0] || num > arr[m - 1][n - 1]) { return false; } while (row <= (n - 1) && col >= 0) { if (arr[row][col] < num) { row++; } else if (arr[row][col] > num) { col--; } else { console.log(row + " " + col); return true; } } return false; } var arr = [ [1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25] ]; findElement(arr, 16); // 3 0 findElement(arr, 23); // 4 2 findElement(arr, 9); // 1 3