Author |
Topic: Find number in ordered matrix. (Read 3504 times) |
|
Corin
Newbie
Posts: 7
|
 |
Find number in ordered matrix.
« on: Nov 13th, 2007, 6:38pm » |
 Quote  Modify
|
Given an ordered matrix, both the column and row is increasing with index. How to find a number in this matrix?
It's an old problem, I don't see how to get a solution with O(n). Thanks for anybody who knows to have a note here...
|
|
 IP Logged |
|
|
|
dont.hurt.again
Newbie
Posts: 6
|
|
Re: Find number in ordered matrix.
« Reply #1 on: Nov 13th, 2007, 9:48pm » |
Quote Modify
|
start moving from top right corner .
when ever u encounter a bigger no move downwards and if no is smaller move leftside.
either u will get ur no or u will be unable to move further. If u are unable to move then there is no such no in the matrix.
the maximum move a person can make is 2n where matrix is nXn.
|
|
IP Logged |
|
|
|
Corin
Newbie
Posts: 7
|
|
Re: Find number in ordered matrix.
« Reply #2 on: Nov 13th, 2007, 10:27pm » |
Quote Modify
|
Assume you have 4x4 matrix like:
1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12
How to search "8" with your strategy? Thanks.
|
|
IP Logged |
|
|
|
riddle_sea
Newbie
Gender: 
Posts: 13
|
|
Re: Find number in ordered matrix.
« Reply #3 on: Nov 13th, 2007, 10:31pm » |
Quote Modify
|
If i am not mistaken then this kind of matrix is given a special name? Can anyone suggest the name?
|
|
IP Logged |
|
|
|
riddle_sea
Newbie
Gender:
Posts: 13
|
|
Re: Find number in ordered matrix.
« Reply #4 on: Nov 13th, 2007, 10:42pm » |
Quote Modify
|
on Nov 13th, 2007, 10:27pm, Corin wrote:Assume you have 4x4 matrix like:
1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12
How to search "8" with your strategy? Thanks. |
|
we can similarly use the same strategy....
we will move downwards starting from 6 till we reach 9 then as 8 is smaller we move left and meet 7 then we move downward again and encounter 11 and as 8 is smaller we move to the left and meet 8 at the last.....
and yes this matrix's special name is Young's Matrix
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find number in ordered matrix.
« Reply #5 on: Nov 14th, 2007, 5:50am » |
Quote Modify
|
on Nov 13th, 2007, 10:27pm, Corin wrote:Assume you have 4x4 matrix like:
1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12
How to search "8" with your strategy? Thanks. |
|
Start from top right corner, 6.
- 6 is too small, go down to 7
- 7 is too small, go down to 9
- 9 is too large, go left to 7
- 7 is too small, go down to 11
- 11 is too large, go left to 10
- 10 is too large, go left to 8
- 8 ... bingo!
There are maximum 2n-1 tests. It can be more than n, but that is still O(n).
|
| « Last Edit: Nov 14th, 2007, 5:52am by Grimbal » |
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Find number in ordered matrix.
« Reply #6 on: Nov 14th, 2007, 7:37am » |
Quote Modify
|
on Nov 13th, 2007, 10:31pm, riddle_sea wrote:
If i am not mistaken then this kind of matrix is given a special name? Can anyone suggest the name? |
|
As far as I know such a matrix is called a Young's tableau. Btw, I have two more questions on Young's tabeau.
i) Consider a non-full young's tableau(the empty positions are filled with some large number).How will you insert an element inside the matrix?
ii) How will you sort the elements of a completely filled Young's tableau.
|
|
IP Logged |
All signatures are false.
|
|
|
riddle_sea
Newbie
Gender:
Posts: 13
|
|
Re: Find number in ordered matrix.
« Reply #7 on: Nov 14th, 2007, 12:41pm » |
Quote Modify
|
on Nov 14th, 2007, 7:37am, gotit wrote:
As far as I know such a matrix is called a Young's tableau. Btw, I have two more questions on Young's tabeau.
ii) How will you sort the elements of a completely filled Young's tableau.
|
|
we can solve it through heaps...
what we have in hand, we have n sorted arrays and total elements nxn...
make a heap containing the first element of each row (being the minimum of the row) then min-heapify it.. you will get the minimum of all 1st column elements.. put that element into the final array.
Now from the array (row) to which the minimum element belongs take the next column element and insert into heap... now again min-heapify ... again put the smallest into the final array...
continue till you have examined all the elements...
The order is O(n2log n)....
Tell me if i am wrong....
|
|
IP Logged |
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: Find number in ordered matrix.
« Reply #8 on: Nov 15th, 2007, 7:25am » |
Quote Modify
|
Cant we merge 2 rows (or cols) in O(n)??
To merge all the 'n' rows, it will take O(n^2). Isnt that the best we can do?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find number in ordered matrix.
« Reply #9 on: Nov 15th, 2007, 8:20am » |
Quote Modify
|
I believe merging k rows or size n is O(nk log k).
|
|
IP Logged |
|
|
|
aditi
Newbie
Posts: 17
|
|
Re: Find number in ordered matrix.
« Reply #10 on: Nov 15th, 2007, 5:48pm » |
Quote Modify
|
Let us assume that empty slots are indicated by 'infinity'.
1.In a Youngs tableau, the largest element is A[n][n]. Thus if A[n][n] is not infinity, then there are no empty slots and we can exit.
2.Else, i = j =n.
3.Place the element to be inserted in A[i][j].
4.Find m =max(A[i][j], A[i][j-1], A[i-1][j])
5.if(m=A[i][j]) quit.
6.if(m=A[i][j-1]) {swap(A[i][j],A[i][j-1]); j--;}
else {swap(A[i][j], A[i-1][j]); i--;}
7.Repeat steps 3-7 as long as i!=1 or j!=1.
|
|
IP Logged |
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: Find number in ordered matrix.
« Reply #11 on: Nov 16th, 2007, 10:18am » |
Quote Modify
|
on Nov 15th, 2007, 8:20am, Grimbal wrote:| I believe merging k rows or size n is O(nk log k). |
|
Why it will take O(nk log k). Each row is sorted, so we could merge any two sorted rows in O(n), right?
Since there are n rows, we could sort them into an array of n^2 size in O(n^2).
The recursion formula is F(n) = F(n-1) + n; F(1) = n;
Am I right?
|
| « Last Edit: Nov 16th, 2007, 10:20am by bbskill » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find number in ordered matrix.
« Reply #12 on: Nov 16th, 2007, 2:11pm » |
Quote Modify
|
on Nov 16th, 2007, 10:18am, bbskill wrote:| Why it will take O(nk log k). Each row is sorted, so we could merge any two sorted rows in O(n), right? |
|
Let's take 8 rows to start with, as an example
We pair the rows up, and get 4 rows of length 2N in O(8N) time
Then we pair the 4 new rows up again and get 2 rows of 4N in O(8N) time
Then we pair those final two rows up, and merge then in O(8N) time
so in total, O(log(8)*8N).
In general a similar method would give O(n k log(k)).
|
| « Last Edit: Nov 16th, 2007, 2:14pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wanderer
Newbie
Posts: 34
|
|
Re: Find number in ordered matrix.
« Reply #13 on: Nov 26th, 2007, 11:35pm » |
Quote Modify
|
on Nov 13th, 2007, 6:38pm, Corin wrote:Given an ordered matrix, both the column and row is increasing with index. How to find a number in this matrix?
It's an old problem, I don't see how to get a solution with O(n). Thanks for anybody who knows to have a note here... |
|
its an old problem..pardon me for coming back to it..
I know the O(n) solution. But is it possible to solve it in O(log n) time ?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find number in ordered matrix.
« Reply #14 on: Nov 27th, 2007, 1:02am » |
Quote Modify
|
It is not.
In the special case where all items above the reverse diagonal (from top right to bottom left) are smaller than the item you search and all items below it are larger, in that special case the only way to eliminate an item of the diagonal from consideration is to test it directly. So in the worst case, you have to check n items.
|
| « Last Edit: Nov 27th, 2007, 1:02am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print