Kth element in Matrix in Java
In a row-wise and column-wise sorted 2D array, each row and column is arranged in ascending order, presenting a unique challenge for finding the Kth smallest element efficiently. The problem at hand is to develop an algorithm that can determine the Kth smallest element within this structured matrix. The task requires navigating through the matrix while considering both row and column arrangements, aiming to minimize computational complexity and efficiently locate the desired element.
Examples:
Example 1:
Input:
Matrix:
![Kth element in Matrix in Java/>
<!-- /wp:html -->
<!-- wp:preformatted -->
<pre class=](https://static.tutorialandexample.com/java/kth-element-in-matrix-in-java1.png)
Output:
The Kth smallest element in the matrix is: 13
Explanation:
In the given matrix, the 8th smallest element is 13. By counting the number of elements less than or equal to each candidate element using the counting method described in the problem, we find that there are exactly 8 elements less than or equal to 13, making it the 8th smallest element in the matrix.
Example 2:
Input:
Matrix:
![Kth element in Matrix in Java/>
<!-- /wp:html -->
<!-- wp:preformatted -->
<pre class=](https://static.tutorialandexample.com/java/kth-element-in-matrix-in-java2.png)
Output:
The Kth smallest element in the matrix is: 7
Explanation:
For the given matrix and K value, the 4th smallest element is 7. By applying the same counting technique, we find that there are 4 elements less than or equal to 7 in the matrix, thus making it the 4th smallest element.
Approach 1: Using iterative approach
ALGORITHM:
Step 1: Initialize low as the smallest element in the matrix and high as the largest element.
Step 2: While low is less than high, calculate mid as the average of low and high.
Step 3: Count the number of elements less than or equal to mid in the matrix.
Step 4: If the count is less than k, update low to mid + 1, discarding elements less than mid.
Step 5: If the count is greater than or equal to k, update high to mid, including mid as a possible candidate.
Step 6: Return low as the kth smallest element.
Implementation:
The implementation of the above steps given below.
FileName: KthElementInMatrix.java
import java.util.*; public class KthElementInMatrix { // Function to count the number of elements less than or equal to mid in the matrix static int countLessThanOrEqualToMid(int[][] matrix, int mid) { int count = 0; int n = matrix.length; int row = n - 1; // Start from the last row int col = 0; // Start from the first column // Traverse the matrix while (row >= 0 && col < n) { if (matrix[row][col] <= mid) { // If current element is less than or equal to mid, // increment count by the number of elements in the current column (row + 1) count += (row + 1); col++; // Move to the next column } else { row--; // Move to the previous row } } return count; } // Function to find the kth smallest element in the matrix static int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int low = matrix[0][0]; // Smallest element in the matrix int high = matrix[n - 1][n - 1]; // Largest element in the matrix // Perform binary search on the range [low, high] while (low < high) { int mid = low + (high - low) / 2; // Calculate mid value int count = countLessThanOrEqualToMid(matrix, mid); // Count elements less than or equal to mid // Adjust low or high based on the count if (count < k) { low = mid + 1; // Discard elements less than mid } else { high = mid; // Include mid as a possible candidate } } return low; // Return the kth smallest element } public static void main(String[] args) { // Example 1 int[][] matrix1 = { {1, 5, 9}, {10, 11, 13}, {12, 13, 15} }; int k1 = 8; System.out.println("Example 1:"); System.out.println("Matrix:"); for (int[] row : matrix1) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k1); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix1, k1)); System.out.println(); // Example 2 int[][] matrix2 = { {1, 3, 5}, {7, 9, 11}, {13, 15, 17} }; int k2 = 4; System.out.println("Example 2:"); System.out.println("Matrix:"); for (int[] row : matrix2) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k2); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix2, k2)); } }
Output:
Example 1: Matrix: [1, 5, 9] [10, 11, 13] [12, 13, 15] K = 8 The Kth smallest element in the matrix is: 13 Example 2: Matrix: [1, 3, 5] [7, 9, 11] [13, 15, 17] K = 4 The Kth smallest element in the matrix is: 7
Complexity Analysis:
Time Complexity:
Time complexity refers to how the runtime of an algorithm increases with the size of the input. In this algorithm, we use binary search to find the kth smallest element in the matrix. The time complexity of binary search is O(log n), where n is the range of possible values (difference between the largest and smallest elements in the matrix). Therefore, the overall time complexity of this algorithm is O(log n), where n is the range of values in the matrix.
Space Complexity:
Space complexity refers to how much memory an algorithm uses relative to the size of the input. The algorithm doesn't use any extra space that grows with the size of the input. It only uses a few variables to keep track of indices and counts. Therefore, the space complexity of this algorithm is O(1), which means it uses constant space regardless of the size of the input matrix.
Approach 2: Using Recursion
ALGORITHM:
Step 1: Start by setting up variables for the lowest and highest possible values in the matrix.
Step 2: Use binary search to find the mid-point between the lowest and highest values.
Step 3: Count the number of elements in the matrix that are less than or equal to the mid-point.
Step 4: Recursively search either the upper or lower half of the matrix based on the count.
Step 5: If the lowest and highest values converge, return the lowest value as the kth smallest element.
Step 6: After recursion, return the kth smallest element found.
Implementation:
The implementation of the above steps given below
FileName: KthElementInMatrix.java
import java.util.*; public class KthElementInMatrix { // Function to count the number of elements less than or equal to mid in the matrix static int countLessThanOrEqualToMid(int[][] matrix, int mid) { int count = 0; int n = matrix.length; int row = n - 1; // Start from the last row int col = 0; // Start from the first column // Traverse the matrix while (row >= 0 && col < n) { if (matrix[row][col] <= mid) { // If current element is less than or equal to mid, // increment count by the number of elements in the current column (row + 1) count += (row + 1); col++; // Move to the next column } else { row--; // Move to the previous row } } return count; } // Recursive function to find the kth smallest element in the matrix static int kthSmallestRecursive(int[][] matrix, int k, int low, int high) { // Calculate mid value int mid = low + (high - low) / 2; // Count elements less than or equal to mid int count = countLessThanOrEqualToMid(matrix, mid); // Base case: low and high converge if (low == high) { return low; // Return the kth smallest element } // Recursively search in the lower or upper half based on the count if (count < k) { return kthSmallestRecursive(matrix, k, mid + 1, high); // Search in the upper half } else { return kthSmallestRecursive(matrix, k, low, mid); // Search in the lower half } } // Function to find the kth smallest element in the matrix static int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int low = matrix[0][0]; // Smallest element in the matrix int high = matrix[n - 1][n - 1]; // Largest element in the matrix // Call the recursive function to find the kth smallest element return kthSmallestRecursive(matrix, k, low, high); } public static void main(String[] args) { // Example 1 int[][] matrix1 = { {1, 5, 9}, {10, 11, 13}, {12, 13, 15} }; int k1 = 8; System.out.println("Example 1:"); System.out.println("Matrix:"); for (int[] row : matrix1) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k1); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix1, k1)); System.out.println(); // Example 2 int[][] matrix2 = { {1, 3, 5}, {7, 9, 11}, {13, 15, 17} }; int k2 = 4; System.out.println("Example 2:"); System.out.println("Matrix:"); for (int[] row : matrix2) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k2); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix2, k2)); } }
Output:
Example 1: Matrix: [1, 5, 9] [10, 11, 13] [12, 13, 15] K = 8 The Kth smallest element in the matrix is: 13 Example 2: Matrix: [1, 3, 5] [7, 9, 11] [13, 15, 17] K = 4 The Kth smallest element in the matrix is: 7
Complexity Analysis:
Time Complexity:
Time complexity tells us how long an algorithm takes to run. In this algorithm, we use binary search to find the kth smallest element. Binary search has a time complexity of O(log n), where n is the range of values in the matrix. So, the overall time complexity of this algorithm is O(log n).
Space Complexity:
Space complexity tells us how much memory an algorithm uses. The algorithm doesn't use additional memory that grows with the size of the input. It only uses a few variables to keep track of indices and counts, so the space complexity is O(1), which means it uses constant space.
Approach 3: Using Priority Queue (Min-heap)
ALGORITHM:
Step 1: Start by creating a min heap using a priority queue.
Step 2: Add the first element of each row to the min heap along with their row and column indices.
Step 3: Extract the smallest element from the heap K times.
Step 4: Update the result with the value of the smallest element extracted each time.
Step 5: For each element extracted, check if there's a next element in the same row and add it to the heap if present.
Step 6: After extracting Kth smallest element, return the result.
Implementation:
The implementation of the above steps given below.
FileName: KthElementInMatrix.java
import java.util.*;
public class KthElementInMatrix {
// Function to find the kth smallest element in the matrix using min heap
static int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
// Create a min heap using a priority queue
PriorityQueue
// Adding the first element of each row to the min heap
for (int i = 0; i < n; i++) {
minHeap.offer(new int[]{matrix[i][0], i, 0});
}
// Extracting the Kth smallest element by removing and adding elements from the heap
int result = 0;
for (int i = 0; i < k; i++) {
int[] min = minHeap.poll(); // Remove the smallest element from the heap
result = min[0]; // Update the result with the smallest element
int row = min[1]; // Get the row index of the smallest element
int col = min[2] + 1; // Get the column index of the next element in the row
if (col < n) {
// If there are more elements in the current row, add the next element to the heap
minHeap.offer(new int[]{matrix[row][col], row, col});
}
}
return result; // Return the Kth smallest element
}
public static void main(String[] args) {
// Example 1
int[][] matrix1 = {
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
int k1 = 8;
System.out.println("Example 1:");
System.out.println("Matrix:");
for (int[] row : matrix1) {
System.out.println(Arrays.toString(row));
}
System.out.println("K = " + k1);
System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix1, k1));
System.out.println();
// Example 2
int[][] matrix2 = {
{1, 3, 5},
{7, 9, 11},
{13, 15, 17}
};
int k2 = 4;
System.out.println("Example 2:");
System.out.println("Matrix:");
for (int[] row : matrix2) {
System.out.println(Arrays.toString(row));
}
System.out.println("K = " + k2);
System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix2, k2));
}
}
Output:
Example 1: Matrix: [1, 5, 9] [10, 11, 13] [12, 13, 15] K = 8 The Kth smallest element in the matrix is: 1 Example 2: Matrix: [1, 3, 5] [7, 9, 11] [13, 15, 17] K = 4 The Kth smallest element in the matrix is: 7
Complexity Analysis:
Time Complexity:
Time complexity refers to how long an algorithm takes to run. In this algorithm, we use a min heap to find the kth smallest element. Adding an element to a heap takes O(log n) time, and we do this for each element in the first column of the matrix, which has 'n' elements. Extracting the smallest element from the heap also takes O(log n) time, and we do this 'k' times. Therefore, the overall time complexity is O(n log n + k log n).
Space Complexity:
Space complexity refers to how much memory an algorithm uses. In this algorithm, we use extra space to store the min heap. The size of the min heap can grow up to 'n' (the number of rows in the matrix). So, the space complexity is O(n) since it depends on the size of the input matrix.
Approach 4: Using Divide and Conquer
ALGORITHM:
Step 1: Initialize variables for the smallest and largest elements in the matrix.
Step 2: Implement a function to count the number of elements less than or equal to a given value (mid) in the matrix.
Step 3: Use binary search to find the kth smallest element between the smallest and largest elements in the matrix.
Step 4: In each iteration of the binary search:
Step 4.1: Calculate the mid value between the smallest and largest elements.
Step 4.2: Count the number of elements less than or equal to the mid value in the matrix.
Step 4.3: If the count is less than k, adjust the search range to the upper half; otherwise, adjust it to the lower half.
Step 5: Repeat the binary search until the smallest and largest elements converge.
Step 6: Return the kth smallest element found during the binary search.
Implementation:
FileName: KthElementInMatrix.java
import java.util.Arrays; public class KthElementInMatrix { // Function to count the number of elements less than or equal to mid in the matrix static int countLessThanOrEqualToMid(int[][] matrix, int mid) { int count = 0; int n = matrix.length; int row = n - 1; // Start from the last row int col = 0; // Start from the first column // Traverse the matrix while (row >= 0 && col < n) { if (matrix[row][col] <= mid) { // If current element is less than or equal to mid, // increment count by the number of elements in the current column (row + 1) count += (row + 1); col++; // Move to the next column } else { row--; // Move to the previous row } } return count; } // Recursive function to find the kth smallest element in the matrix static int kthSmallestRecursive(int[][] matrix, int k, int low, int high) { int n = matrix.length; int mid = low + (high - low) / 2; int count = countLessThanOrEqualToMid(matrix, mid); // Base case: low and high converge if (low == high) { return low; // Return the kth smallest element } // Recursively search in the lower or upper half based on the count if (count < k) { return kthSmallestRecursive(matrix, k, mid + 1, high); // Search in the upper half } else { return kthSmallestRecursive(matrix, k, low, mid); // Search in the lower half } } // Function to find the kth smallest element in the matrix static int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int low = matrix[0][0]; // Smallest element in the matrix int high = matrix[n - 1][n - 1]; // Largest element in the matrix // Call the recursive function to find the kth smallest element return kthSmallestRecursive(matrix, k, low, high); } public static void main(String[] args) { // Example 1 int[][] matrix1 = { {1, 5, 9}, {10, 11, 13}, {12, 13, 15} }; int k1 = 8; System.out.println("Example 1:"); System.out.println("Matrix:"); for (int[] row : matrix1) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k1); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix1, k1)); System.out.println(); // Example 2 int[][] matrix2 = { {1, 3, 5}, {7, 9, 11}, {13, 15, 17} }; int k2 = 4; System.out.println("Example 2:"); System.out.println("Matrix:"); for (int[] row : matrix2) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k2); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix2, k2)); } }
Output:
Example 1: Matrix: [1, 5, 9] [10, 11, 13] [12, 13, 15] K = 8 The Kth smallest element in the matrix is: 13 Example 2: Matrix: [1, 3, 5] [7, 9, 11] [13, 15, 17] K = 4 The Kth smallest element in the matrix is: 7
Complexity Analysis:
Time Complexity:
The time complexity of this algorithm is O(N log N), where N is the size of the matrix. It is because we perform binary search on a range of values, and for each iteration of binary search, we count the number of elements less than or equal to a given value, which takes O(N) time. Since we perform binary search, which divides the search space in half with each iteration, the overall time complexity is O(N log N).
Space Complexity:
The space complexity of both methods is O(1), as they use a constant amount of extra space for variables and temporary values, regardless of the size of the input matrix·
Approach 5: Using Merge Sort
ALGORITHM:
Step 1: To merge all elements into a single array: Iterate through the matrix to extract all elements and store them in a one-dimensional array. The array will contain all elements of the matrix in a linear fashion.
Step 2: Implement the merge sort algorithm to sort the merged array in ascending order. It will arrange all elements from smallest to largest.
Step 3: Once the array is sorted, return the kth element from the sorted array. The element represents the kth smallest element in the original matrix.
Step 4: Merge sort algorithm:
Step 4.1: Split the array into two halves recursively until each subarray contains only one element.
Step 4.2: Merge the sorted subarrays to produce a single sorted array.
Step 4.3: Create two temporary arrays to hold elements from the left and right subarrays.
Step 5: Compare elements from the left and right arrays and merge them into the original array in sorted order.
Implementation:
The implementation of the above steps given below
FileName: KthElementInMatrix.java
import java.util.Arrays; public class KthElementInMatrix { // Function to find the kth smallest element in the matrix static int kthSmallest(int[][] matrix, int k) { // Merge all elements into a single array int n = matrix.length; int[] merged = new int[n * n]; int index = 0; for (int[] row : matrix) { for (int element : row) { merged[index++] = element; } } // Sort the merged array using merge sort mergeSort(merged, 0, merged.length - 1); // Return the kth element return merged[k - 1]; } // Function to perform merge sort static void mergeSort(int[] arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } } // Function to merge two sorted subarrays static void merge(int[] arr, int low, int mid, int high) { int n1 = mid - low + 1; int n2 = high - mid; int[] left = new int[n1]; int[] right = new int[n2]; for (int i = 0; i < n1; ++i) { left[i] = arr[low + i]; } for (int j = 0; j < n2; ++j) { right[j] = arr[mid + 1 + j]; } int i = 0, j = 0; int k = low; while (i < n1 && j < n2) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } while (i < n1) { arr[k] = left[i]; i++; k++; } while (j < n2) { arr[k] = right[j]; j++; k++; } } public static void main(String[] args) { // Example 1 int[][] matrix1 = { {1, 5, 9}, {10, 11, 13}, {12, 13, 15} }; int k1 = 8; System.out.println("Example 1:"); System.out.println("Matrix:"); for (int[] row : matrix1) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k1); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix1, k1)); System.out.println(); // Example 2 int[][] matrix2 = { {1, 3, 5}, {7, 9, 11}, {13, 15, 17} }; int k2 = 4; System.out.println("Example 2:"); System.out.println("Matrix:"); for (int[] row : matrix2) { System.out.println(Arrays.toString(row)); } System.out.println("K = " + k2); System.out.println("The Kth smallest element in the matrix is: " + kthSmallest(matrix2, k2)); } }
Output:
Example 1: Matrix: [1, 5, 9] [10, 11, 13] [12, 13, 15] K = 8 The Kth smallest element in the matrix is: 13 Example 2: Matrix: [1, 3, 5] [7, 9, 11] [13, 15, 17] K = 4 The Kth smallest element in the matrix is: 7
Complexity Analysis:
Time Complexity:
The time complexity of the algorithm is O(n^2 log n), where n is the number of rows or columns in the matrix· The complexity arises from merging all elements into a single array and then sorting it using merge sort, which has a time complexity of O(n log n)·
Space Complexity:
The space complexity is O(n^2) as we are using an additional array to merge all elements from the matrix· The array has the same size as the matrix, resulting in quadratic space complexity·