NUHMAN.com

Introduction

LeetCode 74: Search a 2D Matrix is a classic algorithmic problem that tests your ability to apply binary search in a non-traditional way. Instead of a 1D array, we’re dealing with a 2D matrix, but the matrix's properties make it possible to flatten it conceptually and perform a binary search on it efficiently.

This is a popular interview question and is excellent for learning how to adapt binary search to solve matrix problems.

Problem Statement

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

1. Integers in each row are sorted from left to right.
2. The first integer of each row is greater than the last integer of the previous row.

Example:

go

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

Output: true
go

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

Output: false

Approach: Binary Search

Although it's a 2D matrix, due to its structure, we can treat it like a flattened 1D array.

Steps:

1. Imagine the matrix as a flattened 1D array of size m * n.
2. Apply binary search on this array:

• Calculate the mid index.
• Convert the 1D index back to 2D using:
• row = mid / n
• col = mid % n
• Compare the value at matrix[row][col] with the target.

Go Implementation

go

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1

    for left <= right {
        mid := (left + right) / 2
        row := mid / n
        col := mid % n
        midVal := matrix[row][col]

        if midVal == target {
            return true
        } else if midVal < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return false
}

Explanation

• We convert a 2D matrix into a virtual 1D array to apply binary search.
• mid / n gives us the row index.
• mid % n gives us the column index.
• We compare the value at that position with the target and update our search range accordingly.

Time and Space Complexity

MetricComplexityTime ComplexityO(log(m * n))Space ComplexityO(1)

Where m is the number of rows and n is the number of columns in the matrix.

Edge Cases

• Empty matrix or rows.
• Target smaller than the smallest element.
• Target greater than the largest element.
• Matrix with only one element.

Conclusion

LeetCode 74 is a perfect example of adapting traditional algorithms like binary search to solve problems on structured 2D data. Understanding how to map 2D indices to 1D space is a key insight that can be applied in many other problems too.

By solving this in Go, you get familiar with pointerless low-level control and efficient use of loops and conditions—great practice for systems or backend-focused interviews!