[Leetcode][240. Search a 2D Matrix II] 5 Approaches: BF, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis
By Long Luo
This article is the solution 5 Approaches: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis of Problem 240. Search a 2D Matrix II.
Here shows 5 Approaches to slove this problem: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis.
Intuition
This problem is like 74. Search a 2D Matrix, we can refer to the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis.
Brute Force
Just scan the to find the answer.
1 | public static boolean searchMatrix_bf(int[][] matrix, int target) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Binary Search(Row)
Use Binary Search method in each Row to find the answer.
1 | public boolean searchMatrix_bs_row(int[][] matrix, int target) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Binary Search(Diagonal, Row, Col)
This method is more difficult, we have to Binary Search method in each Diagonal, then each Row and each Column to find the answer.
1 | public static boolean searchMatrix_bs_3d(int[][] matrix, int target) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Binary Search(Global)
Consider the as a array, and the Binary Search the array.
1 | public static boolean searchMatrix_bs(int[][] matrix, int target) { |
Analysis
- Time Complexity: .
- Space Complexity: .
2D Coord Axis
The array increases from left to right and from top to bottom.
- Each column, all the numbers above are all smaller than it.
- Each row, the right of the number are all larger than it.
Therefore, the algorithm is as follows:
- From the bottom left corner of the array as the origin, take it as a coordinate axis;
- If the current number is larger than the , moves up;
- If the current number is less than the , move right.
1 | public static boolean searchMatrix_coord_left(int[][] matrix, int target) { |
Analysis
- Time Complexity: .
- Space Complexity: .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