Leetcode 240 - Search a 2D Matrix II
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Understanding the problem
The problem statement on LeetCode reads as follows:
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1:
Input: 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]], target = 5
Output: true
Example 2:
Input: 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]], target = 20
Output: false
Plan your solution
One way to solve this problem is to use a binary search algorithm. Since the rows and columns of the matrix are sorted in increasing order, we can use binary search to find the target value. Specifically, we can start at the top right corner of the matrix and compare the value at that position to the target value. If the value is less than the target value, we can move down one row because the values in that row will be greater than the value at the current position. If the value is greater than the target value, we can move left one column because the values in that column will be less than the value at the current position. We can repeat this process until we either find the target value or we determine that it is not in the matrix.
Implement your solution
Now that we have a plan, let’s implement it in Python.
def searchMatrix(matrix, target):
# Edge case: if the matrix is empty, return False
if not matrix:
return False
# Set the initial position to the top right corner of the matrix
row = 0
col = len(matrix[0]) - 1
# Search for the target value
while row < len(matrix) and col >= 0:
# Compare the value at the current position to the target value
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
# If the value is less than the target, move down one row
row += 1
else:
# If the value is greater than the target, move left one column
col -= 1
# If the value is not found, return False
return False
Test your solution
Testing is an important step in the software development process as it helps ensure that your code is correct and works as intended. In the case of the “Search a 2D Matrix II” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.
For example, we can test our solution with an empty matrix, a matrix with only one element, a matrix with multiple elements but no target value, and a matrix with multiple elements including the target value. We can also test our solution with matrices of different sizes and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Related:
- search a 2d matrix
- find the smallest divisor given a threshold
- search in rotated sorted array
- binary search
- unique binary search trees
- find the town judge with code
Related Posts
- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Leetcode 1027 - Longest Arithmetic Subsequence
- Question 1299 on leetcode
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- advanced-applications-of-binary-search
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 1283 - Find the Smallest Divisor Given a Threshold
- Leetcode 74 - Search a 2D Matrix
- Leetcode 300 - Longest Increasing Subsequence
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- a-binary-search-template
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together