Given a 2D vector mat[][] of integers. The task is to sort the elements of the vectors diagonally from top-left to bottom-right in increasing order.
Examples:
Input: mat[][] =
{{9, 4, 2},
{7, 4, 6},
{2, 3, 3}}
Output:
3 4 2
3 4 6
2 7 9
Explanation:
There are 5 diagonals in this matrix:
1. {2} - No need to sort
2. {7, 3} - Sort - {3, 7}
3. {9, 4, 3} - Sort - {3, 4, 9}
4. {4, 6} - Already sorted
5. {2} - No need to sort
Input: mat[][] =
{{ 4, 3, 2, 1 },
{ 3, 2, 1, 0 },
{ 2, 1, 1, 0 },
{ 0, 1, 2, 3 }}
Output:
1 0 0 1
1 2 1 2
1 2 3 3
0 2 3 4
Approach:
- All elements in the same diagonal have the same index difference i – j where i is the row number and j is the column number. So we can use a map to store every diagonal at index i – j.
- Now we can sort every index of the map using the inbuilt function.
- Now in the original matrix, we can insert every diagonal of a matrix stored in map.
- Finally, we can print the Matrix.
Below is the implementation of the above approach:
CPP
// C++ implementation to sort the// diagonals of the matrix#include <bits/stdc++.h>using namespace std;// Function to sort the// diagonal of the matrixvoid SortDiagonal(int mat[4][4], int m, int n){ // Map to store every diagonal // in different indices here // elements of same diagonal // will be stored in same index unordered_map<int, vector<int> > mp; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // Storing diagonal elements // in map mp[i - j].push_back(mat[i][j]); } } // To sort each diagonal in // ascending order for (int k = -(n - 1); k < m; k++) { sort(mp[k].begin(), mp[k].end()); } // Loop to store every diagonal // in ascending order for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { mat[i][j] = mp[i - j].back(); mp[i - j].pop_back(); } } // Loop to print the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) cout << mat[i][j] << " "; cout << endl; }}// Driven Codeint main(){ int arr[4][4] = { { 4, 3, 2, 1 }, { 3, 2, 1, 0 }, { 2, 1, 1, 0 }, { 0, 1, 2, 3 } }; // Sort the Diagonals SortDiagonal(arr, 4, 4); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { // Function to sort the // diagonal of the matrix static void SortDiagonal(int mat[][], int m, int n) { // Map to store every diagonal // in different indices here // elements of same diagonal // will be stored in same index HashMap<Integer, List<Integer>> mp = new HashMap<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // Storing diagonal elements // in map if(mp.containsKey(i-j)){ mp.get(i-j).add(mat[i][j]); }else{ List<Integer> ll = new ArrayList<>(); ll.add(mat[i][j]); mp.put(i-j,ll); } } } // To sort each diagonal in // ascending order for(int k = -(n - 1); k < m; k++) { Collections.sort(mp.get(k)); } // Loop to store every diagonal // in ascending order for(int i = m - 1; i >= 0; i--) { for(int j = n - 1; j >= 0; j--) { mat[i][j] = mp.get(i-j).get(mp.get(i-j).size()-1); mp.get(i-j).remove(mp.get(i-j).size()-1); } } // Loop to print the matrix for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) System.out.print(mat[i][j]+" "); System.out.println(); } } public static void main (String[] args) { int arr[][] = { { 4, 3, 2, 1 }, { 3, 2, 1, 0 }, { 2, 1, 1, 0 }, { 0, 1, 2, 3 } }; // Sort the Diagonals SortDiagonal(arr, 4, 4); }}// This code is contributed by aadityaburujwale. |
Python3
# Python3 implementation to sort the# diagonals of the matrix# Function to sort the# diagonal of the matrixdef SortDiagonal(mat, m, n): # Map to store every diagonal # in different indices here # elements of same diagonal # will be stored in same index mp = {} for z in range(-5,5): mp[z] = [] for i in range(0,m): for j in range(0,n): # Storing diagonal elements # in map mp[i - j].append(mat[i][j]) # To sort each diagonal in # ascending order for k in range(-1*(n-1),m): mp[k].sort() # Loop to store every diagonal # in ascending order for i in range(m-1,-1,-1): for j in range(n-1,-1,-1): mat[i][j] = mp[i - j][len(mp[i-j])-1] mp[i - j].pop(len(mp[i-j])-1) # Loop to print the matrix for i in range(0,m): for j in range(0,n): print(mat[i][j],end=" ") print("")# Driven Codearr= [ [ 4, 3, 2, 1 ], [ 3, 2, 1, 0 ], [ 2, 1, 1, 0 ], [ 0, 1, 2, 3 ] ]# Sort the DiagonalsSortDiagonal(arr, 4, 4)# This code is contributed by akashish__ |
C#
using System;using System.Collections.Generic;public class GFG { // Function to sort the // diagonal of the matrix public static void SortDiagonal(int[, ] mat, int m, int n) { // Map to store every diagonal // in different indices here // elements of same diagonal // will be stored in same index Dictionary<int, List<int> > mp = new Dictionary<int, List<int> >(); for (int i = -100; i < 100; i++) { mp.Add(i, new List<int>()); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // Storing diagonal elements // in map mp[i - j].Add(mat[i, j]); } } // To sort each diagonal in // ascending order for (int k = -1 * (n - 1); k < m; k++) { mp[k].Sort(); } // Loop to store every diagonal // in ascending order for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { mat[i, j] = mp[i - j][mp[i - j].Count - 1]; mp[i - j].RemoveAt(mp[i - j].Count - 1); } } // Loop to print the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) Console.Write(mat[i, j] + " "); Console.WriteLine(""); } } static public void Main() { int[, ] arr = { { 4, 3, 2, 1 }, { 3, 2, 1, 0 }, { 2, 1, 1, 0 }, { 0, 1, 2, 3 } }; // Sort the Diagonals SortDiagonal(arr, 4, 4); }}// This code is contributed by akashish__ |
Javascript
<script>// Javascript implementation of the above approach// Function to sort the// diagonal of the matrixfunction SortDiagonal(mat, m, n){ // Map to store every diagonal // in different indices here // elements of same diagonal // will be stored in same index var mp = {}; for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { mp[i - j] = []; } } for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { // Storing diagonal elements // in map mp[i - j].push(mat[i][j]); } } // To sort each diagonal in // ascending order for (var k = -(n - 1); k < m; k++) { mp[k].sort(); } // Loop to store every diagonal // in ascending order for (var i = m - 1; i >= 0; i--) { for (var j = n - 1; j >= 0; j--) { mat[i][j] = mp[i - j].pop(); } } // Loop to print the matrix for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) document.write(mat[i][j] + " " ); document.write("<br>"); }}// Driver Codevar arr = [[ 4, 3, 2, 1 ], [ 3, 2, 1, 0 ], [ 2, 1, 1, 0 ], [ 0, 1, 2, 3 ]];// Sort the DiagonalsSortDiagonal(arr, 4, 4);</script> |
Output:
1 0 0 1 1 2 1 2 1 2 3 3 0 2 3 4
Time complexity : O(mnlog(mn)), where m is the number of rows and n is the number of columns of the matrix
Space complexity : O(m*n) as it uses an unordered_map container to store each diagonal of the matrix.
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!
