/*
 * Copyright (C) 2014 Pedro Vicente Gómez Sánchez.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.pedrovgs.problem63;

import java.util.Stack;

/**
 * How would you design an integer stack which, in addition to push and pop, also has a function
 * min which returns the minimum element? Push, pop and min should all operate in 0(1) time.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class ConstantComplexityOrderStack {

  /**
   * Approach based on a inner data structure to store the stack of integers and in the same object
   * the current min value we had when the element was pushed. With this approach we get a time
   * complexity order equals to O(1) but a space complexity order equals to O(N) where N is the
   * number of elements in the stack.
   */
  public static class Stack1 extends Stack<MinValue> {

    public void push(int item) {
      int newMin = Math.min(item, getMin());
      super.push(new MinValue(item, newMin));
    }

    public int getMin() {
      if (isEmpty()) {
        return Integer.MAX_VALUE;
      } else {
        return peek().minValue;
      }
    }
  }

  static class MinValue {
    final int value;
    final int minValue;

    MinValue(int value, int minValue) {
      this.value = value;
      this.minValue = minValue;
    }
  }
}

@@ -1813,11 +1813,860 @@
    %7D%0A  %7D
+%0A%0A  /**%0A   * Approach based on keep a parallel data structure with the min elements. Doing this we can%0A   * reduce the number of additional elements stored, but the complexity order is still O(N) in%0A   * space terms for the worst case. In time terms, the complexity order is equals to O(1).%0A   */%0A  public static class Stack2 extends Stack%3CInteger%3E %7B%0A    Stack%3CInteger%3E innerStack = new Stack%3CInteger%3E();%0A%0A    public void push(int item) %7B%0A      if (item %3C= getMin()) %7B%0A        innerStack.push(item);%0A      %7D%0A      super.push(item);%0A    %7D%0A%0A    public Integer pop() %7B%0A      int value = super.pop();%0A      if (value == getMin()) %7B%0A        innerStack.pop();%0A      %7D%0A      return value;%0A    %7D%0A%0A    public int getMin() %7B%0A      if (innerStack.isEmpty()) %7B%0A        return Integer.MAX_VALUE;%0A      %7D else %7B%0A        return innerStack.peek();%0A      %7D%0A    %7D%0A  %7D
 %0A%7D%0A

Add Stack2 implementation to problem 63