Leetcode 0074 Search 2d Matix

Meta Data

Link

• Search a 2D Matrix - LeetCode

Tags

• DSA Matrix
• Binary Search Algorithm

Similar

• Leetcode-0240-search-2D-matrix-ii

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example

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

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

Solution Approaches

O(N * M) Brute Force Linear Search

• Traverse through the entire matrix and check
• Basically Linear Search Algorithm

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(Log(N * M)) sO(1) Binary Search Entire

• First Element of each row is greated than last element of previous
• By the above property we can simply vizualize the this 2D matrix to be sorted 1D matrix
• If we can associate approriate indexes of that 1D matix to 2D then we this problem simplies to a plain Binary Search Algorithm
• Indexes of 1D matrix are of formed by mat2D[i][j] = mat1D[i*(n) + j]

| (i,j) | 0     | 1     | 3     | 3     | 4     |
| ----- | ----- | ----- | ----- | ----- | ----- |
| 0     | (0,0) | (0,1) | (0,2) | (0,3) | (0,4) |
| 1     | (1,0) | (1,1) | (1,2) | (1,3) | (1,4) |
| 2     | (2,0) | (2,1) | (2,2) | (2,3) | (2,4) |
| 3     | (3,0) | (3,1) | (3,2) | (3,3) | (3,4) |

| (n * i + j) | 0   | 1   | 3   | 3   | 4   |
| ----------- | --- | --- | --- | --- | --- |
| 0           | 0   | 1   | 2   | 3   | 4   |
| 1           | 5   | 6   | 7   | 8   | 9   |
| 2           | 10  | 11  | 12  | 13  | 14  |
| 3           | 15  | 16  | 17  | 18  | 19  |

    int getval(vector<vector<int>> &matrix, int mid){
        int n = (matrix[0].size());
        return matrix[mid/n][mid%n];
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int low = 0;
        int high = matrix.size() * matrix[0].size() - 1 ;

        while (low <= high) {
            int mid = (low + high) / 2;
            int midval = getval(matrix, mid);
            if (midval == target) {return true;}
            else if (midval < target) {
                low = mid + 1;
            }
            else {
                high = mid-1;
            }
        }
        return false;

    }

Return to DSA