algoadvance

Leetcode 240. Search a 2D Matrix II

Problem Statement

LeetCode Problem 240: Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.

Example:

Consider the following 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]
]

Given target = 5, return true.

Given target = 20, return false.

Clarifying Questions

1. What should be returned if the target is found?
   • If the target is found, return true.
2. What should be returned if the target is not found?
   • If the target is not found, return false.
3. Are there any constraints on the size of the matrix?
   • The constraints are typical of a 2D matrix and we can assume the matrix can be large.

Strategy

To efficiently search the matrix given the sorted properties, we can use the following strategy:

1. Start from the Top-Right Corner:
   • Begin the search at the top-right element of the matrix (i.e., matrix[0][n-1]).
   • This leverages the sorted properties because:
     • Moving to the left decreases the value.
     • Moving down increases the value.
2. Iteratively Adjust Search Position:
   • If the current element is equal to the target, return true.
   • If the current element is greater than the target, move left.
   • If the current element is less than the target, move down.
3. End Conditions:
   • The search will end when the boundary of the matrix is crossed (running out of rows or columns).

This strategy ensures that each step either moves down or left, and each element is visited at most once, resulting in a time complexity of O(m + n), where m is the number of rows and n is the number of columns.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size();
        int n = matrix[0].size();
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // move left
            } else {
                row++; // move down
            }
        }

        return false; // target not found
    }
};

Time Complexity

• O(m + n): In the worst case, we may need to traverse the entire height (m) and width (n) of the matrix. Each step moves either left or down, ensuring that each element is checked at most once.

This approach provides an efficient search mechanism for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?