Search 2D Array Matrix with Python #dsa #coding #interviewpreparation #binarysearch #leetcode

Question: Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.

# The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Approach: Binary Search

Perform binary search on a 2D matrix to find a target value. To do this, convert the 2D matrix into a 1D list, to apply binary search. Set up `left` and `right` pointers for the binary search and return `True` if the target is found, `False` otherwise.

Explanation:

Instead of searching in the 2D matrix directly, the code flattens it into a 1D list by mapping each 2D index `(i, j)` to a 1D index `i * number_of_columns + j`. This simplifies the search. The binary search then compares the middle element of the 1D list with the target value.

Time Complexity: O(log(n*m))

Space Complexity: O(1)

#softwareengineer #dsa #interviewpreparation