[Leetcode][378. Kth Smallest Element in a Sorted Matrix] 3 Approaches: Sorting, Merge Sort, Binary Search

By Long Luo

This article is the solution 3 Approaches: Sorting, Merge Sort, Binary Search of Problem 378. Kth Smallest Element in a Sorted Matrix.

Here shows 3 Approaches to slove this problem: Sorting, Merge Sort, Binary Search.

Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] array = new int[n * n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
array[i * n + j] = matrix[i][j];
}
}

Arrays.sort(array);

return array[k - 1];
}

Analysis

  • Time Complexity: \(O(n^2logn)\)
  • Space Complexity: \(O(n^2)\)

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;

PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);

for (int i = 0; i < n; i++) {
pq.offer(new int[]{matrix[i][0], i, 0});
}

for (int i = 0; i < k - 1; i++) {
int[] cur = pq.poll();

if (cur[2] != n - 1) {
pq.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
}
}

return pq.poll()[0];
}

Analysis

  • Time Complexity: \(O(klogn)\)
  • Space Complexity: \(O(n)\)

Binary Search

image
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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) / 2;

if (check(matrix, mid, k, n)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

private static boolean check(int[][] matrix, int target, int k, int n) {
int i = n - 1;
int j = 0;
int num = 0;

while (i >= 0 && j < n) {
if (matrix[i][j] <= target) {
num += i + 1;
j++;
} else {
i--;
}
}

return num >= k;
}

Analysis

  • Time Complexity: \(O(nlog(r-l)\)
  • Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