Kth Smallest Element of a Matrix of given dimensions filled with product of indices

0 0 9 minutes read

Given an integer K and a matrix of size N x M, where each matrix element is equal to the product of its indices(i * j), the task is to find the K^th Smallest element in the given Matrix.
Examples:

Input: N = 2, M = 3, K = 5
Output: 4
Explanation:
The matrix possible for given dimensions is {{1, 2, 3}, {2, 4, 6}}
Sorted order of the matrix elements: {1, 2, 2, 3, 4, 6}
Therefore, the 5^th smallest element is 4.
Input: N = 1, M = 10, K = 8
Output: 8
Explanation:
The matrix possible for given dimensions is {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}
Therefore, the 8^th smallest element is 8.

Naive Approach: The simplest approach is to store all the elements of the matrix in an array and then find the K^th smallest element by sorting the array.

Below is the implementation of the approach:

C++

// C++ code for the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find Kth smallest element in matrix
int kthSmallest(vector<vector<int>> &mat, int n, int m, int k) {
    // Create a temporary array
    int arr[n * m];
 
    // Fill the temporary array
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            arr[index++] = mat[i][j];
        }
    }
 
    // Sort the temporary array
    sort(arr, arr + n * m);
 
    // Return Kth smallest element
    return arr[k - 1];
}
 
// Driver code
int main() {
    // Given matrix
    int n = 2, m = 3, k = 5;
    vector<vector<int>> mat(n, vector<int>(m,0));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mat[i][j] = (i + 1) * (j + 1);
        }
    }
 
    // Function call
    cout << kthSmallest(mat, n, m, k) << endl;
 
    return 0;
}

Java

// Java code for the approach
 
import java.util.*;
 
class GFG {
    // Function to find Kth smallest element in matrix
    public static int kthSmallest(int[][] mat, int n, int m,
                                  int k)
    {
        // Create a temporary array
        int[] arr = new int[n * m];
        // Fill the temporary array
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[index++] = mat[i][j];
            }
        }
 
        // Sort the temporary array
        Arrays.sort(arr);
 
        // Return Kth smallest element
        return arr[k - 1];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given matrix
        int n = 2, m = 3, k = 5;
        int[][] mat = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mat[i][j] = (i + 1) * (j + 1);
            }
        }
 
        // Function call
        System.out.println(kthSmallest(mat, n, m, k));
    }
}

Python

def GFG(mat, n, m, k):
    arr = []
    # Fill temporary array
    for i in range(n):
        for j in range(m):
            arr.append(mat[i][j])
    arr.sort()
    # Return Kth smallest element
    return arr[k - 1]
# Driver code
if __name__ == "__main__":
    n = 2
    m = 3
    k = 5
    mat = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            mat[i][j] = (i + 1) * (j + 1)
    # Function call
    print(GFG(mat, n, m, k))

C#

using System;
using System.Linq;
 
class Program {
    // Function to find Kth smallest element in matrix
    static int kthSmallest(int[][] mat, int n, int m, int k)
    {
        // Create a temporary array
        int[] arr = new int[n * m];
        // Fill the temporary array
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[index++] = mat[i][j];
            }
        }
 
        // Sort the temporary array
        Array.Sort(arr);
 
        // Return Kth smallest element
        return arr[k - 1];
    }
 
    static void Main(string[] args)
    {
        // Given matrix
        int n = 2, m = 3, k = 5;
        int[][] mat = new int[n][];
        for (int i = 0; i < n; i++) {
            mat[i] = new int[m];
            for (int j = 0; j < m; j++) {
                mat[i][j] = (i + 1) * (j + 1);
            }
        }
 
        // Function call
        Console.WriteLine(kthSmallest(mat, n, m, k));
    }
}
// This code is contributed by user_dtewbxkn77n

Javascript

// Javascript code addition 
 
function kthSmallest(mat, n, m, k) {
  // Create a temporary array
  let arr = new Array(n * m);
  // Fill the temporary array
  let index = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      arr[index++] = mat[i][j];
    }
  }
 
  // Sort the temporary array
  arr.sort((a, b) => a - b);
 
  // Return Kth smallest element
  return arr[k - 1];
}
 
