NUHMAN.com

🔍 Problem Statement

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 from left to right.
• Integers in each column are sorted from top to bottom.

Given a target value, return true if the target exists in the matrix and false otherwise.

Example 1:

go

Input: matrix = [
    [1,   4,  7, 11],
    [2,   5,  8, 12],
    [3,   6,  9, 16],
    [10, 13, 14, 17]
], target = 5
Output: true

Example 2:

go

Input: matrix = [
    [1,   4,  7, 11],
    [2,   5,  8, 12],
    [3,   6,  9, 16],
    [10, 13, 14, 17]
], target = 20
Output: false

🧠 Approach

Given the properties of the matrix, where each row and column is sorted, a brute-force approach would involve searching through every element, which could take O(m * n) time. However, we can optimize the search using a more efficient approach.

We can exploit the structure of the matrix to perform the search in O(m + n) time. The key idea is to start from the top-right corner of the matrix:

1. If the current element is equal to the target, we've found the target and return true.
2. If the current element is greater than the target, move left (because all elements to the left are smaller than the current element).
3. If the current element is smaller than the target, move down (because all elements below are larger than the current element).

This approach ensures that we are eliminating one row or column with each step, making the search efficient.

Steps:

1. Start at the top-right corner of the matrix (matrix[0][n-1]).
2. If the current element is equal to the target, return true.
3. If the current element is greater than the target, move left (decrease column).
4. If the current element is smaller than the target, move down (increase row).
5. Continue this process until you either find the target or exceed the boundaries of the matrix.

✅ Go Implementation

go

package main

import "fmt"

// Function to search for a target in the matrix
func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    row, col := 0, len(matrix[0])-1 // Start at the top-right corner

    // Loop through the matrix
    for row < len(matrix) && col >= 0 {
        if matrix[row][col] == target {
            return true // Found the target
        } else if matrix[row][col] > target {
            col-- // Move left
        } else {
            row++ // Move down
        }
    }

    return false // Target not found
}

// Helper function to print the result
func printResult(result bool) {
    if result {
        fmt.Println("True")
    } else {
        fmt.Println("False")
    }
}

// Test the searchMatrix function
func main() {
    // Example 1: matrix = [
    //     [1,  4,  7, 11],
    //     [2,  5,  8, 12],
    //     [3,  6,  9, 16],
    //     [10, 13, 14, 17]
    // ]
    matrix1 := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    target1 := 5
    result1 := searchMatrix(matrix1, target1)
    printResult(result1) // Output: True

    // Example 2: matrix = [
    //     [1,  4,  7, 11],
    //     [2,  5,  8, 12],
    //     [3,  6,  9, 16],
    //     [10, 13, 14, 17]
    // ]
    matrix2 := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    target2 := 20
    result2 := searchMatrix(matrix2, target2)
    printResult(result2) // Output: False
}

🧑‍💻 Explanation of the Code

1. searchMatrix function:

• Initial Check: We first ensure that the matrix is non-empty.
• Start at the top-right corner: We initialize the row index to 0 and the col index to the last column (len(matrix[0])-1).
• Search Logic:
• If the current element equals the target, return true.
• If the current element is greater than the target, move left (decrease the column).
• If the current element is less than the target, move down (increase the row).
• The loop continues as long as we have valid positions within the matrix.

1. printResult function:

• A helper function to print the result as either True or False.

1. main function:

• Tests the searchMatrix function with two example inputs.

📦 Example Usage

go

func main() {
    // Example 1: matrix = [
    //     [1,  4,  7, 11],
    //     [2,  5,  8, 12],
    //     [3,  6,  9, 16],
    //     [10, 13, 14, 17]
    // ]
    matrix1 := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    target1 := 5
    result1 := searchMatrix(matrix1, target1)
    printResult(result1) // Output: True

    // Example 2: matrix = [
    //     [1,  4,  7, 11],
    //     [2,  5,  8, 12],
    //     [3,  6,  9, 16],
    //     [10, 13, 14, 17]
    // ]
    matrix2 := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    target2 := 20
    result2 := searchMatrix(matrix2, target2)
    printResult(result2) // Output: False
}

Example Output:

graphql

True
False

⏱️ Time & Space Complexity

• Time Complexity: O(m + n)
• We are traversing the matrix diagonally, eliminating either a row or a column at each step, so the time complexity is proportional to the sum of the number of rows and columns, O(m + n).
• Space Complexity: O(1)
• We only use a constant amount of space for variables such as row and col. No extra space is required.

This solution efficiently searches the matrix in linear time relative to its dimensions.