Stack with Find-Min/Find-Max More Efficient Than O(N)

Improving finding Min and Max in Array

No. It is impossible to find both maximum and minimum value in exactly n(or n+a) comparisons. It will need at least 3n/2 - 2 comparisons. See this proof and this proof. Maybe you can show these proofs to your teacher...

Are there any other hints about the sequence? Like it's uniformly distributed or such?

Faster way to find min and max values in array

For unosorted data, looping over the array to find min/max takes O(n) time. For sorted it would have been constant time (O(1)) but as I understand it, this is not your case.

Fastest sorting algorithms work in O(n*log(n)), so linear scan (loop) is the fastest option there is.

Also, this is not the case when compiler could optimize something for you.

design a stack such that getMinimum( ) should be O(1)

EDIT: This fails the "constant space" constraint - it basically doubles the space required. I very much doubt that there's a solution which doesn't do that though, without wrecking the runtime complexity somewhere (e.g. making push/pop O(n)). Note that this doesn't change the complexity of the space required, e.g. if you've got a stack with O(n) space requirements, this will still be O(n) just with a different constant factor.

Non-constant-space solution

Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().

So using your example, we'd have:

Real stack        Min stack

5  --> TOP        1
1                 1
4                 2
6                 2
2                 2

After popping twice you get:

Real stack        Min stack

4                 2
6                 2
2                 2

Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)

EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:

Real stack        Min stack

1  --> TOP        1
5                 1
1                 2
4                 
6                 
2                 

Popping from the above pops from both stacks because 1 == 1, leaving:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

Popping again only pops from the main stack, because 5 > 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

Popping again pops both stacks because 1 == 1:

Real stack        Min stack

4                 2
6                 
2                 

This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".

EDIT: Here's an implementation of Pete's evil scheme. I haven't tested it thoroughly, but I think it's okay :)

using System.Collections.Generic;

public class FastMinStack<T>
{
    private readonly Stack<T> stack = new Stack<T>();
    // Could pass this in to the constructor
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    private T currentMin;

    public T Minimum
    {
        get { return currentMin; }
    }

    public void Push(T element)
    {
        if (stack.Count == 0 ||
            comparer.Compare(element, currentMin) <= 0)
        {
            stack.Push(currentMin);
            stack.Push(element);
            currentMin = element;
        }
        else
        {
            stack.Push(element);
        }
    }

    public T Pop()
    {
        T ret = stack.Pop();
        if (comparer.Compare(ret, currentMin) == 0)
        {
            currentMin = stack.Pop();
        }
        return ret;
    }
}

Generalizing the find-min/find-max stack to arbitrary order statistics?

Since the structure can be used to sort k elements with O(k) push and find-kth operations, every comparison-based implementation has at least one of these cost Omega(log k), even in an amortized sense, with randomization.

Push can be O(log k) and pop/find-kth can be O(1) (use persistent data structures; push should precompute the order statistic). My gut feeling based on working with lower bounds for comparison-based algorithms is that O(1) push/pop and O(log k) find-kth is doable but requires amortization.

How to Find the Max Integer Value in a Stack without using max() or iterating over it?

Edit:

without iterating over the Stack

does not actually prohibit all iteration. Rather, the question only prohibits doing the simple

for (Integer i : lifo)

Thus, this solution satisfies the question's limitations.

---

Just empty a copy of the stack. pop each of the elements from the copy, checking for max against an integer all the while.

Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;

while (!lifoCopy.isEmpty())
{
    max = Math.max(lifoCopy.pop(), max);
}

System.out.println("max=" + max.toString());

This will work for you in O(n) time even if your interviewers decide to be more restrictive and not allow more built in functions (max, min, sort, etc.).

Additionally, if you need to have the original unharmed, but can't use clone, you can do so with an extra stack:

Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;

while (!lifo.isEmpty())
{
    int val = lifo.pop();

    max = Math.max(val, max);

    reverseLifo.push(val);
}

while (!reverseLifo.isEmpty())
{
    lifo.push(reverseLifo.pop());
}

System.out.println("max=" + max.toString());

Finally, this assumes that comparison against a temp variable is acceptable. If no comparison is allowed at all, then this solution in conjunction with this method will work.

What is the best way to get the minimum or maximum value from an Array of numbers?

The theoretical answers from everyone else are all neat, but let's be pragmatic. ActionScript provides the tools you need so that you don't even have to write a loop in this case!

First, note that Math.min() and Math.max() can take any number of arguments. Also, it's important to understand the apply() method available to Function objects. It allows you to pass arguments to the function using an Array. Let's take advantage of both:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

Here's the best part: the "loop" is actually run using native code (inside Flash Player), so it's faster than searching for the minimum or maximum value using a pure ActionScript loop.

---

Related Topics