Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
IF there is no space contraint, we can use construct a BST and just print it out. It will take O(mn log(mn)) time.
Now that we have the space constaint, we read the first column print the lowest and delete the element. Read the next element from the row which had the lowest in the previous step and so on.
matrix = [
[20, 40, 80],
[5, 60, 90],
[45, 50, 55]
]
So you read 20 , 5 , 45
Print 5, read the next elemnt from row 2 (as 5 is from row 2)
20, 60, 45 -> print 20 -> read 40
40 60 45 -> print 40 read 80
80 60 45 -> print 45 read 50
80 60 50 -> print 50 -> read 55
80 60 55 -> print 55 nothing to read
80 60 -> print 60 read 90
80 90 -> print 80 nothing to read
90 print 90
finish
So 5, 20, 40, 45, 50 , 55, 60, 80, 90 is the output
This is m-way merging of m sorted arrays. It can be solved using min-heap (priority queue) with size m, in O(mn log m) time.
@Scott: m is the size of a column.
Imagine you have m arrays (each of size n), sorted already. You want to merge them into 1 single list.
The heap/priority queue is to store the m front elements of m arrays, initially.
Each time, the minimum element x in the heap is extracted, and put into the final list. Suppose x was come from the array k. Then, the next element of k-th array is inserted into the heap. This process continues until all elements are inserted/extracted to/from the heap.
Each insert/extract_min operation takes O(log m) for the heap of size m. Thus, overall time is: mn O(logm) = O(mn logm).
This algorithm takes O(m) space. In implementation, it takes 3m space for the heap: 1 int for the value, 1 int for the number k (for k-th array), 1 int for the index of next element in k-th array.
In C++ we can use pair of pairs, like pair<int val, pair<int k, int id> > to represent element of heap. This way will work without user-defined comparison function.
this logic is correct !! but, there's memory can store only one row at a time...
space complexity wise it's correct O(m) == O(3m)
but, this is FB question it won't be straight question, so may be there's something hidden logic
It is asked to use extra memory the size of "row", I believe this is not the expected solution..
Use a priority queue storing the active positions on the matrix, but having acustom comparison operator to compare the values in the respecive positions.
//compile as g++ -std=c++11 matrix_sort.cpp
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
void sorted_print( vector< vector<int> >& matrix )
{
typedef pair<int,int> pos_t;
if (matrix.empty())
return;
auto comp = [&matrix] ( const pos_t& a, const post_t& b ) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } ;
priority_queue< pair<int,int>, vector<pos_t> , decltype(comp) > mem(comp);
for ( int i=0; i < matrix.size(); i++)
mem.emplace( i, 0 );
while (! mem.empty() )
{
auto next = mem.top();
mem.pop();
cout << matrix[ next.first][next.second] << " ";
if ( next.second < matrix[next.first].size()-1 )
mem.emplace( next.first, next.second+1 );
}
}
int main()
{
vector< vector<int> > matrix = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
sorted_print( matrix );
}
//compile as g++ -std=c++11 matrix_sort.cpp
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
void sorted_print( vector< vector<int> >& matrix )
{
typedef pair<int,int> pos_t;
if (matrix.empty())
return;
auto comp = [&matrix] ( const pos_t& a, const post_t& b ) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } ;
priority_queue< pair<int,int>, vector<pos_t> , decltype(comp) > mem(comp);
for ( int i=0; i < matrix.size(); i++)
mem.emplace( i, 0 );
while (! mem.empty() )
{
auto next = mem.top();
mem.pop();
cout << matrix[ next.first][next.second] << " ";
if ( next.second < matrix[next.first].size()-1 )
mem.emplace( next.first, next.second+1 );
}
}
int main()
{
vector< vector<int> > matrix = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
sorted_print( matrix );
}
# Compile as Python 2.7
def MatrixSortedStr (matrix):
result = ""
m = len (matrix)
if (m == 0):
return result
n = len(matrix[0]) # length of columns
nIndex = list()
for i in range (m):
nIndex.append(0)
limit = m*n
counter = 0
while (counter < limit):
i = 0
minSet = False
minIndex = -1
while (i < m):
if (nIndex[i] < n):
if (minSet == False ):
minIndexMatrix = i
minSet = True
else:
if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
minIndexMatrix = i
i += 1
if (result == ""):
result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
else:
result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
nIndex[minIndexMatrix] += 1
counter += 1
return result
matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))
def MatrixSortedStr (matrix):
result = ""
m = len (matrix)
if (m == 0):
return result
n = len(matrix[0]) # length of columns
nIndex = list()
for i in range (m):
nIndex.append(0)
limit = m*n
counter = 0
while (counter < limit):
i = 0
minSet = False
minIndex = -1
while (i < m):
if (nIndex[i] < n):
if (minSet == False ):
minIndexMatrix = i
minSet = True
else:
if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
minIndexMatrix = i
i += 1
if (result == ""):
result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
else:
result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
nIndex[minIndexMatrix] += 1
counter += 1
return result
matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))
#compile as Python 2.7
def MatrixSortedStr (matrix):
result = ""
m = len (matrix)
if (m == 0):
return result
n = len(matrix[0]) # length of columns
nIndex = list()
for i in range (m):
nIndex.append(0)
limit = m*n
counter = 0
while (counter < limit):
i = 0
minSet = False
minIndex = -1
while (i < m):
if (nIndex[i] < n):
if (minSet == False ):
minIndexMatrix = i
minSet = True
else:
if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
minIndexMatrix = i
i += 1
if (result == ""):
result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
else:
result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
nIndex[minIndexMatrix] += 1
counter += 1
return result
matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))
This is a multi array merge similar to the mergesort but with multiple list or arrays. So a min heap is solution for this. In .NET can be done using a SortedDictionary which behave similarly to a min Heap.
I seems very complex but it is necessary to handle repeated numbers when using a SortedDictionary.
This algorithm is O(n*mlogm)
n -> total rows
m -> total columns
public static List<int> GetSortedList(int[][] matrix)
{
List<int> result = new List<int>();
SortedDitionary<int, List<Tuple<int,int>>> minHeap =
new SortedDictionar<int, List<Tuple<int, int>>>();
// Initialize the minHeap with the numbers as sorted key
// and a list of tuples with the index and the row index
// I use a list as multiple rows could have the same value.
for(int i = 0; i < matrix.Length; i++)
{
int[] array = matrix[i];
if(!minHeap.ContainsKey(array[0]))
{
minHeap.Add(
array[0],
new List<Tuple<int,int>> {
new Tuple<int, int[]>(0, array)
});
}
else
{
minHeap[array[0].Add(new Tuple<int, int[]>(0, array));
}
}
while(minHeap.Count > 0)
{
var kvp = minHeap.First(); // O(1)
minHeap.Remove(kvp.Key);
// Going through the list of repeated number arrays
for(int i = 0; i < kvp.Value.Count; i++)
{
int number = kvp.Key;
// Adding to the result
result.Add(number);
int nextIndex = kvp.Value[i].Item1 + 1;
int[] array = kvp.Value[i].Item2;
// It just picked the last number so not adding back
if(nextIndex == array.Length)
{
continue;
}
int next = array[index];
if(!minHeap.ContainsKey(next))
{
// O(logm)
minHeap.Add(
next,
new List<Tuple<int,int[]>> {
new Tuple<int, int[]>(nextIndex , array)
});
}
else
{
// O(logm)
minHeap[next].Add(
new Tuple<int, int[]>(nextIndex , array));
}
}
}
return result;
}
Note: n is the number of rows, m number of columns.
Here's a priority queue n-way merge based code where I'm indeed pulling at most one row at a time into memory. The total space complexity is O(m) + O(3*n) though. Time complexity is: O(n*m*log(n)) + O(n*m^2*log(n)) so O(n*m^2*log(n)). I'm assuming pulling the row I need into memory is O(m).
class IntegerWithOrigin {
// value, row, column
}
public void printInOrder(Matrix matrix) {
if (matrix == null) {
return;
}
PriorityQueue<IntegerWithOrigin> minQueue = new HeapPriorityQueue<IntegerWithOrigin>();
int rowInBuffer = -1;
int[] buffer = new int[matrix.getM()];
for (int i = 0; i < matrix.getN(); i++) {
matrix.readRowInto(i, buffer);
rowInBuffer = i;
minQueue.add(new IntegerWithOrigin(buffer[0], i, 0));
}
while (!minQueue.isEmpty()) {
IntegerWithOrigin min = minQueue.getTop();
System.out.println(min.getValue());
if (min.getColumn() < matrix.getM() - 1) {
if (min.getRow() != rowInBuffer) {
matrix.readRowInto(buffer, min.getRow());
}
min.setColumn(min.getColumn() + 1);
min.setValue(buffer[min.getColumn()]);
minQueue.add(min);
}
}
}
Here is a brute force solution with O(m) space complexity. Time complexity is O(n^2*m^3):
public void printInOrder(Matrix matrix) {
if (matrix == null) {
return;
}
int[] buffer = new int[matrix.getM()];
int lastPrintedValue = Integer.MIN_VALUE;
int printedElements = 0;
while (printedElements != matrix.getN() * matrix.getM()) {
int currentMin = Integer.MAX_VALUE;
for (int i = 0; i < matrix.getN(); i++) {
matrix.readRowInto(i, buffer);
int at = 0;
while (at < buffer.length && buffer[at] <= lastPrintedValue) {
at++;
}
if (at < buffer.length && buffer[at] < currentMin) {
currentMin = buffer[at];
}
}
System.out.println(currentMin);
lastPrintedValue = currentMin;
printedElements++;
}
}
Merge multiple sorted arrays without min heap
#define INT_MAX 2147483647
void PrintMatrix(int *Matrix, int M, int N)
{
int *ArrIndexes = new int[N];
for(int i = 0; i < N; i++)
{
ArrIndexes[i] = 0;
}
for(int i = 0; i < M*N; ++i)
{
int Min = INT_MAX;
int MinArray = 0;
for(int j = 0; j < N; j++)
{
int *arr = &Matrix[j*M];
if(ArrIndexes[j] < M)
{
if(arr[ ArrIndexes[j] ] < Min)
{
Min = arr[ ArrIndexes[j] ];
MinArray = j;
}
}
}
TRACE("%d", Min);
if(i != M*N-1)
{
TRACE(", ");
}
ArrIndexes[MinArray]++;
}
}
void ArrayTest::run()
{
int Matrix[3][3] = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
PrintMatrix((int *)Matrix, 3, 3);
}
def matrix_to_list(mtx, n, m):
heap = []
ret = []
for i in range(len(mtx)):
heapq.heappush(heap, Node(mtx[i][0], i, 0))
while len(heap) > 0:
item = heapq.heappop(heap)
if item.col < (m - 1):
heapq.heappush(heap, Node(mtx[item.row][item.col + 1], item.row, item.col + 1))
ret.append(item.num)
return ret
Algorithm: Treat the rows as sorted elements of a sequence and perform mergesort on the elements.
Work:
O(mn*log(m))
Span:
O(mn)
Proof of Work and Span: The merge operation is linear work, so the work of merge at the root node is
mn
. The work at the lowest level of the call tree is
2^log(m)*n = mn
. Thus, work of the algorithm is the same at all levels. By the brick method (i.e. Master's Theorem), overall work must be
O(mn*log(m))
. Algorithm has
O(mn)
at the root and
O(n)
span at the lowest level of the call tree, so it is root-dominated in terms of span. Thus, span is
O(mn)
.
This code is using O(n*m)complexity. row is n, col is m.
if i m wrong, than plz, correct me.
public class Matrix1{
public static void main(String []args){
int [][] m=new int[][]{
{ 20, 40, 80 },
{ 5, 60, 90 },
{ 45, 50, 55 } };
int i=0,j=1,k=2,a=0,b=0,c=0;
for(int p=0;p<9;p++){
if(c<3&&a<3&&b<3){
if(m[i][a]<m[j][b]&&m[i][a]<m[k][c]){
System.out.print(m[i][a]+" , ");
a++;
if(c==3)
mass(m,j,b,k,c,p);
}
else if(m[j][b]<m[i][a]&&m[j][b]<m[k][c]){
System.out.print(m[j][b]+" , ");
b++;
if(c==3)
mass(m,i,a,k,c,p);
}
else if(m[k][c]<m[j][b]&&m[k][c]<m[i][a]){
System.out.print(m[k][c]+" , ");
c++;
if(c==3)
mass(m,i,a,j,b,p);
}
}
}
}
public static void mass(int arr[][],int i,int a,int j,int b,int p){
int l=9-p;
for(int e=0;e<l;e++){
if(a==3&&b!=3){
System.out.print(arr[j][b]+" , "); b++;
}
if(b==3&&a!=3){
System.out.print(arr[i][a]+" , "); a++;
}
if(a!=3&&b!=3){
if(arr[i][a]<arr[j][b]){
System.out.print(arr[i][a]+" , ");
a++;
}
else{
System.out.print(arr[j][b]+" , ");
b++;
}
}
}
}
}
Without a space constraint, we can solve this by inserting all the elements into a binary search tree, then pulling them out in order.
O(m * n * log(m * n))
(Note that std::set is typically implemented as a binary search tree)
void printSortedWithBST(int **data, int m, int n)
{
std::set<int> tree;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
tree.insert(data[i][j]);
}
}
for (set<int>::const_iterator it = tree.begin(); it != tree.end(); ++it)
{
printf("%d ", *it);
}
printf("\n");
}
If we are space constrained, we can keep an array of indices to indicate our current position in each row, then continuously pull out the lowest value at the current indices until we have printed all the numbers
O(m * n * n)
void printSortedSpaceConstrained(int **data, int m, int n)
{
int toPrint = m * n;
int index[m];
for (int i = 0; i < m; ++i)
{
index[i] = 0;
}
while (toPrint > 0)
{
int minValue = INT_MAX;
int minIndex = 0;
for (int i = 0; i < m; ++i)
{
if (index[i] < n && data[i][index[i]] < minValue)
{
minValue = data[i][index[i]];
minIndex = i;
}
}
printf("%d ", minValue);
++index[minIndex];
--toPrint;
}
printf("\n");
}
Without a space constraint, we can insert all the elements into a binary search tree, then pull them out in order
(Note: std::set is typically implemented as a BST)
O(m * n * log(m * n))
void printSortedWithHeap(int **data, int m, int n)
{
std::set<int> tree;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
tree.insert(data[i][j]);
}
}
for (std::set<int>::const_iterator it = tree.begin(); it != tree.end(); ++it)
{
printf("%d ", *it);
}
printf("\n");
}
With the space constraint, we can keep an array of indices to indicate the position in each row of the lowest value that hasn't been printed, then continuously pull out the lowest value of the current indices until you have printed all the numbers
(Note: I am keeping n indices, which technically is a column, not a row, but it will always be ints, even if the data represents objects of a different kind)
O(m * n * n)
void printSortedSpaceConstrained(int **data, int m, int n)
{
int toPrint = m * n;
int index[m];
for (int i = 0; i < m; ++i)
{
index[i] = 0;
}
while (toPrint > 0)
{
int minValue = INT_MAX;
int minIndex = 0;
for (int i = 0; i < m; ++i)
{
if (index[i] < n && data[i][index[i]] < minValue)
{
minValue = data[i][index[i]];
minIndex = i;
}
}
printf("%d ", minValue);
++index[minIndex];
--toPrint;
}
printf("\n");
}
Here is my Java implementation using PriorityQueues it uses O(m) space
import java.util.PriorityQueue;
public class SortMatrix {
public static void main(String[] args) {
int[][] matrix = {
{45, 50, 55},
{20, 40, 80},
{5, 60, 90},
{1, 2, 3},
};
sort(matrix);
}
public static void sort(int[][] matrix) {
for (int i = 1; i < matrix.length; i++) {
if (matrix[i-1][0] > matrix[i][0]) {
int[] tmp = matrix[i-1];
matrix[i-1] = matrix[i];
matrix[i] = tmp;
i = 0;
}
}
int rows = matrix.length, cols = matrix[0].length;
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
Integer peek = heap.peek();
if (peek != null && peek > matrix[i][j]) {
System.out.println(matrix[i][j] + " ");
continue;
}
if (heap.size() > cols) {
System.out.println(heap.poll() + " ");
}
heap.add(matrix[i][j]);
}
}
while (heap.peek() != null) {
System.out.println(heap.poll() + " ");
}
}
}
public static void main(String[] args) {
int array[][] = { { 20, 40, 80 }, { 5, 60, 90 }, { 45, 50, 55 } };
int sortIndex[] = new int[array.length];
for (int i = 0; i < array.length; i++) {
sortIndex[i] = 0;
}
for (int i = 0; i < array.length * array[0].length; i++) {
int min = 0;
for (int j = 0; j < sortIndex.length; j++) {
if (sortIndex[j] != -1) {
min = array[j][sortIndex[j]];
break;
}
}
int indexMin = 0;
for (int j = 1; j < sortIndex.length; j++) {
if (sortIndex[j] != -1 && array[j][sortIndex[j]] < min) {
min = array[j][sortIndex[j]];
indexMin = j;
}
}
System.out.print(min + " ");
sortIndex[indexMin] = sortIndex[indexMin] + 1;
if (sortIndex[indexMin] >= array[0].length) {
sortIndex[indexMin] = -1;
}
}
}
public static void main(String[] args) {
int array[][] = { { 20, 40, 80 }, { 5, 60, 90 }, { 45, 50, 55 } };
int sortIndex[] = new int[array.length];
for (int i = 0; i < array.length; i++) {
sortIndex[i] = 0;
}
for (int i = 0; i < array.length * array[0].length; i++) {
int min = 0;
for (int j = 0; j < sortIndex.length; j++) {
if (sortIndex[j] != -1) {
min = array[j][sortIndex[j]];
break;
}
}
int indexMin = 0;
for (int j = 1; j < sortIndex.length; j++) {
if (sortIndex[j] != -1 && array[j][sortIndex[j]] < min) {
min = array[j][sortIndex[j]];
indexMin = j;
}
}
System.out.print(min + " ");
sortIndex[indexMin] = sortIndex[indexMin] + 1;
if (sortIndex[indexMin] >= array[0].length) {
sortIndex[indexMin] = -1;
}
}
}
using Groovy way and recursion
class ListOrderNumbersFromMatrix {
def static evaluate(matriz) {
def minQueue = null
def min = null
matriz.each() { Queue row ->
if (min == null)
min = row.peek()
if (row.peek() && row.peek() <= min)
minQueue = row;
}
println minQueue.poll();
if (!matriz.flatten().empty)
evaluate(matriz)
}
static void main(String[] args) {
def matriz = [
[20,40,80] as LinkedList,
[5,60,90] as LinkedList,
[45,50,55] as LinkedList
]
ListOrderNumbersFromMatrix.evaluate(matriz);
}
}
You can refer to this code. It uses heap data structure.
This code works fine except the first element printed will always be mat[0][0].
package practice;
import java.util.Scanner;
public class matrix_sorting_problem {
static int m=3,n=4;
static int[] a;
static int[][] mat;
public static void main(String args[]){
mat=new int[m][n];
Scanner s=new Scanner(System.in);
for(int i=0;i<m;i++){
System.out.println("enter values for col "+i );
for(int j=0;j<n;j++){
mat[i][j]=s.nextInt();
}
}
a=new int[m];
int c=0;
int cou=0;
for(int i=0;i<m;){
if(c<n){
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
c++;
i++;
}
else{
c=0;
cou++;
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
i++;
}
}
matrix_sorting_problem m=new matrix_sorting_problem();
for(int x=0;x<11;x++)
System.out.println(m.getmin());
}
void heapify(){
int temp=a[0];
int col=temp%10;
int row=(temp/10)%10;
//System.out.println(a[0]+" "+col+" "+row);
if((col+1)<n){
a[0]=(mat[row][col+1])*100+row*10+col+1;
//System.out.println(a[0]+" "+col+" "+row);
}else{
int flag=0;int i=0;
col=(a[i]%10)+1;
row=(a[i]/10)%10;
while(flag!=1){
//System.out.println(col+ " " +row);
//System.out.println("stuck here");
if(col<n){
a[0]=(mat[row][col])*100+row*10+col;
//System.out.println(a[0]);
flag=1;
}else{
i++;
}
if(i<m){
col=(a[i]%10)+1;
row=(a[i]/10)%10;}
else{
a[0]=999;
flag=1;
}
}
}
//a[0]=a[a.length-1];
int i=0;
/*for( i=0;i<m;i++){
System.out.print(" "+ a[i]);
}*/
i=0;
while(((2*i)+1<a.length)&&(((a[i]/100)>(a[2*i+2]/100))||((a[i]/100)>(a[2*i+1]/100)))){
//System.out.println("stuck here in while- value of i"+ i);
if(a[2*i+1]/100>a[2*i+2]/100){
// System.out.println("executing if");
int temp1=a[i];
a[i]=a[2*i+2];
a[2*i+2]=temp1;
i=2*i+2;
}else{
// System.out.println("executing else");
int temp1=a[i];
a[i]=a[2*i+1];
a[2*i+1]=temp1;
i=2*i+1;
}
}
}
int getmin(){
int temp= a[0];
//System.out.println(temp);
heapify();
return temp/100;
}
}
The below code is just for reference. It uses heap data structure.
This code works fine except the first element printed will always be mat[0][0].
package practice;
import java.util.Scanner;
public class matrix_sorting_problem {
static int m=3,n=4;
static int[] a;
static int[][] mat;
public static void main(String args[]){
mat=new int[m][n];
Scanner s=new Scanner(System.in);
for(int i=0;i<m;i++){
System.out.println("enter values for col "+i );
for(int j=0;j<n;j++){
mat[i][j]=s.nextInt();
}
}
a=new int[m];
int c=0;
int cou=0;
for(int i=0;i<m;){
if(c<n){
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
c++;
i++;
}
else{
c=0;
cou++;
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
i++;
}
}
matrix_sorting_problem m=new matrix_sorting_problem();
for(int x=0;x<11;x++)
System.out.println(m.getmin());
}
void heapify(){
int temp=a[0];
int col=temp%10;
int row=(temp/10)%10;
//System.out.println(a[0]+" "+col+" "+row);
if((col+1)<n){
a[0]=(mat[row][col+1])*100+row*10+col+1;
//System.out.println(a[0]+" "+col+" "+row);
}else{
int flag=0;int i=0;
col=(a[i]%10)+1;
row=(a[i]/10)%10;
while(flag!=1){
//System.out.println(col+ " " +row);
//System.out.println("stuck here");
if(col<n){
a[0]=(mat[row][col])*100+row*10+col;
//System.out.println(a[0]);
flag=1;
}else{
i++;
}
if(i<m){
col=(a[i]%10)+1;
row=(a[i]/10)%10;}
else{
a[0]=999;
flag=1;
}
}
}
//a[0]=a[a.length-1];
int i=0;
/*for( i=0;i<m;i++){
System.out.print(" "+ a[i]);
}*/
i=0;
while(((2*i)+1<a.length)&&(((a[i]/100)>(a[2*i+2]/100))||((a[i]/100)>(a[2*i+1]/100)))){
//System.out.println("stuck here in while- value of i"+ i);
if(a[2*i+1]/100>a[2*i+2]/100){
// System.out.println("executing if");
int temp1=a[i];
a[i]=a[2*i+2];
a[2*i+2]=temp1;
i=2*i+2;
}else{
// System.out.println("executing else");
int temp1=a[i];
a[i]=a[2*i+1];
a[2*i+1]=temp1;
i=2*i+1;
}
}
}
int getmin(){
int temp= a[0];
//System.out.println(temp);
heapify();
return temp/100;
}
}
/* Using In place sorting , no additional rows in memory, making use of the sort order */
#include <stdio.h>
2
3 void main () {
4
5 #define ROW 3
6 #define COL 3
7
8 int mat[ROW][COL]= {
9 { 0,1,5,} ,
10 { 5, 90,100} ,
11 { -1,2,2 }
12
13 } ;
14
15 int swapped_column=-1,swapped_row=-1,i,j,k,m,tmp,l,swapped = 0;
16
17
18 for (l=0;l<ROW;l++) {
19 for (i=0;i<COL;i++) {
20 for (j=l+1;j<ROW;j++) {
21
22 swapped_column = 0;
23 swapped_row = j;
24
25 if ( *(*(mat +l) + i ) > *(*(mat + j) + 0 )) {
26 swapped = 1 ;
27 for (k=1;k<COL ; k++ ) {
28
29 if ( *(*(mat +l) + i ) > *(*(mat + j) + k )) {
30 swapped_column = k;
31 swapped_row = j;
32 swapped = 1 ;
33 }
34
35 }
36 if (swapped) {
37 tmp = *(*(mat +l) + i ) ;
38 *(*(mat +l) + i ) = *(*(mat + j) + 0 ) ;
39 for (m=0;(swapped_column> 0 ) && (m<swapped_column ); m++ ) {
40 *(*(mat +j)+m) = *(*(mat +j)+ (m+1)) ;
}
42 *(*(mat +swapped_row) + swapped_column) = tmp ;
43 swapped =0 ;
44 }
45 }
46 }
47 }
48 }
49
50
51 for (i=0;i<ROW;i++) {
52 for (j=0;j<COL;j++) {
53 printf("%d\t", *(*(mat+i)+j) ) ;
54 }
55 printf("\n") ;
56 }
57
58 }
1 /* Using in place sort., maing use of the existing row sort order */
2 #include <stdio.h>
3
4 void main () {
5
6 #define ROW 3
7 #define COL 3
8
9 int mat[ROW][COL]= {
10 { 0,1,5,} ,
11 { 5, 90,100} ,
12 { -1,2,2 }
13
14 } ;
15
16 int swapped_column=-1,swapped_row=-1,i,j,k,m,tmp,l,swapped = 0;
17
18
19 for (l=0;l<ROW;l++) {
20 for (i=0;i<COL;i++) {
21 for (j=l+1;j<ROW;j++) {
22
23 swapped_column = 0;
24 swapped_row = j;
25
26 if ( *(*(mat +l) + i ) > *(*(mat + j) + 0 )) {
27 swapped = 1 ;
28 for (k=1;k<COL ; k++ ) {
29
30 if ( *(*(mat +l) + i ) > *(*(mat + j) + k )) {
31 swapped_column = k;
32 swapped_row = j;
33 swapped = 1 ;
34 }
35
36 }
37 if (swapped) {
38 tmp = *(*(mat +l) + i ) ;
39 *(*(mat +l) + i ) = *(*(mat + j) + 0 ) ;
40 for (m=0;(swapped_column> 0 ) && (m<swapped_column ); m++ ) {
41
42
43 *(*(mat +j)+m) = *(*(mat +j)+ (m+1)) ;
44
45 }
46 *(*(mat +swapped_row) + swapped_column) = tmp ;
47 swapped =0 ;
48 }
49 }
50 }
51 }
52 }
53
54
55 for (i=0;i<ROW;i++) {
56 for (j=0;j<COL;j++) {
57 printf("%d\t", *(*(mat+i)+j) ) ;
58 }
59 printf("\n") ;
60 }
61
62 }
private ArrayList<ArrayList<Integer>> mMatrix;
private void initMatrix() {
if (mMatrix == null) {
mMatrix = new ArrayList<>();
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(20);
tmp.add(40);
tmp.add(80);
mMatrix.add(tmp);
ArrayList<Integer> tmp2 = new ArrayList<>();
tmp2.add(5);
tmp2.add(60);
tmp2.add(90);
mMatrix.add(tmp2);
ArrayList<Integer> tmp3 = new ArrayList<>();
tmp3.add(45);
tmp3.add(50);
tmp3.add(55);
mMatrix.add(tmp3);
}
}
private int getColMin() {
int minIndex, minValue;
ArrayList<Integer> row = mMatrix.get(0);
minIndex = 0;
minValue = row.get(0);
for (int i = 1; i < mMatrix.size(); i++) {
row = mMatrix.get(i);
int nextValue = row.get(0);
minValue = Math.min(minValue, nextValue);
if (minValue == nextValue) {
minIndex = i;
}
}
return minIndex;
}
private void printSorted() {
while (!mMatrix.isEmpty()) {
int colMin = getColMin();
ArrayList<Integer> row = mMatrix.get(colMin);
// Print: row.get(0));
row.remove(0);
if (row == null || row.isEmpty()) {
mMatrix.remove(colMin);
}
}
}
Here is my solution using mean heap. Space complexity is O(m).
void print_matrix(int *matrix[], int h, int w)
{
int x, y;
heap minHeap(h, true);
for (y = 0; y <h; y++)
minHeap.add(node(0, y, matrix[y][0]));
while(minHeap.size())
{
node min = minHeap.extract();
cout << min.value << " ";
if (min.x < w-1)
minHeap.add(node(min.x+1, min.y, matrix[min.y][min.x+1]));
}
}
1. find the smallest number in the first column and print it out.
2. remove the smallest number from its row, and shift all number to the left.
3. repeat.
Assume the max value in the matrix is smaller than 10^32-1
public void printSortedMatrix(int[][] matrix)
{
for(int a=0;a<matrix.length*matrix[0].length;a++){
int min = Integer.MAX_VALUE;
int index = 0;
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] < min){
min = matrix[i][0];
index = i;
}
}
System.out.print(min+",");
for(int j=1;j<matrix[0].length;j++){
matrix[index][j-1] = matrix[index][j];
}
matrix[index][matrix[0].length-1] = Integer.MAX_VALUE;
}
}
All the above solutions provide a good way of solving this problem except that memory requirement isn't met. How about we solve it this way.
Consider the matrix to be 3X3.
1. Sort the [0,0] [0,1] and [0,2], this will result in sorted first row. Infact this step can be skipped since individual rows are already sorted.
2. Then sort [0,1] [0,2] and [1,0] (basically it is a sliding window of the number of elements in a row.
3. Then sort [0,2] [1,0] and [1,2] and so on
4. Need to do this till no more swaps are happening. Basically a bubble sort in K batches.
{{ { void CustomSort(int** matrix, int Rows, int Cols, int startIndex, int endIndex, bool& swapped)
{
swapped = false;
for (int i = startIndex; i < endIndex; i++)
{
int currentRow = i / Rows;
int currentCol = i / Cols;
int nextRow = (i + 1) / Rows;
int nextCol = (i + 1) / Cols;
if (matrix[currentRow][currentCol] > matrix[nextRow], [nextCol])
{
swap(matrix, currentRow, currentCol, nextRow, nextCol);
swapped = true;
}
}
}
void MatrixSortconstrainedByRowMemory(int** Matrix, int Rows, int Cols)
{
int totalElements = Rows * Cols;
Bool swapped = true;
while (swapped)
{
for (int i = 0; i < totalElements; i = i + Cols)
{
CustomSort(Matrix, Rows, Cols, i, (i + Cols) - 1, swapped);
}
}
}
} }}
{{ {
void CustomSort(int** matrix, int Rows, int Cols, int startIndex, int endIndex, bool& swapped)
{
swapped = false;
for (int i = startIndex; i < endIndex; i++)
{
int currentRow = i / Rows;
int currentCol = i / Cols;
int nextRow = (i + 1) / Rows;
int nextCol = (i + 1) / Cols;
if (matrix[currentRow][currentCol] > matrix[nextRow], [nextCol])
{
swap(matrix, currentRow, currentCol, nextRow, nextCol);
swapped = true;
}
}
}
void MatrixSortconstrainedByRowMemory(int** Matrix, int Rows, int Cols)
{
int totalElements = Rows * Cols;
Bool swapped = true;
while (swapped)
{
for (int i = 0; i < totalElements; i = i + Cols)
{
CustomSort(Matrix, Rows, Cols, i, (i + Cols) - 1, swapped);
}
}
}
} }}
Simple solution: Use MinHeap.
- patrj March 07, 2015Add all the elements of first column to the heap and min heapify, print the root, remove and put the next from the same row. Repeat.