Beautify a Matrix

user_9843722 0
Viewed 2571

I recently received this in an interview and couldn't figure out how to solve it, I want to make sure I learn from this and know how to solve it for the future.

Question:

Let's define the beauty of a square matrix as the minimal positive integer which doesn't appear in this matrix. For example, if the square matrix 2 x 2 contains the numbers 1, 2, 4, and 6, then the beauty of this matrix will be equal to 3.

You are given a square matrix of positive integers called 'numbers', and an integer 'size' which evenly divides numbers.length. You task is to arrange the matrix elements in the following way:

  • Split the matrix into non-overlapping 'size x size' submatrices;
  • Arrange all the submatrices in ascending order of their beauty, then put them back into the matrix.

The order of the submatrices should be from left to right, from top to bottom. In case of a tie (If two submatrices have the same beauty) place them in relative order they were originally presented in the initial matrix. Here's the order of the submatrices in the case where there are 9 of them (ie. when numbers.length / size = 3):

1   2   3  | 1   2   3 | 1   2   3 
4   5   6  | 4   5   6 | 4   5   6 
7   8  10  | 7   9  10 | 8   9  10 
----------------------------------
1   2   3  | 1   2   3 | 1   2   3  
4   5   7  | 4   6   7 | 5   6   7 
8   9  10  | 8   9  10 | 8   9  10 
----------------------------------  
1   2   4  | 1   3   4 | 2   3   4  
5   6   7  | 5   6   7 | 5   6   7
8   9  10  | 8   9  10 | 8   9  10 

is (in terms of *beauty*):

9 | 8 | 7
---------
6 | 5 | 4
---------
3 | 2 | 1

And should be returned as:

2   3   4  | 1   3   4 | 1   2   4  
5   6   7  | 5   6   7 | 5   6   7
8   9  10  | 8   9  10 | 8   9  10
----------------------------------
1   2   3  | 1   2   3 | 1   2   3  
5   6   7  | 4   6   7 | 4   5   7 
8   9  10  | 8   9  10 | 8   9  10 
----------------------------------  
1   2   3  | 1   2   3 | 1   2   3 
4   5   6  | 4   5   6 | 4   5   6 
8   9  10  | 7   9  10 | 7   8  10

As a side note, I tend to be pretty bad at matrix manipulation type of questions in interviews so any advice or tips on how to improve would be appreciated!

matrix-multiplication matrix sorting algorithm
2 Answers

In my C# version, I am using a class SubMatrix to bundle the functionality of sub-matrices:

using System;
using System.Collections.Generic;
using System.Linq;

namespace akMatrixBeauty
{
    class SubMatrix : IComparable<SubMatrix>
    {
        private int[,] matrix;   //  main matrix, avoids some copy operations
        private int row0;        //  top row
        private int col0;        //  left column
        private int size;        //  sub-matrix dimension
        private int beauty;      //  calculated beauty
        private int order;       //  iteration index of sub_matrix

        //  construct submatrix
        public SubMatrix(int[,] matrix, int row0, int col0, int size)
        {
            this.matrix = matrix;
            this.row0 = row0;
            this.col0 = col0;
            this.size = size;

            beauty = ComputeBeauty();
            order = row0 * size + col0;
        }

        //  indexer: return element of sub-matrix from the main matrix
        public int this[int row, int col]
        {
            get { return matrix[row0 + row, col0 + col]; }
        }

        //  compare against another sub-matrix for sorting
        public int CompareTo(SubMatrix other)
        {
            int delta = beauty.CompareTo(other.beauty);

            //  resolve tie, if needed
            return (delta != 0) ? delta : order.CompareTo(other.order);
        }

        //  this comparator demonstrates some Linq wizardry
        //  might be useful for interviews ...
        private int ComputeBeauty()
        {
            //  iterate through sub-matrix to collect all elements         row     col
            var elements = Enumerable.Range(0, size*size).Select(i => this[i/size, i %size]);

            //  return the smallest positive integer not contained
            return Enumerable.Range(1, elements.Max()).Where(e => !elements.Contains(e)).Min();
        }
    }
}

