# Java solution

• sorry my code is really messy
what i did is to remove all cells that cant contain the kth smallest number and just sort the rest of the numbers

public class Solution {
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;

if (low >= high)
return;

int middle = low + (high - low) / 2;
int pivot = arr[middle];

int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}

while (arr[j] > pivot) {
j--;
}

if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}

if (low < j)
quickSort(arr, low, j);

if (high > i)
quickSort(arr, i, high);
}

public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
if (k == 1) {return matrix[0][0];}
if (k == n*n) {return matrix[n-1][n-1];}

int min_line = -1;
int max_line = -1;
for (int i = 1; i < 2*n; i++) {
if ((i > k)&&(i <= n)&&(min_line == -1)) min_line = i;
else if (((i-n+1)*n > k)&&(i > n)&&(min_line == -1)) min_line = i;
if (((i-1)*n+1 >= k)&&(i <= n)&&(max_line == -1)) max_line = i;
else if ((((n-1)*n+(i-n+1)) >= k)&&(i > n)&&(max_line == -1)) max_line = i;
}

int new_k = -1;
if (max_line-1 > n) {
new_k = n*(1+n)/2;
for (int i = n+1; i < max_line; i++) {
new_k += (i-2*(i-n));
}
new_k = k-new_k;
} else {
new_k = k-(max_line-1)*(1+max_line-1)/2;
}

int counter = 0;
for (int i = max_line; i < min_line; i++){
int temp = 0;
if (i <= n) {
temp = i;
counter += temp;
} else {
temp = i-2*(i-n);
counter += temp;
}
}

int[] A = new int[counter];
int p = 0;
for (int i = max_line; i < min_line; i++) {
int start_i = i;
if (i > n) start_i -= (i-n);
int start_j = 1;
if (i > n) start_j = (i-n+1);

int temp = 0;
if (i <= n) {
temp = i;
} else {
temp = i-2*(i-n);
}

for (int j = p; j < temp+p; j++) {
A[j] = matrix[start_i-1][start_j-1];
start_i--;
start_j++;
}
p+=temp;
}
quickSort(A,0,A.length-1);
return A[new_k-1];
}

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.