Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
I edited it for info. ...with more details .. pls let me know if you need complexity analysis etc.
Here is detail:
cs.stackexchange.com/questions/12853/heap-give-an-on-lg-k-time-algorithm-to-merge-k-sorted-lists-into-one-so.
@Ajeet. No need for reference or comp. analysis. or book chapter bro. Work from first principles.
See above my earlier reply. I am fairly certain it is O(N^2 lgN)
Doubt it's O( NlgN )
You have to push N^2 elements in and out of an _up to_ N element min heap.
That's O(N^2) * O(lgN)
You keep editing your initial post making it look more accurate. Why not just comment reply?
i think it's better to use different letters. mixing 'n' and 'N' makes it unclear.
change to something like M log N, and say that M = N^2, the total amount of numbers.
Yes agree, that's why initially i posted it with O(NlogN) and that creates all confusion ...it should be .. O(MlogN): where M = total number of elements = N^2.
Edited it ...
It seems to me that, in something like O(n), 'n' is commonly understood as referring to the number of elements one is asked to sort, etc.. NxN, in this particular question, is referring the width and height of a table which is a totally different meaning. I think people have been confusing the two.
The definition of n in the time complexity, this is just total number of elements, so I must agree with Michael J Keating who gave us the most closed answer.
Merge Sort is just known as O(n log n), and the time complexity of his algorithm is less than Merge Soft big O analysis. The N for the 2D matrix in the question is differ from n in the time complexity computation as it is just total number of elements.. don't be confused if I am right...
There is an N in the problem, nothing more nothing less.
some other n, some other K , redefining N=all elements .... no
We need to stop memorizing letters along with theorems and matching them to historical studies and problems.
This is like first year physics when people got confused because the diff. equation for the spring based harmonic oscillator is x ' = something.
"Professor, but isn't it dy/dx with x independent variable? it's always f(x) = something in calculus books"
Michael and Sung:
Letters don't matter. We try to measure the size of the input with the most "independent" and "fundamental" measure possible.
Ok say we are using n or N for measuring things.
If we let n (N) be the numbers of elements, fine.
But this is equal to the square of the width of the matrix. Does it not make sense to use the width instead?
Let's see:
1) If we used number of elements, then sure we can regurgitate formulas (nlgn for mergesort, klgn or whatever for merging k lists), but does it really give insight into this specific problem?
For one, think about O(nlgn) (if we used # elem.) vs. O(n^2 lg n) (if we used width) to describe the runtime of mergesort.
Which is more useful to this problem?
2) n or N or K are irrelevant and can be interchanged for y, u, p, cats, dogs, blah in big-O.
These are "dummy variables" just like the x in f(x) or y in integral(f(y)dy).
Don't commit too many dummy variables to memory. When you study something, don't burn "n is used for this problem" , "K is used for merge lists" into your ROM.
Ok, this whole thread got swamped out by
1) incorrect use of bigO and letters and stating theorems
2) claiming solutions broke the theoretical minimum possible for the problem
and comparing theorems incorrectly
3) not enough discussion of the problem itself....
Time to bail, me thinks.
Yes, I understand they are dummy variables. But if the question read:
"Given a sorted 2D X * X array" instead of "Given a sorted 2D N x N array"
I imagine we would consider 'n' or 'N' the number of elements rather than the number of rows.
Also, it's not clear to me how considering O(n) to represent the row count rather than the element count is more helpful - particularly when it's clear that one must touch every element in the matrix.
But I agree - time and energy would be better spent on the problem itself.
A couple of things my solution does not take advantage of is the properties of the table having the same width and height, and that the columns are sorted in addition to the rows. But I couldn't see how to take advantage of this.
@Michael, yes the problem has an NxN.
So someone responding reasonably has two options:
1) use N without any definition, so the reason know he/she means the N defined in the problem
2) or redefine a new letter and not muddle it up with N from the problem definition
NxN means N rows and N columns.
It makes a big difference in using #rows (or columns) instead of number of elements. How about the fact the question was worded that way? Also think of "log" for one example. log wipes out the effect of squaring and pushes any effect into the bigO hidden constant, and this information is best brought to light by working with N=width.
For another, we are working with a square matrix, so do you think it's good enough to simple state theorems that were "stated" for linear arrays?
See:
For the problem itself, we have global upper and lower bounds on any optimal solution in terms of time complexity:
1) Upperbound O(N^2 lgN) <--- Because the original poster's mergesort does this
2) Lowerbound Omega(N^2) <-- Gotta touch them all. In fact, it can't be C <1 constant within the O either
It is. If naive sorting is done (by converting 2D array to 1D array), complexity is MlogM (M = N^2). In K-way merge, complexity is MlogN (since heap only contains N elements at any time).
Side note: K-way merge sort is also used to sort extremely long arrays which cannot fit in memory - called as external merge sort.
This solution does not use all the conditions provided in the problem. For this solution to be viable, either being row-wise sorted or being column-wise sorted is enough.
Can be done in N^2. Idea is same as yours - k way merge, but uses the col sorting as well. See my soln at the bottom of the page.
github.com/vikhyath/c-runs/tree/master/n-way-merge
/*
Program to do to n-way merge, where n is the SIZE of n*n array
Emulating n-way merge from file through arrays, where each array row corresponds to a sorted file
Running time: O(n^2 logn), will be O(n^3) if min heap is not used
1) Get sizeof(min-heap) elements from n*n array
2) Put in min heap, remove the root element O(log n)
3) Fill min heap with a new element from array O(#elements) = O(n^2)
4) Do steps 2-3 till n*n array is exhausted
5) Now remove the root from min heap as many times as there are elements left in heap
*/
I dont think we can do better than O(n^2). The total number of elements in the matrix is n*n and we have to visit them at least once.
It seemed Collection Algorithm could be applicable theoretically, but using this method became more complicated in my case as there were also many internal calculation to be reordered and mapped, so firstly implemented by a general merge method with the results in Java. I only skipped minimum numbers. Can anyone try this by more efficient way of collection algorithm??
Making strategy of partial set of collection was not so difficult, but implementation by a stupid computer was not efficient even though I used iterators of Java, there could be more complicated computation than simple general merge algorithm as I failed...
public class ConvertSorted2Dto1D {
final static int givenN = 5;
private static void merge(int[] lArray, int lL, int lH, int[] rArray, int rL, int rH, int[] array, int min) {
int[] arrayL = new int[lH - lL];
int l = 0;
int r = rL;
int i = min;
System.arraycopy(lArray, lL, arrayL, 0, arrayL.length);
// Combine left[] and right[]
while(l < arrayL.length && r < rH) {
if(arrayL[l] > rArray[r]) {
array[i++] = rArray[r++];
} else {
array[i++] = arrayL[l++];
}
}
// Remaining in left[]
while(l < arrayL.length) {
array[i++] = arrayL[l++];
}
// Remaining in right[]
while(r < rH) {
array[i++] = rArray[r++];
}
}
public static void convert2Dto1D(int[][] array2D, int[] array1D) {
if(givenN > 0) {
System.arraycopy(array2D[0], 0, array1D, 0, givenN);
int min = 1;
for(int i = 1; i < givenN; i++) {
for(; min < i*givenN; min++) {
if(array2D[i][0] < array1D[min]) {
break;
}
}
merge(array1D, min, i*givenN, array2D[i], 0, givenN, array1D, min);
}
}
}
public static void main(String[] args) {
int[][] sorted2D = new int[givenN][givenN];
int[] sorted1D = new int[givenN*givenN];
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
sorted2D[i][j] = (int)(Math.random()*9 + i*11 + j*31);
}
}
System.out.println("Before");
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
System.out.print(" " + sorted2D[i][j]);
}
System.out.println();
}
convert2Dto1D(sorted2D, sorted1D);
System.out.println("After");
for(int i = 0; i < givenN * givenN; i++) {
System.out.print(" " + sorted1D[i]);
}
System.out.println();
}
}
Before
2 39 65 101 125
12 42 74 110 142
26 59 88 122 154
40 72 95 133 161
46 81 107 145 173
After
2 12 26 39 40 42 46 59 65 72 74 81 88 95 101 107 110 122 125 133 142 145 154 161 173
The runtime of this approach is O(N^3). The merge sizes are
n+n
2n+n
3n+n
...
n*n+n
Summing up: (1+2+3+..+N)*(N+N) = N*(N+1)/2 * (2N) = O(N^3)
You can do it in O(N^2 log N) using the same method to merge k sorted arrays (a heap). In this question, k = n.
You should know the definition of n in time complexity, n is just total number of elements in the algorithm. The time complexity of Merge Sort is known as O(n log n), so this must be at most O(n log n)... N for the size of matrix in the question, it is differ from big O computation... so this is just like O(n log n)..
I think Merge sort would be good way in the given condition of (array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]).
Implemented in Java with the results.
public class ConvertSorted2Dto1D {
final static int givenN = 5;
private static void merge(int[] lArray, int lLow, int lHi, int[] rArray, int rLo, int rHi, int[] array, int min) {
int[] tempL = new int[lHi - lLow];
int l = 0;
int r = rLo;
int i = min;
System.arraycopy(lArray, lLow, tempL, 0, tempL.length);
// Combine left[] and right[]
while(l < tempL.length && r < rHi) {
if(tempL[l] > rArray[r]) {
array[i++] = rArray[r++];
} else {
array[i++] = tempL[l++];
}
}
// Remaining in left[]
while(l < tempL.length) {
array[i++] = tempL[l++];
}
// Remaining in right[]
while(r < rHi) {
array[i++] = rArray[r++];
}
}
public static void convert2Dto1D(int[][] array2D, int[] array1D) {
for(int i = 1; i < givenN; i++) {
if(i == 1)
merge(array2D[0], 0, givenN, array2D[1], 0, givenN, array1D, 0);
else
merge(array1D, i, i*givenN, array2D[i], 0, givenN, array1D, i);
}
}
public static void main(String[] args) {
int[][] sorted2D = new int[givenN][givenN];
int[] sorted1D = new int[givenN*givenN];
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
sorted2D[i][j] = (int)(Math.random()*9 + i*11 + j*31);
}
}
System.out.println("Before");
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
System.out.print(" " + sorted2D[i][j]);
}
System.out.println();
}
convert2Dto1D(sorted2D, sorted1D);
System.out.println("After");
for(int i = 0; i < givenN * givenN; i++) {
System.out.print(" " + sorted1D[i]);
}
System.out.println();
}
}
Before
5 35 67 100 125
14 49 79 106 139
23 55 89 117 147
40 70 96 130 160
52 79 106 137 175
After
5 14 23 35 40 49 52 55 67 70 79 79 89 96 100 106 106 117 125 130 137 139 147 160 175
one way i could think of is having N iterators for N rows,
Take the min val from N iterators, add to your 1D array..
then Move the Iterator having Min val to Next..
if iterator.hasNext is None.. then remove that iterator from comparing List of N iterators
In this code, I just use the merge part of merge sort to achieve a O(n) time.
public void reduceDimensionality(int[][] array){
int [] odarray = new int[array.length * array[0].length];
int[] pointers = new int[array.length];
int count = 0;
while(count < (array.length * array[0].length)){
int min = 9999999;
int pointer = 0;
for(int k = 0; k < pointers.length; k++){
if( pointers[k] < array[0].length && array[k][pointers[k]] < min){
min = array[k][pointers[k]];
pointer = k;
}
}
odarray[count] = array[pointer][pointers[pointer]];
count++;
pointers[pointer]++;
}
for(int i = 0; i < odarray.length; i++){
System.out.print(odarray[i] + " ");
}
}
In merge sort we have 2 arrays to merge. Here I use the same algorithm to merge n algorithms.
use dynamic programming.
Split N*N array to 4 2D array
A1 A2
B1 B2
all the elements in A1 is smaller than the elements in B2
So we have concatenate A1 and B2 to C
then we need to merge A2 and B1 to C
the time complexity is N^2 * log4 N
The faster solution is merge sort by all rows (or columns) at the same time.
To do this, we need min-heap.
Here is how to *use* MinHeap for sorting. MinHeap does not implemented is this code. You can find the implamantation in google if you need.
template<class T> class MegreSort2d
{
struct Link
{
Link(const T** data, int i, int j)
: i(i), j(j), value(data[i][j]) {}
const int i, j;
const T& value;
};
static void sort(const T** data, T* outData, int n)
{
MinHeap<Link> heap;
current_mins.add(Link(data, 0,0));
for(size_t i=0; i<n*n; ++i)
{
const Link& link = heap.getMinValue();
outData[i]=link.value; //save as sorted
if(link.i<(n-1))
heap.add(Link(data, link.i+1,link.j)); //add next value from this row
if(link.i==0 && link.j<(n-1))
heap.add(Link(data, 0,link.j+1)); //add first value from next row
heap.remove(link);
}
}
};
This was my first idea, re-posted from the other thread:
Treat the matrix has a (quasi) min heap:
LEFT(i, j ) = A[i+1,j] //left child
RIGHT(i, j ) = A[i, j+1] //right child
Note, the matrix is a kind of quasi-min-heap to begin with:
1) A[0,0] - top left - is the minimum of all elements
2) Every node A[i,j] is < LEFT, RIGHT children (as defined above)
So we can create an aux. min. heap,
store (0,0) in there, then:
while( aux.min.heap not empty)
{
x=extractMinAux;
storeInResultArray(x);
insertMinAux( children of x
THAT are not descendents //descendent check is easy O(1)
of elements already in aux.min heap );
}
return result array
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
^^^ One one type of extreme case it should run in N^2 :)
Because the axillary mean heap will never have more than 2 elements.
One the other type of extreme case (you know what it is right?), the auxillary min heap will grow from size 1 to N then back down to 1 (roughly)
So it will be roughly ~ C*N * lg(H(N)) where H(N) is the hyperfactorial function
This should be theta bound N^2 *lg(N)
{But not as TIGHT a bound to N^2(lg(N)) as the merge K sorted list thing idea people are using, because in that idea the min heap is almost always having N elements}
So if someone with time can
1) Try to make this idea work (fill in details)
2) Calculate the "expected" runtime based on a reasonable probability distribution on the valid matrix inputs of size NxN.
Maybe expected is closer to ~C*N^2 (best case) than ~C*N*lg(H(N)) (worst)
and it pops out to be some nonsense like N^2 lg(lg(N)) ?
There is hope because:
1) the "worst" case type of input matrix is not going to happen all the time
{Is seems less likely than the best case type of input above}
2) even in the worst case, the min heap grows to size N and back down (doesn't stay at size N for most of the running of algorithm like the merging N lists alg.).
{ Above is my first idea from other thread. Haven't refined it because the other thread got bogged down. }
priority_queue<int,vector<int>,greater<int>>heap;
int id=(MAXLength*MAXLength)-1;
int index=0;
int *result=new int[id];
memset(result,-1,sizeof(int)*id);
for(i=MAXLength-1;i>=0;i--)
{
for(j=MAXLength-1;j>=0;j--)
heap.push(a[i][j]);
}
while(!heap.empty())
{
result[index++]=heap.top();
// cout<<heap.top()<<" ";
heap.pop();
}
for(i=0;i<index;i++)
cout<<result[i]<<" ";
cout<<endl;
The best algorithm here will use a Min heap as follows.
1. Create a min heap. add array[0][0] to this heap.
2. Now, iteratively do the following:
2.1-> pop the min element in the heap.
2.2-> if element popped was a[i][j], then do the following:
2.2.1 --> if a[i+1][j-1] has already been popped, or if j = 0, you can insert element a[i+1][j] into the heap. do not do this if j = n-1(last column)
2.2.2 --> if a[i-1][j+1] has already been popped, or if i = 0, you can insert element a[i][j+1] into the heap. do not do this if i = n-1(last row).
3. Rinse and repeat step 2 until there are no more elements left to pop.
This algorithm also has a worst case complexity of O(N^2logN), but works much better in the average case.
void Sorted_Matrix_2_Array(int a[MAXLength][MAXLength], vector<int> &result)
{
int i;
priority_queue<int,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>heap;
for(i=0;i<MAXLength;i++)
heap.push(make_pair(a[i][0],make_pair(i,0)));
while(!heap.empty())
{
pair<int,pair<int,int>>p=heap.top();
heap.pop();
result.push_back(p.first);
pair<int,int>q=p.second;
q.second++;
if(q.second < MAXLength)
heap.push(make_pair(a[q.first][q.second],make_pair(q.first,q.second)));
}
}
You could flatten the 2D array down to a 1D array then bubble sort it since it is mostly sorted. With a a mostly sorted list you have a best case O(n) operation.
If you want you can also use Insertion Sort since the 2D array means the array is mostly sorted. That would also give you a best case of O(n)
You can view the lower diagonal part of the matrix as a max heap and the upper diagonal part as min heap. The parent-left-right relationship established by the adjacent cells, i.e. (i,j) is a parent, (i+1, j) is the left child and (i, j+1) the right child. So you just need to do a heapsort with the relation established and it seems you can't really beat O(n^2 log(n)) as otherwise heapsort would sort faster than O(n log(n)) an array of n elements. You'd then have to merge the results of 2 heaps.
mergesort is NMlog(NM)
my answer is
log(N)*NM on worst case
{{import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;
class Converter{
int[][] array;
class Point implements Comparable{
int r,c;
Point(int r, int c){
this.r = r;
this.c = c;
}
int get(){
return array[r][c];
}
int compaireTo(Point b){
return new Integer(get()).compareTo(b.get());
}
@Override
public int compareTo(Object b) {
// TODO Auto-generated method stub
Point pb = (Point) b;
return new Integer(get()).compareTo(pb.get());
}
}
int[] convert2Dto1D(int[][] array){
this.array = array;
TreeSet<Point> candidates = new TreeSet<Point>();
int L = array.length * array[0].length;
int[] answer = new int[L];
candidates.add(new Point(1, 0));
candidates.add(new Point(0, 1));
answer[0] = array[0][0];
for(int i = 1; i < L; i++){
Point p = candidates.pollFirst();
if(p == null){
continue;
}
answer[i] = p.get();
if(p.r + 1 < array.length){
candidates.add(new Point(p.r + 1, p.c));
}
if(p.c + 1 < array[0].length){
candidates.add(new Point(p.r, p.c + 1));
}
}
return answer;
}
public static void main(String[] argv){
int[][] array = {{0, 1, 5}, {2, 4, 6}, {3, 7, 8}};
Converter c = new Converter();
System.out.println(Arrays.toString(c.convert2Dto1D(array)));
}
}
}}
Time complexity for the following algorithm is N^2*lg(PriorityQueue.size). It is similar to the general k-way merge. But it only puts an item into the priority queue if there are no items adjacent to it from left or up. Since PriorityQueue.size is less than or equal to N, this algorithm is faster than the general k-way merge.
import heapq
def convert_2D_to_1D(aa, n):
a = [None] * (n * n)
idx = 0
pq = []
visits = {}
heapq.heappush(pq, (aa[0][0], (0, 0)))
while len(pq) > 0:
# print("priority queue size: ", len(pq))
top = heapq.heappop(pq)[1]
x = top[0]
y = top[1]
a[idx] = aa[x][y]
idx += 1
if x < n - 1:
item = (x + 1, y)
if y == 0:
heapq.heappush(pq, (aa[x + 1][y], item))
elif item in visits:
heapq.heappush(pq, (aa[x + 1][y], item))
del visits[item]
else:
visits[item] = True
if y < n - 1:
item = (x, y + 1)
if x == 0:
heapq.heappush(pq, (aa[x][y + 1], item))
elif item in visits:
heapq.heappush(pq, (aa[x][y + 1], item))
del visits[item]
else:
visits[item] = True
return a
# 4 * 4 2D array
n = 4
aa = [
[1, 2, 4, 6],
[2, 4, 5, 8],
[4, 6, 12, 13],
[8, 10, 18, 19]
]
print(aa)
print(convert_2D_to_1D(aa, n))
# 10 * 10 2D array
n = 10
aa = [[j for j in xrange(n)] for i in xrange(n)]
for i in xrange(n):
for j in xrange(n):
aa[i][j] += i
print(aa)
print(convert_2D_to_1D(aa, n))
You dont actually need a heap - can do in O(N^2). Idea is very similar to k-way merge on rows, but uses additional property that cols are sorted as well.
First merge row 0, col 0
Then move to [1][1], merge row 1, col1
Then move to [2][2], merge row 2, col2
O(N^2).
Pseudo code:
int onedarr[] = new int[N*N];
int ctr = 0;
for(int step = 0; step < N; ++step)
{
int rowIndex = step;
int colIndex = step;
onedarr[++ctr] = arr[rowIndex][colIndex];
for(int i = step+1; i < N; ++i)
{
if(rowIndex == N-1 || arr[i][colIndex] < arr[rowIndex][i])
{
onedarr[++ctr] = arr[i][colIndex++];
}
else
{
onedarr[++ctr] = arr[rowIndex++][i];
}
}
}
Hi guys,
Here's my take on the exercise in Scala. It seems to me it has O(M * N * lg N) complexity. Although I'm having a hard time justifying it in the lg N part. Maybe you can give me a hand!
At any given point in the algorithm, the number of elements in the priority queue is <= N. The number of comparisons we do between elements is at most lg N. Will there ever be repeated comparisons to make the lg N actually be lg N^2?
object KWayMerge {
case class Entry[T <% Ordered[T]](value: T, array: Int) extends Ordered[Entry[T]] {
override def compare(that: Entry[T]) = {
-value.compare(that.value)
}
}
def treat[T <% Ordered[T]](entry: Entry[T], indexes: Array[Int], chunks: Array[Array[T]], result: Queue[T], pq: PriorityQueue[Entry[T]]) = {
val value = entry.value
val arrayN = entry.array
val array = chunks(arrayN)
indexes(arrayN) = indexes(arrayN) + 1
if (indexes(arrayN) < array.length) {
pq += Entry(chunks(arrayN)(indexes(arrayN)), arrayN)
}
result.enqueue(value)
}
def kWayMerge[T <% Ordered[T]](chunks: Array[Array[T]]): Iterable[T] = {
val result = new Queue[T]()
val indexes = new Array[Int](chunks.length)
for (i <- 0 until indexes.length) {
indexes(i) = 0
}
val pq = new PriorityQueue[Entry[T]]()
for (i <- 0 until chunks.length) {
val currIndex = indexes(i)
val arr = chunks(i)
val current = arr(currIndex)
pq += Entry[T](current, i)
}
while (!pq.isEmpty) {
val min = pq.dequeue()
treat(min, indexes, chunks, result, pq)
}
result
}}
On a 3x3 array (n=9), this solution does 27 comparisons if I'm not missing something.
Anyway, I believe this should be O(n x sqrt(n)) complexity.
public static int[] convert2DArrayto1DArray(int[][] array) {
if (array == null)
return null;
// example inputs:
// [1,4,7] [1,2,3]
// [2,5,8] [4,5,6]
// [3,6,9] [7,8,9]
// desired output:
// [1,2,3,4,5,6,7,8,9]
// allocate the target array
int[] target = new int[array.length * array.length]; // NxN
// merge the sorted arrays
int[] currentIndexes = new int[array.length];
for (int i = 0; i < target.length ; i++) {
// which array has our next value?
int arrayWithValue = 0;
int minValue = Integer.MAX_VALUE;
for (int j = 0; j < currentIndexes.length; j++) {
// have we reached the end of this array already?
if (currentIndexes[j] > array.length - 1)
continue;
// possible next value from this array?
if (array[j][currentIndexes[j]] < minValue) {
minValue = array[j][currentIndexes[j]];
arrayWithValue = j;
}
}
target[i] = minValue;
currentIndexes[arrayWithValue]++;
}
return target;
}
public static void test() {
int[][] arrays = {
{1,4,7},
{2,5,8},
{3,6,9}};
int[] array = Util.convert2DArrayto1DArray(arrays);
for (int value : array)
System.out.print(value + " ");
}
// output:
// 1 2 3 4 5 6 7 8 9
Cool, it seems you found the closed solution!!!
I was going to try like this, but it gave me pain to find the answer in a short time, so I tried the general merge method first...
for (int i = 0; i < target.length ; i++)
Here target contains N*N elements and ignoring the inner for loop, this iteration itself is O(N^2).
Isn't this a O(N^3) solution?
I tried doing same yesterday, keeping i (index in target 1-D array) fixed and finding the candidates for index i. There are over N candidates for a position.
For position (0) there are 0 candidates, (0,0) is the smallest.
For position (1) there are N candidates, N-1 candidates in column1 and 1 candidate at (o,1).
For position (2) there are 2N-2 candidates, elements in column0 and column1 excluding those that have been picked for 0th and 1st index.
I tried various approaches but I couldn't do better than O(N^2logN) and I think that's the best we can do. Atleast I am not able to think of any method that gives next element in target 1-D array in O(1) time and every element needs to be scanned atleast once O(N^2).
Please let me know, if I am missing something.
I'm not trying to trick anyone, really :)
If you have a table, for instance, of 10 rows and and 10 columns (NxN) and you are asked to sort the entire table into a single array, you have 100 elements to deal with - not 10. n=100 for big O analysis. If your table was 5 rows and 20 columns, you would also have an n=100 situation - not n=5, not n=20. The N in NxN is not the number of elements - it's the height and width of the matrix.. n, on the other hand, is the number of elements your algorithm is dealing with. That's how I see it :)
If we are taking N to mean the number of total elements, let's call the dimensions X so N = X*X.
This can be beaten by using a heap to store the current set of minimum elements per array (rather than searching for the minimum each step which costs X steps). Removing minimum from heap costs log X, inserting next value costs log X.
So total complexity is O(N log(sqrt(N))
shinsetsu,
You cannot do this in an effort to justify use of N=num elements: => "So total complexity is O(N log(sqrt(N)))"
Because, log(sqrt(N)) = log(N) inside big O/theta
log wipes out any polynomial.
Even for a 1D array mergesort we can say merge sort's runtime is T(N) = O(N log(any_polynomial(N))) and we would be correct, but we lose precision.
We have to work with the "X" from your post directly.
I got the solution in O(n). Do verify and reply
import java.io.*;
import java.util.Scanner;
class arraysort2d
{
public int n;
public int irows, jrows,icols,jcols;
public static void main(String args[])
{
arraysort2d obj = new arraysort2d();
obj.input_array();
}
public int get_input()
{
Scanner input = new Scanner(System.in);
String answer = input.nextLine();
return(Integer.parseInt(answer));
}
public void input_array()
{
int i,j,count = 0, rval = 0;
System.out.println("Input the value of N ");
n = get_input();
System.out.println(" Value of N " + n);
int arr[][] = new int [n][n];
int array1d[] = new int[n*n];
System.out.println("Input the array ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
arr[i][j] = get_input();
}
}
System.out.println(" The array is ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
System.out.print(" " + arr[i][j]) ;
}
System.out.print("\n");
}
// ------------ Computation starts-----------------------
irows = 0;
jrows = 1;
icols = 1;
jcols = 0;
array1d[rval++] = arr[0][0];
while(++count < n * n)
{
if (arr[irows][jrows] < arr[icols][jcols])
{
array1d[rval++] = arr[irows][jrows];
if(jrows == n-1)
{
if(icols == n-1)
jrows = n-1;
else
jrows = 1;
irows += 1;
}
else
jrows ++;
}
else
{
array1d[rval++] = arr[icols][jcols];
if(icols == n-1)
{
if(jrows == n-1)
icols = n-1;
else
icols = 1;
jcols +=1;
}
else
icols ++;
}
}
System.out.print(" " + count + " " + rval + "\n");
array1d[--rval] = arr[n-1][n-1];
//---------- Computation ends -------------
for ( i = 0; i < n*n; i ++)
{
System.out.print(" " + array1d[i]);
}
}
}
I got the solution in O(n). Do verify and reply
import java.io.*;
import java.util.Scanner;
class arraysort2d
{
public int n;
public int irows, jrows,icols,jcols;
public static void main(String args[])
{
arraysort2d obj = new arraysort2d();
obj.input_array();
}
public int get_input()
{
Scanner input = new Scanner(System.in);
String answer = input.nextLine();
return(Integer.parseInt(answer));
}
public void input_array()
{
int i,j,count = 0, rval = 0;
System.out.println("Input the value of N ");
n = get_input();
System.out.println(" Value of N " + n);
int arr[][] = new int [n][n];
int array1d[] = new int[n*n];
System.out.println("Input the array ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
arr[i][j] = get_input();
}
}
System.out.println(" The array is ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
System.out.print(" " + arr[i][j]) ;
}
System.out.print("\n");
}
// ------------ Computation starts-----------------------
irows = 0;
jrows = 1;
icols = 1;
jcols = 0;
array1d[rval++] = arr[0][0];
while(++count < n * n)
{
if (arr[irows][jrows] < arr[icols][jcols])
{
array1d[rval++] = arr[irows][jrows];
if(jrows == n-1)
{
if(icols == n-1)
jrows = n-1;
else
jrows = 1;
irows += 1;
}
else
jrows ++;
}
else
{
array1d[rval++] = arr[icols][jcols];
if(icols == n-1)
{
if(jrows == n-1)
icols = n-1;
else
icols = 1;
jcols +=1;
}
else
icols ++;
}
}
System.out.print(" " + count + " " + rval + "\n");
array1d[--rval] = arr[n-1][n-1];
//---------- Computation ends -------------
for ( i = 0; i < n*n; i ++)
{
System.out.print(" " + array1d[i]);
}
}
}
So it seems no better solution than simply converting to 2D and then sorting it? Since all are N^2*lg(N) ?
Since the original input is already sorted we may use this and avoid re-sorting thus providing N^2 complexity
What about the following recursive algorithm? It looks a bit complex and it's readability could be improved though :)
public class Array2Dto1D {
public static int[] convert(int[][] array2D) {
int[] columnIndex = new int[array2D.length];
int[] output = new int[array2D.length * array2D[0].length];
convertInternal(array2D, columnIndex, 0, output, 0, Integer.MAX_VALUE);
return output;
}
private static int convertInternal(int[][] array2D, int[] rowIndex, int column, int[] array1D, int array1Dindex, int limit) {
if (column >= array2D.length) return array1Dindex;
int array1DNextIndex = array1Dindex;
for (int row = rowIndex[column]; row < array2D[column].length; row++) {
int value = array2D[column][row];
// try the next column if it exists and if it's next value is less than the next value of the current column
boolean tryNextColumn = column < array2D.length - 1 && value > array2D[column + 1][rowIndex[column + 1]];
if (tryNextColumn) {
array1DNextIndex = convertInternal(array2D, rowIndex, column + 1, array1D, array1DNextIndex, value);
}
// cannot process remaining elements in the column until elements in previous columns are not processed
if (value > limit) return array1DNextIndex;
rowIndex[column] = row + 1;
array1D[array1DNextIndex++] = value;
}
return convertInternal(array2D, rowIndex, column + 1, array1D, array1DNextIndex, Integer.MAX_VALUE);
}
public static void main(String[] args) {
int[][] A = new int[][]{
{1, 2, 3, 300, 301},
{100, 101, 102, 400, 401},
{200, 500, 501, 502, 503},
};
int[] output = convert(A);
int[] expected = {1, 2, 3, 100, 101, 102, 200, 300, 301, 400, 401, 500, 501, 502, 503};
compare(output, expected);
A = new int[][]{{1}};
output = convert(A);
expected = new int[]{1};
compare(output, expected);
}
private static void compare(int[] output, int[] expected) {
System.out.println(Arrays.toString(output));
System.out.println("As expected: " + Arrays.equals(expected, output));
}
}
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class MatrixToOneDim {
class Indices {
int i;
int j;
public Indices(int i, int j) {
// TODO Auto-generated constructor stub
this.i = i;
this.j = j;
}
@Override
public boolean equals(Object arg0) {
// TODO Auto-generated method stub
if(! (arg0 instanceof Indices)) {
return false;
}
Indices point = (Indices)arg0;
return this.i == point.i && this.j == point.j;
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return Integer.parseInt("" + this.i + this.j + "");
}
}
int output[];
int count;
int arr[][];
int n;
public MatrixToOneDim (int arr[][], int n) {
this.arr = arr;
this.n = n;
this.count = 0;
this.output = new int[n*n];
}
public void convert() {
output[count++] = arr[0][0];
Map<Indices, Boolean> threePoints = new HashMap<Indices, Boolean>();
threePoints.put(new Indices(1, 0), true);
threePoints.put(new Indices(0, 1), true);
this.convertRecur(threePoints);
}
public void convertRecur(Map<Indices, Boolean> threePoints) {
if(threePoints.size() == 0) {
return;
}
Indices ind = findMin(threePoints);
threePoints.remove(ind);
output[count++] = arr[ind.i][ind.j];
boolean firstPresent = threePoints.containsKey(new Indices(ind.i+1, ind.j));
boolean secondPresent = threePoints.containsKey(new Indices(ind.i, ind.j+1));
if(ind.i+1 < n && ind.j+1 < n) {
if(! firstPresent && ! secondPresent && threePoints.size() < n - 1) {
threePoints.put(new Indices(ind.i+1, ind.j), true);
threePoints.put(new Indices(ind.i, ind.j+1), true);
} else if(! firstPresent && ! secondPresent) {
threePoints.put(arr[ind.i+1][ind.j] < arr[ind.i][ind.j+1] ? new Indices(ind.i+1, ind.j) : new Indices(ind.i, ind.j+1), true);
} else {
if(firstPresent)
threePoints.put(new Indices(ind.i, ind.j+1), true);
else {
threePoints.put(new Indices(ind.i+1, ind.j), true);
}
}
} else if(ind.i+1 < n && !firstPresent) {
threePoints.put(new Indices(ind.i+1, ind.j), true);
} else if(ind.j+1 < n && !secondPresent) {
threePoints.put(new Indices(ind.i, ind.j+1), true);
}
convertRecur(threePoints);
}
private Indices findMin(Map<Indices, Boolean> threePoints) {
int min = Integer.MAX_VALUE;
Indices indMin = null;
for(Entry<Indices, Boolean> entry : threePoints.entrySet()) {
Indices ind = entry.getKey();
if(min > arr[ind.i][ind.j]) {
min = arr[ind.i][ind.j];
indMin = ind;
}
}
return indMin;
}
public static void main(String[] args) {
int arr[][] = {{2, 39, 65, 101, 125},
{12, 42, 74, 110, 142},
{26, 59, 88, 122, 154},
{40, 72, 95, 133, 161},
{46, 81, 107, 145, 173}}; //{{1, 3, 6, 10, 15}, {2, 5, 9, 14, 19}, {4, 8, 13, 18, 22}, {7, 12, 17, 21, 24}, {11, 16, 20, 23, 25}};
MatrixToOneDim mat = new MatrixToOneDim(arr, 5);
mat.convert();
for (int i = 0; i < mat.output.length; i++) {
System.err.print(mat.output[i] + " ");
}
}
}
I was just thinking of an approach which is O(n)
just consider an array like
a[][]=
1 2 3
4 5 6
7 8 9
now we start with 1 i.e. a[0][0] our result array contains {1}, now we compare it with a[0][1] and a[1][0] i.e. we compare it with 2 and 4 and we select minimum of them i.e. a[0][1] which is 2, so now our result array is {1,2} now we take index a[0][1] and compare it with a[1][1] and a[0][2] where we find a[0][2] is minimum and hence select it, so now result array is {1,2,3} now we go to a[0][2] and because we are at last column we compare it with a[1][2] and a[1][0] which would get us 4, so now result array would be {1,2,3,4} and so on. one condition we need to make sure is of visited which would come in last column, in which we would compare elements with current element and check if compared ones are less than current element or not..if it is ignore that element
coding it won't be that difficult and complexity is O(n) as each element is accessed only once. (i will try coding in sometime)
Can you please let me know why it is down voted?.. I would like to know the reason why this solution won't work
The updates on the right show this activity:
ender said Hi Urik, yes, I have rephrased some sentences to make ...
ender up-voted EOF's comment: Since the matrix has ...
ender up-voted URIK LAGNES's comment: 1) O(N ...
ender, your original post with strong opinions and N^2 code has disappeared, now the replies are just floating...
We can use tree map for the same, since tree map use BST for sorting the elements and on the top of that red black tree balancing act.
Hence it will be done maximum in O(logN), please find the code below.
import java.util.*;
public class SortTwoDArray {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[][] twoDArray={{1,13,45,23,56},{12,14,16,122,343},{18,100,105,178,156},{3,5,6,7,8},{0,99,205,232,1211}};
sortTwoDArray(twoDArray);
}
private static void sortTwoDArray(Integer[][] twoDArray) {
Set<Integer> sortedSet=new TreeSet<Integer>();
for(Integer[] outerArray : twoDArray){
for(Integer element : outerArray)
{
sortedSet.add(element);
}
}
System.out.print("SortedArray : ");
for(Integer element : sortedSet)
{
System.out.print(element+" ");
}
}
}
Aren't you performing a O(log N) operation N times? I would think this solution is O(N log N)
I got the solution in O(n). Do verify and let me know
import java.io.*;
import java.util.Scanner;
class arraysort2d
{
public int n;
public int irows, jrows,icols,jcols;
public static void main(String args[])
{
arraysort2d obj = new arraysort2d();
obj.input_array();
}
public int get_input()
{
Scanner input = new Scanner(System.in);
String answer = input.nextLine();
return(Integer.parseInt(answer));
}
public void input_array()
{
int i,j,count = 0, rval = 0;
System.out.println("Input the value of N ");
n = get_input();
System.out.println(" Value of N " + n);
int arr[][] = new int [n][n];
int array1d[] = new int[n*n];
System.out.println("Input the array ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
arr[i][j] = get_input();
}
}
System.out.println(" The array is ");
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
System.out.print(" " + arr[i][j]) ;
}
System.out.print("\n");
}
// ------------ Computation starts-----------------------
irows = 0;
jrows = 1;
icols = 1;
jcols = 0;
array1d[rval++] = arr[0][0];
while(++count < n * n)
{
if (arr[irows][jrows] < arr[icols][jcols])
{
array1d[rval++] = arr[irows][jrows];
if(jrows == n-1)
{
if(icols == n-1)
jrows = n-1;
else
jrows = 1;
irows += 1;
}
else
jrows ++;
}
else
{
array1d[rval++] = arr[icols][jcols];
if(icols == n-1)
{
if(jrows == n-1)
icols = n-1;
else
icols = 1;
jcols +=1;
}
else
icols ++;
}
}
System.out.print(" " + count + " " + rval + "\n");
array1d[--rval] = arr[n-1][n-1];
//---------- Computation ends -------------
for ( i = 0; i < n*n; i ++)
{
System.out.print(" " + array1d[i]);
}
}
}
There is no solution faster that O(n^2 * Log n) where n - is the size of matrix.
Check you solution on something like this:
a a a a b
a a a b c
a a b c c
a b c c c
b c c c c
Where
a - different values in range (x1, x2)
b - different values in range (x2+1, x3 - 1)
c - different values in range (x3, x4)
I mean, all values upper diagonal is less than diagonal. And all values then down than diagonal - is more than diagonal.
struct item {
int ele;
int i;
int j;
item(int ele_, int i_, int j_) { i = i_ ; j = j_ ; ele = ele_ ; }
// for min heap in c++, u need to right this comparator
bool operator<(const item& other)
{
return ele > other.ele;
}
};
vector<int> convert(const vector< vector<int> >& a, int n)
{
assert(a.size() == n && a[0].size() == n);
priority_queue<item> pq;
vector< vector<bool> > visit(n, vector<bool>(n, false));
vector<int> ans;
int i(0), j(0);
if (n > 0) pq.push( item(a[i][j], i, j) );
while (!pq.empty())
{
item it = pq.top(); pq.pop();
ans.push_back(it.ele);
if (it.i + 1 < n && !visit[it.i+1][it.j]) {
ans.push( item(a[it.i+1][it.j], it.i+1, it.j) );
visit[it.i+1][it.j] = true;
}
if (it.j + 1 < n && !visit[it.i][it.j+1] ) {
ans.push( item(a[it.i][it.j+1], it.i. it.j+1) );
visit[it.i][it.j+1] = true;
}
}
return ans;
}
1) O(N*N) worst case for any solution? Huh? You mean OMEGA(N*N) ?
2) Merge sort which runs in O(N* Log N)
-> In this problem N is a dimension of the square matrix. So M.Sort is O(N^2 lgN)
3) With this approach, the space efficiency is O(1) and the time efficiency is O(1/4 * N*N).
-> What does this mean? What is the "1/4" for? You break the square matrix up into 4 element blocks (with two outer for loops). But then you have inner for loops to work on each for 4 elements per block. You aren't magically touching only 1/4 the elements.
4) Have you tested this? How could this possibly work? Looks like you'd have to sort "sorted_array" at the end for it to be really sorted (correct me if I'm wrong).
For the problem itself, we have global upper and lower bounds on any optimal solution in terms of time complexity:
1) Upperbound O(N^2 lgN) <--- Because the original poster's mergesort does this
2) Lowerbound Omega(N^2) <-- Gotta touch them all. In fact, it can't be C <1 constant within the O either.
Since the matrix has O(n*n) elements thus the merge sort will take O(n^2 log n^2) = O(2*n^2 log n) time. Though it is true that O(n*n) is the asymptotic lower bound, but I doubt if the problem can be solved in O(n*n) time unless some special cases or some restrictions on input are given.
@EOF
True. I can see a solution that might be N^2 with high probability (or avg. case N^2 maybe, or at the very least N^2 best case) but can't think of an N^2 worst case.
The matrix is already (from top left) in a min-heap form (but with a stronger rep. invariant property, with subtrees overlapping unlike a usual min-heap).
We can create a separate min-heap, put the (0,0) element then loop on max_extract's and inserting children of everything we extracted (but we can also use the extra overlapping properly to exclude certain children from needing to be inserted into the min. heap).
The size of the aux. min. heap is "usually" rather small on the average case (and in the best case it should be small and independent of N, making the whole alg. N^2 in best case).
Children of a node in the matrix would be defined as:
LEFT(i, j ) = A[i+1,j]
RIGHT(i, j ) = A[i, j+1]
Node, the matrix is a kind of quasi-min-heap to begin with:
1) A[0,0] - top left - is the minimum of all elements
2) Every node A[i,j] is < LEFT, RIGHT children (as defined above)
So we can create an aux. min. heap,
store (0,0) in there, then:
while( aux.min.heap not empty)
{
x=extractMinAux;
storeInResultArray(x);
insertMinAux( children of x THAT are not descendents of elements already in aux.min heap <--- this bit is special for this quasi min heap );
}
return result array
I think this is the most suitable scenario for K-Way merge. K represents the number of sorted one dimensional arrays.
- Ajeet October 19, 2013Because it is NxN array, and it is row wise and column wise sorted.
Here number of sorted arrays = number of row (or we can use columns)= N
So here K will be equal to N.
Here is algorithm:
Put the minimum element of each array (each row will be treated as a array) into a min-heap.
Then, repeatedly extract the minimum element from the heap, and replacing it by inserting the next
element from the same array.
The heap will never be bigger than N elements, so each operation (either extract-min or
insert) takes O(lg N) time.
There are O(n) operations (one insert and one extract-min
for each element), so the running time is
O(MlogN): where M = total number of elements = N^2.
Reference: CLRS (2nd Ed) problem 6.5-8