The main program constructs a list of sub-matrices. It sorts the list using the comparator function of class SubMatrix.

using System;
using System.Collections.Generic;

namespace akMatrixBeauty
{
    class Program
    {
        static void Main(string[] args)
        {
            //  initialize
            var matrix = new int[,]
            {
                { 1, 2, 3, 1, 2, 3, 1, 2, 3},
                { 4, 5, 6, 4, 5, 6, 4, 5, 6},
                { 7, 8,10, 7, 9,10, 8, 9,10},
                { 1, 2, 3, 1, 2, 3, 1, 2, 3},
                { 4, 5, 7, 4, 6, 7, 5, 6, 7},
                { 8, 9,10, 8, 9,10, 8, 9,10},
                { 1, 2, 4, 1, 3, 4, 2, 3, 4},
                { 5, 6, 7, 5, 6, 7, 5, 6, 7},
                { 8, 9,10, 8, 9,10, 8, 9,10}
            };
            const int size = 3;
            var subMatrices = new List<SubMatrix>();
            int rows = matrix.GetLength(0);
            int cols = matrix.GetLength(1);

            for (int row = 0; row < rows; row += size)
                for (int col = 0; col < cols; col += size)
                {
                    var subMatrix = new SubMatrix(matrix, row, col, size);

                    subMatrices.Add(subMatrix);
                }

            ShowMatrix(subMatrices, size, rows, cols);

            //  sort in ascending order of beauty and original position
            //  cf. SubMatrix.CompareTo() 
            subMatrices.Sort();

            ShowMatrix(subMatrices, size, cols, rows);

            Out("");
        }

        private static void ShowMatrix(List<SubMatrix> subMatrices, int size, int rows, int cols)
        {
            Out("");

            for (int row = 0; row < rows; row++)
            {
                string s = "";

                for (int col = 0; col < cols; col++)
                {
                    //  combination of row and col determines the position of the sub-matrix
                    var subMatrix = subMatrices[(row / size) * (cols / size) + (col / size)];

                    s += $"{subMatrix[row % size, col % size], 3}";

                    if (((col + 1) % size == 0) && (col + 1 != cols))
                    {
                        s += " | ";   //  column separator
                    }
                }

                Out(s);

                if (((row + 1) % size == 0) && (row + 1 != rows))
                {
                    //  row separator
                    s = " " + new string('-', 3 * (cols + cols / size - 1));
                    Out(s);
                }
            }

            Out("");
        }

        private static void Out(string s)
        {
            Console.WriteLine(s);
        }
    }
}
user_19110640

Java:

int[][] beautifyMatrix(int[][] m, int size) {
    Map<Integer, List<int[][]>> map = new TreeMap<>();

    for (int i=0; i<m.length; i+=size) {
        for (int j=0; j<m.length; j+=size) {
            fillMap(m, i, j, map, size);
        }
    }

    int [][] res = new int[m.length][m.length];
    int i = 0;
    int j = 0;
    for (Map.Entry<Integer, List<int[][]>> entry : map.entrySet()) {
        for (int[][] sub : entry.getValue()) {
            for (int k=0; k<sub.length; k++) {
                for (int l=0; l<sub.length; l++) {
                    res[k+i][j+l] = sub[k][l];
                }
            }
        }
        if (j < m.length) {
            j += size;
        }
        else {
            i += size;
            j = 0;
        }
    }

    return res;
}

private void fillMap(int [][] m, int i, int j, Map<Integer, List<int[][]>> map, int size) {
    int [][] subM = new int[size][size];
    int row = 0;
    int col = 0;
    for (int k=i; k<size; k++) {
        for (int l=j; l<size; l++) {
            subM[row][col++] = m[k][j];
        }
        row++;
    }

    int beauty = getBeauty(subM, size);
    List<int[][]> subs = map.getOrDefault(beauty, new ArrayList<>());
    subs.add(subM);
    map.put(beauty, subs);
}

private int getBeauty(int[][] m, int size) {
    int total = size * size;
    for (int i=0; i<m.length; i++) {
        for (int j=0; j<m.length; j++) {
            total -= m[i][j];
        }
    }

    return total;
}
user_16672160
Related