Okay, I guess this question will be more tough to tackle in complete
generality. in two sorted arrays, lets assume elements are in strictly
increasing order, hence the extra care of duplicates in either array
is gone. However, the same element can be present in both arrays.
For ex.
{1,2,3} {2,3,4}
The duplicate case can obviously be solved, but i am not sure if we
can have O(n) time bound in that case.
On Sep 2, 3:36 am, "icy`" <[email protected]> wrote:
> @Dave thanks for clarifying that (4,3) is different from (3,4)
>
> But let's suppose, for example, n is 3
> so A is of size n, and B is of size n, as required
> e.g. A = [1 1 2] , B = [1 2 2]
>
> S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }
>
> but now you see there are repeated points that are also in the same
> order. These are duplicates and should be removed, if S is truly a
> set. Pruned version:
>
> S = { (1,1) (1,2) (2,1) (2,2) }
>
> size of set is not n^2, or 9, but rather
> (size of unique(A) ) * (size of unique(B) ) = 4
>
> With this in mind, I would first eliminate or ignore duplicates as you
> are iterating through A, B
>
> On Sep 1, 5:50 pm, Dave <[email protected]> wrote:
>
>
>
>
>
>
>
> > @Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
> > (1,2). These are different than the pairs you listed, because they are
> > ordered: the first element is from set A and the second element is
> > from set B. This was masked because of your choice of A = B. But you
> > wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
> > = [5 6 7 8].
>
> > There is no restriction in the original problem statement that the
> > numbers in each array are distinct. One application I have seen of
> > this problem is with the travel reservation web sites, where they will
> > show you some number of the cheapest round trip flight combinations.
> > In that case, there is more to the data items than just the price,
> > including at least airline and flight time. Several different flights
> > might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
> > [1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
> > case, the first 2 (cheapest) round trips will have score 2. Then
> > follows 7 round trips with score 3. Etc.
>
> > Dave
>
> > On Sep 1, 4:12 pm, "icy`" <[email protected]> wrote:
>
> > > actually this makes me think about the question requirements a bit..
> > > in math, arent sets supposed to have *unique* elements?
>
> > > so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
> > > S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
> > > (1,1) } ??
>
> > > since A is equal to B, the size of S is (4 choose 2) plus the four
> > > mirror pairs, so 6+4 = 10
>
> > > and the question implies mathematical sets with that notation, so why
> > > are there necessarily n squared elements in S ...?
>
> > > On Sep 1, 2:01 pm, rajul jain <[email protected]> wrote:
>
> > > > @bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
> > > > (3,3)....
> > > > correct me if am wrong..
>
> > > > On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana <
>
> > > > [email protected]> wrote:
> > > > > @Mac: It gives us the first largest pair but need not all n pairs ..
> > > > > ex:
> > > > > A=1 1 3 4
> > > > > B=1 2 3 4
> > > > > pairs : (4,4),(4,3),(3,3),(2,4) .....
>
> > > > > On Thu, Sep 1, 2011 at 4:57 AM, MAC <[email protected]> wrote:
>
> > > > >> since its sorted , cant we just take last (largest if assedning)
> > > > >> elements
> > > > >> of each and return o(1) .. (since +ve we can do so i guess)
>
> > > > >> On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
> > > > >> <[email protected]>wrote:
>
> > > > >>> Given two sorted positive integer arrays A(n) and B(n), we define a
> > > > >>> set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
> > > > >>> in S. The value of such a pair is defined as Val(a,b) = a + b. Now
> > > > >>> we
> > > > >>> want to get the n pairs from S with largest values. need an O(n)
> > > > >>> algorithm.
>
> > > > >>> --
> > > > >>> Regards,
> > > > >>> Navneet
>
> > > > >>> --
> > > > >>> You received this message because you are subscribed to the Google
> > > > >>> Groups
> > > > >>> "Algorithm Geeks" group.
> > > > >>> To post to this group, send email to [email protected].
> > > > >>> To unsubscribe from this group, send email to
> > > > >>> [email protected].
> > > > >>> For more options, visit this group at
> > > > >>>http://groups.google.com/group/algogeeks?hl=en.
>
> > > > >> --
> > > > >> thanks
> > > > >> --mac
>
> > > > >> --
> > > > >> You received this message because you are subscribed to the Google
> > > > >> Groups
> > > > >> "Algorithm Geeks" group.
> > > > >> To post to this group, send email to [email protected].
> > > > >> To unsubscribe from this group, send email to
> > > > >> [email protected].
> > > > >> For more options, visit this group at
> > > > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > > > --
>
> > > > > **Please do not print this e-mail until urgent requirement. Go Green!!
> > > > > Save Papers <=> Save Trees
> > > > > *BharatKumar Bagana*
> > > > > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
> > > > > *
> > > > > Mobile +91 8056127652*
> > > > > <[email protected]>
>
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to [email protected].
> > > > > To unsubscribe from this group, send email to
> > > > > [email protected].
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text -
>
> > > - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
