**Problem:**

Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

**Solution:**

A possible solution utilizes a propagating front separating the elements that have already been sorted into the 1D array from those that are still pending. The solution is \(\mathcal{O}(N)\) in space because of the storage required for the front and \(\mathcal{O}(N^3)\) in time as the insertion of each of the \(N^2\) numbers requires a comparison of the N front values (at most).

The algorithm generalizes to sorting \(D\)-dimensional arrays, in which case the front has dimension \(D-1\).

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream> #include <limits> using namespace std; // typedef double arraytype; typedef int arraytype; #define N 4 // example with a 4x4 matrix const arraytype mat[N][N] = {{1,2,4,5},{2,3,5,7},{4,6,12,13},{5,20,21,22}}; // sorted 2D array int main () { arraytype arr[N*N] = {0}; // initialize the array to zero unsigned int front[N] = {0}; // use a front that contains the first number to consider for each column, i.e., // the first number in each column that has not be sorted in the 1D array yet for ( unsigned int n = 0; n != N*N; ++n ) { // loop the 1D array arraytype m = numeric_limits<arraytype>::max(); // init smallest element found to max unsigned int f = 0; // variable for updating the front in one column for ( unsigned int col = 0; col != N; ++col ) { // walk the 2D array by columns if ( front[col] == N ) continue; // if the front hits row N in column col go to next column if ( (col > 0) && (front[col] == 0) && (front[col-1] == 0) ) break; // optimization: stop the current column iteration if the front in column col and col-1 is at row 0 (and col > 0) if ( m > mat[front[col]][col] ) { // check 2D array for value smaller than m m = mat[front[col]][col]; // update m f = col; // set f for updating front but don't update front yet because another smaller value might be found } } arr[n] = m; // set value in 1D array front[f]++; // update front } for ( auto& i : arr ) // print sorted 1D array cout << i << " "; cout << endl; return 0; }

Solutions with complexity of \(\mathcal{O}(N^2)\log(N)\) are achieved by maintaining the front values in a priority queue. This is the same as the merge step of mergesort.

Simply adding all values of the 2D array into a min heap and extracting them of the top is also \(\mathcal{O}(N^2)\log(N)\) (as \(\mathcal{O}(N^2)\log(N^2) = \mathcal{O}(N^2)2\log(N) = \mathcal{O}(N^2)\log(N)\)). Adding the values to the heap following diagonals from the largest number (bottom right) to the smallest number (top left) will reduce the bubble down time.