Hello everyone, in this article we are going to discuss a very famous DSA problem Search a 2D matrix(https://leetcode.com/problems/search-a-2d-matrix/). It is a leetcode mediumâ€“level problem. We will discuss the problem statement, solution approach, and different methods to solve the problem.

## Problem Statement

Write an efficient algorithm that searches for a value ** target** in an

**integer matrix**

*m x n***. This matrix has the following properties:**

*matrix*- Integers in each row are sorted from left to right
- The first integer of each row is greater than the last integer of the previous row

### Example 1

**Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3**Output:** true

### Example 2

**Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13**Output:** false

## Problem Explanation

This problem is very simple and straightforward. We have to search for an element in the 2D matrix, if the element is present in the matrix, we will return true else we will return false.

## Solutions to Search a 2D matrix: leetcode 74

### 1. Brute Force solution approach to the problem

For brute force we can traverse the matrix with the help of two for loops and compare every element with the element given, if any element matches the given element, we return true else we return false.

This approach requires O(N^2) time complexity and O(1) space complexity.

### 2. O(m*n) Approach

bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size(); for(int i = 0;i<m;i++) { for(int j = 0;j<n; j++) if(matrix[i][j] == target) return true; } return false; }

### 3. O(log(m*n)) Approach

We can reduce the time complexity of the question to O(log(m*n)) by using binary search on a 2D matrix.

Here we will see how we can apply binary search on 2D matrix, if we look at our problem carefully, our matrix is sorted, which gives a hint that binary search can be applied.

Let us say, the matrix in the image above is given as an example and we have to search 3.

We will start comparing from the top right element in our case 7, we compare this element to 3, 3 < 7 we shift to the left in the same row.

Now we are on 5, again 3 < 5, and we shift to more left.

Now if we compare, 3==3 so we will return true.

**C++ code for O(log(m*n)) Approach**

bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size(); //initializing I and j to top right element int i = 0, j = n - 1; //controlling the loop while(i >= 0 && i < m && j >= 0 && j < n) { //checking conditions if(matrix[i][j] < target) i++; else if(matrix[i][j] > target) j--; //returning true if element found else if(matrix[i][j] == target) return true; } //returning false if element not found. return false; }

**Also Read:**

- Download 1000+ Projects, All B.Tech & Programming Notes, Job, Resume & Interview Guide, and More – Get Your Ultimate Programming Bundle!
- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope