BSEX01 - Editorial

Understanding the Problem

We are given an N x M matrix with two important properties:

  1. Each row is sorted in ascending order.
  2. The first integer of each row is greater than the last integer of the previous row.

Given an integer Target, we need to determine if it exists in the matrix.

Key Observations

  • The matrix is structured in a way that if we flatten it row-wise, it would form a fully sorted 1D array.
  • This means that we can use binary search, which efficiently searches for elements in a sorted array.

Approach

Since the matrix can be conceptually treated as a sorted 1D array, we can apply binary search directly. Instead of manually flattening the matrix, we use mathematical indexing to map a 1D index into 2D row-column coordinates:

  • Index Mapping:
    • Consider the matrix as a 1D array where each index (i) corresponds to:
      • Row: i / M
      • Column: i % M

Using this, we can access the value at any index without explicitly converting the matrix into an array.

Binary Search Execution

  1. Initialize two pointers:

    • left = 0 (beginning of the matrix)
    • right = N * M - 1 (last index in the conceptual 1D array)
  2. Run a binary search:

    • Compute mid = (left + right) / 2.
    • Convert mid into row and column using the formulas above.
    • If matrix[mid / M][mid % M] equals target, return True.
    • If matrix[mid / M][mid % M] is less than target, move left to mid + 1.
    • Otherwise, move right to mid - 1.
  3. If the loop ends without finding the target, return False.

Complexity Analysis

Since we are performing binary search on a sorted N x M matrix, the time complexity is:

O(log (N x M)) = O(log N + log M)

  • The space complexity is O(1) as we use only a few extra variables.
  • This is faster than O(N + M), which would be the complexity of a naive row-wise or column-wise search.