Replace diagonal elements in each row of given Matrix by Kth smallest element of that row

0 0 5 minutes read

Given a matrix mat[ ][ ] of size N*N and an integer K, containing integer values, the task is to replace diagonal elements by the Kth smallest element of row.

Examples:

Input: mat[][]= {{1, 2, 3, 4}
{4, 2, 7, 6}
{3, 5, 1, 9}
{2, 4, 6, 8}}
K = 2
Output: 2, 2, 3, 4
4, 4, 7, 6
3, 5, 3, 8
2, 4, 6, 4
Explanation: 2nd smallest element of 1st row = 2
2nd smallest element of 2nd row is 4
2nd smallest element of 3rd row is 3
2nd smallest element of 4th row is 4

Input: mat[][] = {{1, 2, 3}
{7, 9, 8}
{2, 3, 6}}
K = 2
Output: 2, 2, 3
7, 8, 8
2, 3, 3

Approach: The solution is based on the concept of sorting. Follow the steps mentioned below:

Traverse the matrix row-wise.
Copy this row in another list.
Sort the list and get the Kth smallest element and replace the diagonal element with that.

Below is the implementation of the above approach.

C++

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int N = 4;
 
// Function to print Matrix
void showMatrix(int mat[][N])
{
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Function to return k'th smallest element
// in a given array
int kthSmallest(int arr[], int n, int K)
{
    // Sort the given array
    sort(arr, arr + n);
 
    // Return k'th element
    // in the sorted array
    return arr[K - 1];
}
 
// Function to replace diagonal elements
// with Kth min element of row.
void ReplaceDiagonal(int mat[][N], int K)
{
    int i, j;
    int arr[N];
 
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            arr[j] = mat[i][j];
        mat[i][i] = kthSmallest(arr, N, K);
    }
    showMatrix(mat);
}
 
// Utility Main function.
int main()
{
    int mat[][N] = { { 1, 2, 3, 4 },
                     { 4, 2, 7, 6 },
                     { 3, 5, 1, 9 },
                     { 2, 4, 6, 8 } };
 
    int K = 3;
    ReplaceDiagonal(mat, K);
    return 0;
}

Java

// Java code to find the maximum median
// of a sub array having length at least K.
import java.util.*;
public class GFG
{
 
  static int N = 4;
 
  // Function to print Matrix
  static void showMatrix(int mat[][])
  {
    int i, j;
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        System.out.print(mat[i][j] + " ");
      }
      System.out.println();
    }
  }
 
  // Function to return k'th smallest element
  // in a given array
  static int kthSmallest(int arr[], int n, int K)
  {
    // Sort the given array
    Arrays.sort(arr);
 
    // Return k'th element
    // in the sorted array
    return arr[K - 1];
  }
 
  // Function to replace diagonal elements
  // with Kth min element of row.
  static void ReplaceDiagonal(int mat[][], int K)
  {
    int i, j;
    int arr[] = new int[N];
 
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++)
        arr[j] = mat[i][j];
      mat[i][i] = kthSmallest(arr, N, K);
    }
    showMatrix(mat);
  }
 
  // Driver code
  public static void main(String args[])
  {
    int mat[][] = { { 1, 2, 3, 4 },
                   { 4, 2, 7, 6 },
                   { 3, 5, 1, 9 },
                   { 2, 4, 6, 8 } };
 
    int K = 3;
    ReplaceDiagonal(mat, K);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code for the above approach
N = 4
 
# Function to print Matrix
def showMatrix(mat):
    i = None
    j = None
    for i in range(N):
        for j in range(N):
            print(mat[i][j], end= " ")
        print('')
     
# Function to return k'th smallest element
# in a given array
def kthSmallest(arr, n, K):
 
    # Sort the given array
    arr.sort()
 
    # Return k'th element
    # in the sorted array
    return arr[K - 1]
 
# Function to replace diagonal elements
# with Kth min element of row.
def ReplaceDiagonal(mat, K):
    i = None
    j = None
    arr = [0] * N
 
    for i in range(N):
        for j in range(N):
            arr[j] = mat[i][j]
        mat[i][i] = kthSmallest(arr, N, K)
    showMatrix(mat)
 
# Utility Main function.
mat = [[1, 2, 3, 4], [4, 2, 7, 6], [3, 5, 1, 9], [2, 4, 6, 8]]
 
K = 3
ReplaceDiagonal(mat, K)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code to find the maximum median
// of a sub array having length at least K.
using System;
 
public class GFG {
 
  static int N = 4;
 
  // Function to print Matrix
  static void showMatrix(int[, ] mat)
  {
    int i, j;
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        Console.Write(mat[i, j] + " ");
      }
      Console.WriteLine();
    }
  }
 
  // Function to return k'th smallest element
  // in a given array
  static int kthSmallest(int[] arr, int n, int K)
  {
    // Sort the given array
    Array.Sort(arr);
 
    // Return k'th element
    // in the sorted array
    return arr[K - 1];
  }
 
  // Function to replace diagonal elements
  // with Kth min element of row.
  static void ReplaceDiagonal(int[, ] mat, int K)
  {
    int i, j;
    int[] arr = new int[N];
 
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++)
        arr[j] = mat[i, j];
      mat[i, i] = kthSmallest(arr, N, K);
    }
    showMatrix(mat);
  }
 
  // Driver code
  public static void Main()
  {
    int[, ] mat = { { 1, 2, 3, 4 },
                   { 4, 2, 7, 6 },
                   { 3, 5, 1, 9 },
                   { 2, 4, 6, 8 } };
 
    int K = 3;
    ReplaceDiagonal(mat, K);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
       // JavaScript code for the above approach 
       let N = 4;
 
       // Function to print Matrix
       function showMatrix(mat) {
           let i, j;
           for (i = 0; i < N; i++) {
               for (j = 0; j < N; j++) {
                   document.write(mat[i][j] + " ");
               }
               document.write('<br>')
           }
       }
 
       // Function to return k'th smallest element
       // in a given array
       function kthSmallest(arr, n, K)
       {
        
           // Sort the given array
           arr.sort(function (a, b) { return a - b })
 
           // Return k'th element
           // in the sorted array
           return arr[K - 1];
       }
 
       // Function to replace diagonal elements
       // with Kth min element of row.
       function ReplaceDiagonal(mat, K) 
       {
           let i, j;
           let arr = new Array(N);
 
           for (i = 0; i < N; i++) {
               for (j = 0; j < N; j++)
                   arr[j] = mat[i][j];
               mat[i][i] = kthSmallest(arr, N, K);
           }
           showMatrix(mat);
       }
 
       // Utility Main function.
       let mat = [[1, 2, 3, 4],
       [4, 2, 7, 6],
       [3, 5, 1, 9],
       [2, 4, 6, 8]];
 
       let K = 3;
       ReplaceDiagonal(mat, K);
 
 // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N² * logN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!