Question

Given a square matrix of integers m, your task is to rearrange its numbers in the following way:

• First, sort its values in ascending order of how frequently the number occurs in m. In the case of a tie, sort the equally frequent numbers by their values, in ascending order.
• Second, place the sorted numbers diagonally, starting from the bottom right corner, like this:

Example

For

m = [[ 1, 4, -2],
     [-2, 3,  4],
     [ 3, 1,  3]]

the output should be

sortMatrixByOccurrences(m) = [[3,  3,  4],
                              [3,  4,  1],
                              [1, -2, -2]]

• First we look at the frequency of each number:

  • Number 1 occurs 2 times;
  • Number -2 occurs 2 times;
  • Number 3 occurs 3 times;
  • Number 4 occurs 2 times.

  Because numbers 1, -2, and 4 occur the same number of times, we sort them by their values in ascending order. Number 3 occurs the most numbers of times, so it goes after all other numbers. Finally, after sorting we get the following array: [-2, -2, 1, 1, 4, 4, 3, 3, 3]

• After sorting, the numbers should be placed diagonally starting from the bottom right corner, as follows:

  [[3,  3,  4],
   [3,  4,  1],
   [1, -2, -2]]
  

Input/Output

• [execution time limit] 0.5 seconds (cpp)

• [input] array.array.integer m

  A square matrix of integers.

  Guaranteed constraints:
  1 ≤ m.length ≤ 40,
  m[i].length = m.length,
  -1000 ≤ m[i][j] ≤ 1000.

• [output] array.array.integer

  • The matrix m rearranged according to the specifications above.

code given:

std::vector> sortMatrixByOccurrences(std::vector> m) {

}

Answer 1

The following is the code for above question. It has met all the requirements stated in the question.

#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
//comparator which sorts based on frequency value in ascending order
bool cmp(pair<int, int>& a, 
         pair<int, int>& b) 
{ 
    return a.second < b.second; 
} 
vector<int> sort(map<int, int>& m) 
{ 
    // Declare vector of pairs 
    vector<pair<int, int> > a; 
 
    for (auto& it : m) { 
        a.push_back(it); //push each pair to vector
    } 
 
    sort(a.begin(), a.end(), cmp); //now sort based on comparator
  
    int k=0,j;
    vector<int>vi;//declare one more vector to store the sorted values as stated in question
    for (auto& it : a) { 
  
        for(j=0;j<it.second;j++)
        {
            vi.push_back(it.first); //push the values into vector based on frequency
        }
    } 
    return vi;
} 
vector<vector<int>> sortMatrixByOccurences(vector<vector<int>> m)
{
     map<int,int> a;
    int i,j;
    //insert the values in vector into map
    for(i=0;i<m.size();i++)
    {
        for(j=0;j<m[i].size();j++)
        {
            if(a.find(m[i][j])==a.end())
            {
                a[m[i][j]]=1;
            }
            else
            {
                a[m[i][j]]++;
            }
        }
    }
   vector<int>v=sort(a);
    
    int mat_size=m.size(),sp=0;
     int mat[mat_size][mat_size]={0}, k, q;
     //now insert the values into matrix diagonally starting from bottom right corner
     //This loop is for creating upper triangle i.e starting from bottom right corner
      for ( k = mat_size-1; k >=1; k--){
      i=mat_size-1;
      for ( j = k; j <=mat_size-1; j++){
         mat[i][j] = v[sp++];
         i--;
      }
   }
   //now continue with lower triangle
   //this loop is for creating lower triangle
  for ( i = mat_size-1; i >=0; i--){
      k=i;
      for ( j = 0; j <=i; j++){
         mat[k][j] = v[sp++];
        k--;
      }
   }
   //store the matrix values back into original vector m
   for ( i = 0; i < mat_size; i++){
      for(j = 0; j < mat_size; j++){
          m[i][j]=mat[i][j];
      }
   }
   
   return m;
}

int main()
{
    vector<vector<int>> m{{1,4,-2},{-2,3,4},{3,1,3}};
    int i,j;
    m=sortMatrixByOccurences(m);
    int mat_size=m.size();
   //print the values of vector m
   for ( i = 0; i < mat_size; i++){
      for(j = 0; j < mat_size; j++){
         cout<<m[i][j]<<" ";
      }
      cout<<endl;
   }//hence required result
    return 0;
}

I will also attach the output for your reference.

Output and code screenshot:

#Please dont forget to upvote if you find the solution helpful. Feel free to ask doubts if any, in the comments section. Thank you.