Re: [algogeeks] Re: Find the number of islands/connected components
got the islands...but first we scan each element then also dfs for them if
all are 1..then how it can be o(row*col)...plz explain me complexity ofr
this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand wrote:
> {*1*,* 1*, 0, 0, 0},
> {0, *1*, 0, 0, *1*
> },
> {*1*, 0, 0, *1*, *1*},
> {0, 0, 0, 0, 0},
> {*1*, 0, *1*, 0, *1*}
>
> above different set of color represent different island.Simple DFS is used to
> find all the island
>
>
>
> On Fri, Apr 26, 2013 at 3:11 AM, Don wrote:
>
>> The complexity is still O(ROWS*COLS) because each location in the
>> matrix will be visited once by the loop and once by DFS. Once a
>> location has been visited by DFS, it is marked as visited and can't be
>> visited again.
>> Don
>>
>> On Apr 25, 5:11 pm, rahul sharma wrote:
>> > What will be complexity if all elements in matrix are 1..
>> >
>> > when first dfs will call then all matrix will be scanned setting each
>> > element to visited...
>> > then again loop contiues to scan all the elements..plz explain
>> >
>> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma > >wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > {*1*,* 1*, 0, 0, 0},
>> > > {0, *1*, 0, 0, *1*},
>> > > {*1*, 0, 0, *1*, *1*},
>> > > {0, 0, 0, 0, 0},
>> > > {*1*, 0, *1*, 0, *1*}
>> >
>> > > Can anybody eplain how there are 5 islands in above matrix..thnx in
>> advance
>> >
>> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is
used to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don wrote:
> The complexity is still O(ROWS*COLS) because each location in the
> matrix will be visited once by the loop and once by DFS. Once a
> location has been visited by DFS, it is marked as visited and can't be
> visited again.
> Don
>
> On Apr 25, 5:11 pm, rahul sharma wrote:
> > What will be complexity if all elements in matrix are 1..
> >
> > when first dfs will call then all matrix will be scanned setting each
> > element to visited...
> > then again loop contiues to scan all the elements..plz explain
> >
> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > {*1*,* 1*, 0, 0, 0},
> > > {0, *1*, 0, 0, *1*},
> > > {*1*, 0, 0, *1*, *1*},
> > > {0, 0, 0, 0, 0},
> > > {*1*, 0, *1*, 0, *1*}
> >
> > > Can anybody eplain how there are 5 islands in above matrix..thnx in
> advance
> >
> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
islands are five as for each cell we assume all surrounding positions to be
connected... so if coordinates are (x,y) then it is connected to (x+1, y),
(x-1, y), (x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1), (x, y-1), (x, y+1)
On Thu, Apr 11, 2013 at 9:35 AM, rahul sharma wrote:
> I didnt get..plz explain more...thnx
>
>
> On Thursday, April 11, 2013, Don wrote:
> > Reformatting to make it easier to see:
> >
> > 11000
> > 01001
> > 10011
> > 0
> > 10101
> >
> > In this case an "island" is any set of "1's" which are connected
> > vertically, horizontally, or diagonally.
> > So the five islands are
> >
> > 11000
> > 01002
> > 10022
> > 0
> > 30405
> >
> > Don
> >
> > On Apr 10, 4:34 pm, rahul sharma wrote:
> >> {*1*,* 1*, 0, 0, 0},
> >> {0, *1*, 0, 0, *1*},
> >> {*1*, 0, 0, *1*, *1*},
> >> {0, 0, 0, 0, 0},
> >> {*1*, 0, *1*, 0, *1*}
> >>
> >> Can anybody eplain how there are 5 islands in above matrix..thnx in
> advance
> >>
> >> source:-http://www.geeksforgeeks.org/find-number-of-islands/
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: find the number.
@Dave :but it will take more time. any other solution wrote:
> @Naresh: The sequence of numbers generated by this rule for any given
> starting number is called a Collatz Sequence. Try googling it.
>
> Here is a list of the number of iterations required for n between 1
> and 10,000: http://oeis.org/A006577/b006577.txt. Maybe that will help.
>
> Dave
>
> On Dec 11, 7:20 am, Naresh A wrote:
> > Given range of numbers between A and B (A<= B)
> > Find the number within given range which has more number of iterations as
> > per the following
> >
> > n { stop ; return iteration number } if n=1;
> > n = 3n+1 if n is odd
> > n = n/2 if n is even
> >
> > for eg :
> >
> > n=3 odd
> >
> > n=10;
> > n=5;
> > n=16;
> > n=8;
> > n=4;
> > n=2;
> > n=1;
> >
> > iterations : 7
> >
> > --
> > *
> > Time complexity= ( >
> > *
> > *NARESH ,A*
> > **
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Shoban babu.B
M.E.,CSA,
IISc.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
I think hash would be the less space intensive than anything else.
About your example of 1000 elements and big numbers:
Any decent hash function with size 1024 as bucket will give you good results.
Insertion time will be close to O(1)
One such hash would be rotating hash which takes care of all 4 bytes of integer.
unsigned jsw_hash ( void *key, int len )
{
unsigned char *p = key;
unsigned h = 16777551;
int i;
for ( i = 0; i < len; i++ )
h = ( h << 1 | h >> 31 ) ^ tab[p[i]];
return h;
}
Of course, we can find such array whose elements may not get good hash
results and insertion time may increase.
But, for practical purpose and uniform distribution of elements, hash will work.
Let me know your thoughts.
Janak
On Wed, Jun 2, 2010 at 12:03 AM, Veer Sharma wrote:
>
> Hi Janak
>
> Thanks for your reply and good that we are exited. But if you see the
> problem, this approach is already known which has space complexity of
> O(n). But this if you are lucky that the array has numbers which are
> not more than n itself.
>
> If the given array is say 1000 size and it has numbers which can be
> anything, say a very large number 14556543 (lets forget max storage of
> int/long in various programing languages). Then it will be a tough job
> to keep insertion in your hash table O(1). There will be lots of hash
> classes and if you do not chose a good hash function (which can be
> better found by knowing the nature of the numbers in the aray and we
> done know about them) you may end up with O(n) insertion time.
>
> So lets think a less space expensive method.
>
> Tanks,
> Veer
>
> On Jun 1, 9:57 am, janak chandarana wrote:
> > On Mon, May 31, 2010 at 10:01 PM, souravsain wrote:
> > > Hi All
> >
> > > This is my first post to this community and so am exited. The problem
> > > is to find the no. that has maximum frequency in an array (size n) of
> > > integers.
> >
> > > The approach to use a hash table, itereate through array (O(n)) and
> > > keep inserting into hash table (O(1)) and then scan the hash table
> > > (O(n)) to find entry with max frequency is known.
> >
> > You don't need to scan hash table again.
> > Keep track of max while inserting.
> > Update max when ever freq of some character is more than max.
> >
> > > Not to mention that
> > > one more iteration is needed to find the maximum value in array so as
> > > to decide the sixe of hash table (to keep insertion perfectly O(N).
> >
> > > I am looking for a solution which is having O(1) space complexity. The
> > > best I can think of is to sort the array in O(nlogn) and then make a
> > > pass through the array O(n) to find one with max frequency. So here
> > > time complexity is O(nlogn + n). Can we have a better solution?
> >
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
