leetcode LargestDivisibleSubset

public class LargestDivisibleSubset {
  /**
   * Given a n x n matrix where each of the rows and columns are sorted in ascending order,
   * find the kth smallest element in the matrix.
   *
   * Note that it is the kth smallest element in the sorted order, not the kth distinct element.
   *
   * Example:
   *
   * matrix = [
   *    [ 1,  5,  9],
   *    [10, 11, 13],
   *    [12, 13, 15]
   * ],
   * k = 8,
   *
   * return 13.
   * Note:
   * You may assume k is always valid, 1 ≤ k ≤ n2.
   */
  public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int left = matrix[0][0];
    int right  = matrix[n-1][n-1];
    while(left < right){
      int mid = left + (right - left) >> 1;
      int count = getCount(matrix, mid);
      if (count < k){
        right = mid + 1;
      }
      else{
        left = mid;
      }

    }
    return left;
  }

  public int getCount(int[][] matrix, int mid){
    int i = matrix.length;
    int j = 0;
    int count = 0;
    while(j<matrix.length && i > 0){
      if (matrix[i][j] > mid){
        i --;
      }
      else {
        count += i +1;
        j ++;
      }
    }
    return count;
  }
}