Leetcode 0240 Search 2d Matrix Ii

Meta Data

Tags

Similar

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 * 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
  • 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


Notes mentioning this note