Kth Smallest Element in a Sorted Matrix

LeetCode Q 378 - Kth Smallest Element in a Sorted Matrix

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.

Solution

Solution 1: Heap

1. we offer the numbers in the first row to the que.
2. we do the following k - 1 times: Poll a number and offer the number below it to the que if it has.
3. the value of the first item in the queue is the answer

Time Complexity: O(klogn)
Space Complexity: O(n)
k: how many times we do the loop.   n: matrix row no.

Code:

public int kthSmallest(int[][] matrix, int k) {
	// int[] arr = {val, row, col};
	Queue<\int[]> pq = new PriorityQueue<>((a,b) -> (a[0] - b[0]));
	for (int i = 0; i < matrix[0].length; i++) 
		pq.offer(new int[]{matrix[0]\[i], 0, i});
    
	while (k != 1) {
		int[] temp = pq.poll();
		if (temp[1] + 1 < matrix.length)
			pq.offer(new int[]{matrix[temp[1] + 1][temp[2]], temp[1] + 1, temp[2]});
		k--;
	}
    
	return pq.peek()[0]; 
}

Solution 2: Binary Search

1. choose matrix[0][0] as left and matrix[n-1][n-1] as right, and get the mid.
2. count the number of numbers less or equal to mid.

• if (number < k): this mid is smaller than the target, so we let left = mid + 1;
• if (number > k): this mid is larget than the target, so we let right = mid - 1;
• if (number == k): there exists two cases. 1) this mid may be the target 2) this mid is not in the matrix and larger than the target

Then we keep shrinking the range, let right = mid - 1, this guarantees left is the kthSmallest

Time Complexity: O(logRange*nlogn)
Every time we call the count method, it costs O(nlogn) time.
The maximum range is Integer.MAX_VALUE - Integer.MIN_VALUE = 2^23 - 1. So logRange is no more than 32, which can be regarded as a constant.
So the time complexity if O(nlogn).
Space Complexity: O(1)
k: how many times we do the loop.   n: matrix row no.

Code:

public int kthSmallest(int[][] matrix, int k) {
	int n = matrix.length, left = matrix[0]\[0], right = matrix[n-1]\[n-1];
	while (left <= right) {
		int mid = left + (right - left) / 2;
		int count = countLessEqual(matrix, mid, n);
		if (count < k)
			left = mid + 1;
		else // mid >= k
			right = mid - 1;
	}
	return left;
}

private int countLessEqual(int[][] matrix, int target, int n) {
	int res = 0;
	for (int[] numbers: matris) {
		int left = 0, right = n - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (numbers[mid] > target) right = mid - 1;
			else left = mid + 1;
		}
		res += left;
	}
	return res;
}

Solution 3: Optimized Solution based on Solution 2

We optimize the countLessEqual Method. This method is similar to Search a 2D Matrix II.

Time Complexity: O(n)
Space Complexity: O(1)
k: how many times we do the loop.   n: matrix row no.

Code:

public int kthSmallest(int[][] matrix, int k) {
	int n = matrix.length, left = matrix[0]\[0], right = matrix[n-1]\[n-1];
	while (left <= right) {
		int mid = left + (right - left) / 2;
		int count = countLessEqual(matrix, mid, n);
		if (count < k)
			left = mid + 1;
		else // mid >= k
			right = mid - 1;
	}
	return left;
}

private int countLessEqual(int[][] matrix, int target, int n) {
	int res = 0;
	int row = 0, col = n - 1;
	whiel (left < n && col >= 0) {
		if (matrix[row]\[col] <= target) {
			res += col + 1; row++;
		} else {
			col--;
		}
	}
	return res;
}

Comparison of time complexities of Solution 1 and Solution3:

k	O(1)	O(n)	O(n^2)
Solution 1:	logn	nlogn	n^2*logn
Solution 3:	n	n	n

When k is constant, Solution 1 is better. Otherwise Solution 2 is better.