HomeLeetcode240. Search a 2D Matrix II - Leetcode Solutions
Leetcode

240. Search a 2D Matrix II – Leetcode Solutions

Declan Clarke

Description

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.

Examples:

Example 1:

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

Example 2:

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 = 20
Output: false

Solution in Python

Approach:

  1. Matrix Properties:
    • Each row is sorted from left to right.
    • Each column is sorted from top to bottom.
  2. Optimal Approach:
    • Start from the top-right corner of the matrix.
    • If the current element is greater than the target, move left (to reduce the value).
    • If the current element is less than the target, move down (to increase the value).
    • This allows us to efficiently eliminate either an entire row or column in each step.
  3. Time Complexity:
    • Since we traverse either left or down in each step, the algorithm runs in O(m + n) time, where m is the number of rows and n is the number of columns.
Python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Step 1: Get the dimensions of the matrix
        if not matrix or not matrix[0]:
            return False  # Handle edge case of empty matrix
        
        rows = len(matrix)    # Number of rows in the matrix
        cols = len(matrix[0]) # Number of columns in the matrix
        
        # Step 2: Start at the top-right corner of the matrix
        row = 0               # Row pointer starts at the first row
        col = cols - 1        # Column pointer starts at the last column
        
        # Step 3: Iterate while row and col are within bounds
        while row < rows and col >= 0:
            current_value = matrix[row][col]
            
            # Step 4: Compare current value with the target
            if current_value == target:
                return True  # Target found
            
            # Step 5: If current value is greater than the target, move left
            elif current_value > target:
                col -= 1  # Move to the left column
            
            # Step 6: If current value is less than the target, move down
            else:
                row += 1  # Move to the next row
        
        # Step 7: If we exit the loop, target is not found
        return False

Explanation of Each Step:

  1. Matrix and Edge Case:
    • First, we check if the matrix or the first row is empty. If so, we return False because there’s nothing to search.
  2. Initialize Pointers:
    • We start from the top-right corner (matrix[0][cols - 1]), which is the largest element in the first row and the smallest element in the last column.
  3. Traverse the Matrix:
    • If the current element is equal to the target, we return True.
    • If the current element is larger than the target, it means we need a smaller value, so we move left (decrement the column).
    • If the current element is smaller than the target, we need a larger value, so we move down (increment the row).
  4. Return False:
    • If we exhaust the matrix without finding the target, return False.

Solution in C++

C++
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Step 1: Check if the matrix is empty or has no columns
        if (matrix.empty() || matrix[0].empty()) {
            return false; // Handle the edge case where the matrix is empty
        }
        
        // Step 2: Get the number of rows and columns
        int rows = matrix.size();        // Number of rows in the matrix
        int cols = matrix[0].size();     // Number of columns in the matrix
        
        // Step 3: Initialize row and column pointers
        int row = 0;          // Start at the first row
        int col = cols - 1;   // Start at the last column (top-right corner)
        
        // Step 4: Traverse the matrix while within bounds
        while (row < rows && col >= 0) {
            int current_value = matrix[row][col]; // Current element
            
            // Step 5: If the current value is the target, return true
            if (current_value == target) {
                return true;  // Target found
            }
            
            // Step 6: If the current value is greater than the target, move left
            else if (current_value > target) {
                col--;  // Move left to reduce the value
            }
            
            // Step 7: If the current value is less than the target, move down
            else {
                row++;  // Move down to increase the value
            }
        }
        
        // Step 8: If we finish the loop without finding the target, return false
        return false;  // Target not found
    }
};

Solution in Javascript

JavaScript
var searchMatrix = function(matrix, target) {
    // Step 1: Check if matrix is empty or has no columns
    if (matrix.length === 0 || matrix[0].length === 0) {
        return false; // Return false if matrix is empty
    }
    
    // Step 2: Initialize variables to track the current position
    let rows = matrix.length;         // Number of rows in the matrix
    let cols = matrix[0].length;      // Number of columns in the matrix
    
    let row = 0;         // Start at the first row
    let col = cols - 1;  // Start at the last column (top-right corner)
    
    // Step 3: Traverse the matrix while within bounds
    while (row < rows && col >= 0) {
        let currentVal = matrix[row][col]; // Get the current value
        
        // Step 4: Check if the current value matches the target
        if (currentVal === target) {
            return true; // Target found
        }
        
        // Step 5: If current value is greater than the target, move left
        if (currentVal > target) {
            col--; // Move left to reduce the value
        } 
        // Step 6: If current value is less than the target, move down
        else {
            row++; // Move down to increase the value
        }
    }
    
    // Step 7: If the loop completes without finding the target, return false
    return false; // Target not found
};

Solution in Java

Java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Step 1: Check if the matrix is empty or has no columns
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false; // Return false if matrix is empty or invalid
        }
        
        // Step 2: Initialize rows and columns for traversal
        int rows = matrix.length;       // Number of rows in the matrix
        int cols = matrix[0].length;    // Number of columns in the matrix
        
        // Step 3: Start from the top-right corner of the matrix
        int row = 0;          // Start at the first row
        int col = cols - 1;   // Start at the last column (top-right corner)
        
        // Step 4: Traverse the matrix while staying within the bounds
        while (row < rows && col >= 0) {
            // Get the current value in the matrix
            int currentValue = matrix[row][col];
            
            // Step 5: Check if the current value matches the target
            if (currentValue == target) {
                return true; // Target found, return true
            }
            
            // Step 6: If the current value is greater than the target, move left
            if (currentValue > target) {
                col--; // Move left to reduce the value
            }
            // Step 7: If the current value is less than the target, move down
            else {
                row++; // Move down to increase the value
            }
        }
        
        // Step 8: If we exit the loop without finding the target, return false
        return false; // Target not found
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com