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 4Input: 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 Matrixvoid 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 arrayint 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 approachN = 4# Function to print Matrixdef 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 arraydef 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 = 3ReplaceDiagonal(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
3 2 3 4 4 6 7 6 3 5 5 9 2 4 6 6
Time Complexity: O(N2 * logN)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
