Search in a Row and Column Wise Sorted Matrix
Binary Search on 2D Arrays DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Searching for a target value in a 2D matrix where each row and column is sorted in non-decreasing order, Matrices, Two-dimensional Array Traversal, Binary Search, Brute Force, Time Complexity, Space Complexity, Big O Notation, Loops, Optimization, Arrays, matrix, matrix search, search algorithms, binary search, time complexity analysis, Matrix Search.
Search in a 2D Sorted Matrix Problem Statement You have been given a 2 D array mat of size N x M where N and M denote the number of rows and columns, respectively. The elements of each row and each column are sorted in non decreasing order. However, the first element of a row is not necessarily greater than the last element of the previous row (if it exists). You are given an integer target, and your task is to find if it exists in the given mat or not. Input Format The first line contains three integers: N (number of rows), M (number of columns), and target (the integer to search for). The next N lines contain M integers each, representing the elements of the mat matrix. Output Format Return true if the target exists in the matrix, false otherwise. Examples Example 1: Input: N = 5, M = 5, target = 14 mat = Output: Explanation: Target 14 is present in the cell (3, 2)(0 based indexing) of the matrix. Example 2: Input: N = 3, M = 3, target = 12 mat = Output: Explanation: As target 12 is not present in the matrix, the answer is false.