BSEX06 - Editorial

editorial
,
1

Understanding the Problem

We are given an N x N grid where:

  1. Each row is sorted in ascending order.
  2. Each column is also sorted in ascending order.

Our task is to find the (k)-th smallest element in this sorted matrix without using extra space.

Key Observations

1. The Matrix is Sorted Both Row-wise and Column-wise

  • This means smaller values are concentrated at the top-left of the matrix, while larger values are at the bottom-right.
  • We can exploit this sorted structure to efficiently find the (k)-th smallest element.

2. Binary Search on Values Instead of Indexes

  • Since the smallest value is at matrix[0][0] and the largest value is at matrix[N-1][N-1], our search space is ([matrix[0][0], matrix[N-1][N-1]]).
  • We use binary search on the possible values rather than searching directly for the (k)-th smallest element.

Approach

1. Binary Search on Value Range

  • Step 1: Initialize left as matrix[0][0] (smallest value) and right as matrix[N-1][N-1] (largest value).
  • Step 2: Perform binary search:
    • Compute mid = (left + right) / 2).
    • Count the number of elements ≤ mid in the matrix.
    • If the count is ≥ k, it means the (k)-th smallest value might be mid, so we move left.
    • If the count is < k, it means the (k)-th smallest value must be larger, so we move right.

2. Counting Elements (≤ mid) Efficiently

To count the number of elements ≤ mid in (O(N)) time:

  1. Start from the top-right corner (matrix[0][N-1]).
  2. Move left while matrix[r][c] > mid.
  3. Add the count of all elements in that column before moving down.
  4. Repeat for all rows.

Time Complexity of Counting: (O(N))

Complexity Analysis

  • Binary search on values: O(log (max - min)), where max and min are the largest and smallest matrix values.
  • Counting elements ≤ mid: O(N) per iteration.

Total Complexity:
O(N log (max - min))