gravatar

Blog # 51 : Minimum & Maximum + Stack


Assume you have infinite memory. Design an algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time.

Eg. 5, 9, 2, 35, 23, 1, ...
After 3rd element, the algorithm would tell min = 2, max = 9
After 6th element, algorithm would tell min = 1, max = 35




Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.




Courtesy: Vibhaj

gravatar

stack max , min;
for first two entries a, b.. add greater one to max n smaller to min..
for any entry Ai:
if (A[i]>max)
pop max;
max.push(A[i]);
else if (a[i]<min)
min.push(a[i]);
else proceed to next entry;

gravatar

Using stacks ? Why not just 2 variables having current max & min ?
Or you want to reduce the 2 comparisons for each number ?

gravatar

@Nayan: "Using stacks" is just a constraint