Leetcode 378 - Kth Smallest Element in a Sorted Matrix

Prompt: Given an n x n integer matrix, all integers are sorted from smallest to largest from left to right and also from top to bottom. The prompt will also give an integer k. The goal is to return kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Input: matrix = [[-5]], k = 1
Output: -5

Solution: We can use a binary search solution since the matrix is sorted. For the binary search, we have to count how many elements in the matrix that are smaller than the mid value. To initialize the mid value, we can take the smallest and biggest elements in the matrix. For each loop, if the count is greater than k then we have to update the biggest value with the mid and if the count is smaller than k then we have to update the smallest value with the mid. The runtime for this solution is O(n² log n) since we have a binary search and each loop of the binary search we had to search the matrix to count all elements smaller than the mid value.