Solving the LeetCode "Search a 2D Matrix" Problem in Go

Difficulty: Medium | Tags: Array, Binary Search, Matrix

Introduction

The "Search a 2D Matrix" problem requires efficiently searching for a target value in a matrix with specific sorted properties. The challenge lies in achieving O(log(m * n)) time complexity, which suggests using binary search.

Problem Analysis

The matrix is sorted row-wise and column-wise, with each row's first element greater than the previous row's last element. This structure allows treating the matrix as a single sorted array, enabling binary search.

Solution Approach

We can perform binary search by flattening the matrix conceptually. The midpoint is calculated, and its corresponding row and column indices are derived. The target is compared with the midpoint value to adjust the search range.

Go Implementation

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    rows := len(matrix)
    cols := len(matrix[0])
    left := 0
    right := rows * cols - 1
    for left <= right {
        mid := left + (right - left) / 2
        midValue := matrix[mid / cols][mid % cols]
        if midValue == target {
            return true
        } else if midValue < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

Complexity Analysis

The time complexity is O(log(m * n)) due to binary search. The space complexity is O(1) as no additional data structures are used.

Testing and Examples

Test cases include:
1. Target present in the matrix (Example 1).
2. Target absent in the matrix (Example 2).
3. Empty matrix.
4. Single-element matrix with and without the target.

Best Practices and Tips

Ensure boundary conditions are handled, such as empty matrices. Use integer division and modulus to map the flattened index back to 2D indices. Always verify edge cases to avoid off-by-one errors.