Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Published

...

Code Block
languagego
func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)

    L, R := matrix[0][0], matrix[n-1][n-1]
    for L <= R {
        mid := L + (R - L) / 2

        c := count(matrix, mid)
        if c >= k {
            R = mid -
1         } else {
            L = mid + 1
        }
    }

    return LR
}

func count(matrix [][]int, x int) int {
    n := len(matrix)
    num := 0
    i, j := n-1, 0
    for i >= 0 && j < n {
        if matrix[i][j] <= x {
            num += i+1
            j++
        } else {
            i--
        }
    }
    return num
}