@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
unfeasible to me.
@Piyush: Are you sure an O(N) algo exists?
Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
algo as it doesn't generate duplicates)
For arrays
A = a1 a2 ... an
B = b1 b2 .... bn
Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
Insert (an, bn).
Repeat N Times {
Pop off and output the max value from the priority queue. Let that be
(ai, bj) // O(log N)
if(i == j) {
Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. //
O(log n)
} else if(i < j) {
Insert (ai-1, bj) in the priority queue. // O(log n)
} else {
Insert (ai, bj-1) in the priority queue. // O(log n)
}
}
Time complexity: O(N log N)
Space complexity: O(N) ??
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XCjyFaTFD-UJ.
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.
