Interview 150
Search a 2D Matrix
- Problem
- LC 74
- File
- interview150_LC74SearchA2DMatrix.java
- Path
- pkg5leetcode/interview150/interview150_LC74SearchA2DMatrix.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC74SearchA2DMatrix.java
- Approach
- Treat matrix as sorted array; binary search on flattened index.
- Complexity
- Time O(log(m*n)), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Search a 2D Matrix | LC 745 * APPROACH: Treat matrix as sorted array; binary search on flattened index.6 * COMPLEXITY: Time O(log(m*n)), Space O(1)7 */8public class interview150_LC74SearchA2DMatrix {9 static boolean searchMatrix(int[][] matrix, int target) {10 int m = matrix.length, n = matrix[0].length, lo = 0, hi = m * n - 1;11 while (lo <= hi) {12 int mid = (lo + hi) / 2, val = matrix[mid / n][mid % n];13 if (val == target) return true;14 if (val < target) lo = mid + 1;15 else hi = mid - 1;16 }17 return false;18 }19 20 public static void main(String[] args) {21 int[][] m = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};22 check(searchMatrix(m, 3), "case1");23 check(!searchMatrix(m, 13), "case2");24 System.out.println("all tests passed");25 }26 27 static void check(boolean cond, String name) {28 if (!cond) throw new AssertionError("FAILED: " + name);29 System.out.println(" PASS " + name);30 }31}