// Driver code
let n = 2, m = 3, k = 5;
let mat = [];
for (let i = 0; i < n; i++) {
  mat.push(new Array(m));
  for (let j = 0; j < m; j++) {
    mat[i][j] = (i + 1) * (j + 1);
  }
}
 
// Function call
console.log(kthSmallest(mat, n, m, k));
// The code is contributed by Nidhi goel.

Output

Time Complexity: O(N×M×log(N×M))
Auxiliary Space: O(N×M)

Efficient Approach:
To optimize the naive approach the idea is to use the Binary Search algorithm. Follow the steps below to solve the problem:

Initialize low as 1 and high as N×M, as the K^th smallest element lies between 1 and N×M.
Find the mid element between the low and high elements.
If the number of elements less than mid is greater than or equal to K, then update high to mid-1 as the Kth smallest element lies between low and mid.
If the number of elements less than mid is less than K, then update low to mid+1 as the Kth smallest element lies between mid and high.
As the elements in the ith row are the multiple of i, the number of elements less than mid in the ith row can be calculated easily by min(mid/i, M). So, the time complexity to find the number of elements less than mid can be done in only O(N).
Perform binary search till low is less than or equal to high and return high + 1 as the Kth smallest element of the matrix N×M.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
 
#define LL long long 
 
// Function that returns true if the 
// count of elements is less than mid 
bool countLessThanMid(LL mid, LL N, 
                    LL M, LL K) 
{ 
    // To store count of elements 
    // less than mid 
    LL count = 0; 
 
    // Loop through each row 
    for (int i = 1; 
        i <= min((LL)N, mid); ++i) { 
 
        // Count elements less than 
        // mid in the ith row 
        count = count + min(mid / i, M); 
    } 
 
    if (count >= K) 
        return false; 
    else
        return true; 
} 
 
// Function that returns the Kth 
// smallest element in the NxM 
// Matrix after sorting in an array 
LL findKthElement(LL N, LL M, LL K) 
{ 
    // Initialize low and high 
    LL low = 1, high = N * M; 
 
    // Perform binary search 
    while (low <= high) { 
 
        // Find the mid 
        LL mid = low + (high - low) / 2; 
 
        // Check if the count of 
        // elements is less than mid 
        if (countLessThanMid(mid, N, M, K)) 
            low = mid + 1; 
        else
            high = mid - 1; 
    } 
 
    // Return Kth smallest element 
    // of the matrix 
    return high + 1; 
} 
 
// Driver Code 
int main() 
{ 
    LL N = 2, M = 3; 
 
    LL int K = 5; 
 
    cout << findKthElement(N, M, K) << endl; 
 
    return 0; 
} 

Java

