Leetcode 0240 Search 2d Matrix Ii

Meta Data

Link

• Search a 2D Matrix II - LeetCode

Tags

• DSA Matrix
• Binary Search Algorithm

Similar

• Other solutions at Leetcode-0074-search-2D-matix

Problem Statement

• Write an efficient algorithm that searches for a value target in an m x n integer matrix 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

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

Solution Approaches

O(N * M) Brute Force Linear Search

• Implement a simple Linear Search Algorithm for matrix

O(N * Log(M)) Binary Search Row Wise

• As rows are sorted perform Binary Search Algorithm on each
• If target is not found at the end of search then move to the next row
• Time for binary search is log M which is applied on N rows so O(N * Log(M)) in total.

O(N+M) Top Right Approach

• Link
  • 21 Search in Row wise And Column wise Sorted Array - YouTube by [[ Aditya Verma ]]
• Using Row Wise Column Wise Sorted Property
  • For any element a[i][j] the following is true
    • Elements towards left are always smaller
      • a[0][j] a[1][j] ... a[i-1][j] < a[i][j]
    • Elements towards down are always bigger
      • a[i][j+1] a[i][j+2] ... a[i][m] > a[i][j]
  • This makes the property applicable for Binary Search Algorithm type implementation
  • Starting from Top Left we can move in two directions down to get larger and left to get smaller

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int m = matrix.size() - 1;
	int n = matrix[0].size() - 1;

	int i = 0;
	int j = n;

	while (i <= m and j >= 0) {
		if (matrix[i][j] == target) {return true;}
		else if (matrix[i][j] < target) {i++;}
		else {j--;}
	}
	return false;
}

Return to DSA