Sort a 2D vector diagonally using Map Data Structure

0 0 6 minutes read

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.

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!