// Java program to implement 
// the above approach 
class GFG{
     
// Function that returns true if the 
// count of elements is less than mid 
public static boolean countLessThanMid(int mid, int N, 
                                       int M, int K) 
{ 
     
    // To store count of elements 
    // less than mid 
    int count = 0; 
 
    // Loop through each row 
    for(int i = 1; 
            i <= Math.min(N, mid); ++i) 
    { 
         
        // Count elements less than 
        // mid in the ith row 
        count = count + Math.min(mid / i, M); 
    } 
 
    if (count >= K) 
        return false; 
    else
        return true; 
} 
 
// Function that returns the Kth 
// smallest element in the NxM 
// Matrix after sorting in an array 
public static int findKthElement(int N, int M, int K) 
{ 
     
    // Initialize low and high 
    int low = 1, high = N * M; 
 
    // Perform binary search 
    while (low <= high) 
    { 
         
        // Find the mid 
        int mid = low + (high - low) / 2; 
 
        // Check if the count of 
        // elements is less than mid 
        if (countLessThanMid(mid, N, M, K)) 
            low = mid + 1; 
        else
            high = mid - 1; 
    } 
 
    // Return Kth smallest element 
    // of the matrix 
    return high + 1; 
} 
 
// Driver code
public static void main(String[] args) 
{
    int N = 2, M = 3; 
    int K = 5; 
 
    System.out.println(findKthElement(N, M, K));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for the above approach 
# Function that returns true if the 
# count of elements is less than mid 
def countLessThanMid(mid, N, M, K):
     
    # To store count of elements 
    # less than mid 
    count = 0
 
    # Loop through each row 
    for i in range (1, min(N, mid) + 1):
 
        # Count elements less than 
        # mid in the ith row 
        count = count + min(mid // i, M)
     
    if (count >= K):
        return False
    else:
        return True
 
# Function that returns the Kth 
# smallest element in the NxM 
# Matrix after sorting in an array 
def findKthElement(N, M, K):
 
    # Initialize low and high 
    low = 1
    high = N * M
 
    # Perform binary search 
    while (low <= high):
 
        # Find the mid 
        mid = low + (high - low) // 2
 
        # Check if the count of 
        # elements is less than mid 
        if (countLessThanMid(mid, N, M, K)):
            low = mid + 1
        else:
            high = mid - 1
 
    # Return Kth smallest element 
    # of the matrix 
    return high + 1
 
# Driver Code 
if __name__ == "__main__":  
    N = 2
    M = 3
    K = 5
    print(findKthElement(N, M, K))
     
# This code is contributed by Chitranayal

C#

// C# program to implement 
// the above approach 
using System;
 
class GFG{
     
// Function that returns true if the 
// count of elements is less than mid 
public static bool countLessThanMid(int mid, int N, 
                                    int M, int K) 
{ 
     
    // To store count of elements 
    // less than mid 
    int count = 0; 
 
    // Loop through each row 
    for(int i = 1; 
            i <= Math.Min(N, mid); ++i) 
    { 
         
        // Count elements less than 
        // mid in the ith row 
        count = count + Math.Min(mid / i, M); 
    } 
 
    if (count >= K) 
        return false; 
    else
        return true; 
} 
 
// Function that returns the Kth 
// smallest element in the NxM 
// Matrix after sorting in an array 
public static int findKthElement(int N, int M,
                                        int K) 
{ 
     
    // Initialize low and high 
    int low = 1, high = N * M; 
 
    // Perform binary search 
    while (low <= high) 
    { 
         
        // Find the mid 
        int mid = low + (high - low) / 2; 
 
        // Check if the count of 
        // elements is less than mid 
        if (countLessThanMid(mid, N, M, K)) 
            low = mid + 1; 
        else
            high = mid - 1; 
    } 
 
    // Return Kth smallest element 
    // of the matrix 
    return high + 1; 
} 
 
// Driver code
public static void Main(String[] args) 
{
    int N = 2, M = 3; 
    int K = 5; 
 
    Console.WriteLine(findKthElement(N, M, K));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program for the above approach 
 
// Function that returns true if the 
// count of elements is less than mid 
function countLessThanMid(mid, N, M, K) 
{ 
    // To store count of elements 
    // less than mid 
    let count = 0; 
 
    // Loop through each row 
    for (let i = 1; 
        i <= Math.min(N, mid); ++i) { 
 
        // Count elements less than 
        // mid in the ith row 
        count = count + Math.min(parseInt(mid / i), M); 
    } 
 
    if (count >= K) 
        return false; 
    else
        return true; 
} 
 
// Function that returns the Kth 
// smallest element in the NxM 
// Matrix after sorting in an array 
function findKthElement(N, M, K) 
{ 
    // Initialize low and high 
    let low = 1, high = N * M; 
 
    // Perform binary search 
    while (low <= high) { 
 
        // Find the mid 
        let mid = low + parseInt((high - low) / 2); 
 
        // Check if the count of 
        // elements is less than mid 
        if (countLessThanMid(mid, N, M, K)) 
            low = mid + 1; 
        else
            high = mid - 1; 
    } 
 
    // Return Kth smallest element 
    // of the matrix 
    return high + 1; 
} 
 
// Driver Code
    let N = 2, M = 3; 
 
    let K = 5; 
 
    document.write(findKthElement(N, M, K)); 
 
</script>

Output:

Time Complexity: O(N×log(N×M))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!