Sort a 2D vector diagonally using Map Data Structure

Last Updated : 31 Jan, 2023

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 matrix
void 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 Code
int 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 matrix
def 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 Code
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__

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 matrix
function 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 Code
var arr = [[ 4, 3, 2, 1 ],
    [ 3, 2, 1, 0 ],
    [ 2, 1, 1, 0 ],
    [ 0, 1, 2, 3 ]];
 
// Sort the Diagonals
SortDiagonal(arr, 4, 4);
</script>

Output:

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.

spp____

Improve

Sort a 2D vector diagonally

Sort a 2D vector diagonally using Map Data Structure

CPP

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?