Kth Smallest Element in a Sorted Matrix

class Solution {

  public int findKthSmallest(int[][] matrix, int k) {

    int size = matrix.length;
    int low = matrix[0][0], high = matrix[size - 1][size - 1];
    while (low < high) {

      int mid = low + (high - low) / 2;
      int[] minMaxPair = {matrix[0][0], matrix[size - 1][size - 1]};

      int count = this.countLessOrEqual(matrix, mid, minMaxPair);

      if (count == k) return minMaxPair[0];

      if (count < k) low = minMaxPair[1]; // search right
      else high = minMaxPair[0]; // search left
    }
    return low;
  }

  private int countLessOrEqual(int[][] matrix, int mid, int[] minMaxPair) {

    int count = 0;
    int size = matrix.length, row = size - 1, col = 0;

    while (row >= 0 && col < size) {

      if (matrix[row][col] > mid) {

        // Updates the smallest number greater than the middle value
        minMaxPair[1] = Math.min(minMaxPair[1], matrix[row][col]);
        row--;

      } else {

        // Updates the largest number less than the middle value
        minMaxPair[0] = Math.max(minMaxPair[0], matrix[row][col]);
        count += row + 1;
        col++;
      }
    }

    return count;
  }
}

The given Java class, Solution, presents a way to solve the problem of finding the k-th smallest element in a sorted matrix. The method findKthSmallest is pivotal in how this solution operates, using a binary search approach to efficiently narrow down the possible values until the k-th smallest element is identified.

Here's how the solution operates:

• The binary search is set up between the smallest element in the matrix, at matrix[0][0], and the largest element, at matrix[size-1][size-1].
• During each iteration of the while loop, the mid-value of the current range (low to high) is calculated.
• A pair, minMaxPair, initializes as the smallest and largest possible values from the matrix and aids in adjusting the search bounds.
• The countLessOrEqual function is called with the current middle value mid, and it returns the number of elements that are less than or equal to mid. It also updates minMaxPair to reflect the smallest value greater than mid and the largest value less than mid that are encountered during its execution.
  • The function increments the count of qualifying elements by navigating through the matrix, adjusting its count based on the positioning relative to mid.
• If the count matches k, minMaxPair[0] is returned as it represents the k-th smallest value.
• Depending on whether the count is lesser or greater than k, the search range is updated to either the right or the left segment respectively.
• The loop continues until low equals high, which then low is returned as the result.

Throughout the process, this implementation leverages the sorted property of the matrix for efficient searching and counting, making it capable of handling large matrices with a time complexity better than a direct sorting approach which is typically O(n log n). This focused binary search ensures the method achieves the desired result with optimized performance.

class Solution:

    def countLEQ(self, matrix, threshold, lowerBound, upperBound):
        
        elementsCount, dimension = 0, len(matrix)
        idxRow, idxCol = dimension - 1, 0
        
        while idxRow >= 0 and idxCol < dimension:
            if matrix[idxRow][idxCol] > threshold:
                upperBound = min(upperBound, matrix[idxRow][idxCol])
                idxRow -= 1
            else:
                lowerBound = max(lowerBound, matrix[idxRow][idxCol])
                elementsCount += idxRow + 1
                idxCol += 1

        return elementsCount, lowerBound, upperBound
    
    def findKthSmallest(self, matrix: List[List[int]], k: int) -> int:
        
        dimension = len(matrix)
        lower, upper = matrix[0][0], matrix[dimension - 1][dimension - 1]
        
        while lower < upper:
            middle = lower + (upper - lower) / 2
            minElement, maxElement = matrix[0][0], matrix[dimension - 1][dimension - 1]

            count, minElement, maxElement = self.countLEQ(matrix, middle, minElement, maxElement)

            if count == k:
                return minElement
            if count < k:
                lower = maxElement  # search in higher range
            else:
                upper = minElement  # search in lower range

        return lower

The problem "Kth Smallest Element in a Sorted Matrix" involves finding the kth smallest element in an n x n matrix sorted in non-decreasing order both row-wise and column-wise. This Python solution efficiently determines the answer using a binary search approach combined with a counting mechanism.

• Initialize the binary search bounds, lower and upper, as the first and last elements in the matrix, respectively.

• Within the binary search, calculate the middle value between the current lower and upper.

• Count how many matrix elements are less than or equal to this middle value. This count is done via the countLEQ method which iterates through the matrix efficiently by comparing elements.

  • Begin from the bottom-left corner of the matrix. If the current element is greater than the middle value, reduce the row index to move upwards; otherwise, increase the column index; this maintains the sorted order properties of the matrix.
  • Simultaneously, adjust the lowerBound and upperBound for the next iteration based on the currently considered element in the matrix.

• Check the count of elements:

  • If the count exactly matches k, the minElement (lower bound reached during counting) is our answer.
  • If the count is less than k, focus the next iteration on the upper half of our search range.
  • Conversely, if the count is greater than k, adjust to search in the lower half.

• The search continues until lower converges with upper, which will then hold the value of the kth smallest element.

Through the use of binary search and a specific counting method, this solution handles the task with improved complexity over naive methods, effectively leveraging the sorted properties of the matrix.