Summer Coding Challenge, Week #1

Stack.java

import java.io.*;
import java.util.*;

public class Stack 
{
    private int[] stack;
    private int N = 0;
    private int min;

    public int getMin() throws EmptyStackException
    {
        if (this.isEmpty()) throw new EmptyStackException();
        return  min;
    }

    public Stack(int capacity)
    {
        stack = new int[capacity];
        this.min = Integer.MAX_VALUE;
    }

    public Stack()
    {
        stack = new int[1];
        this.min = Integer.MAX_VALUE;
    }

    public boolean isEmpty()
    {
        return N == 0;
    }

    private int encode(int n)
    {
        return n * 2 - this.min;
    }

    public void push(int n)
    {
        if (N == stack.length) resize (2 * stack.length);
        if (min > n)
        {
            stack[N++] = encode(n);
            min = n;
        }
        else 
        {
            stack[N++] = n;
        }
    }

    public int pop() throws EmptyStackException
    {
        if (this.isEmpty()) throw new EmptyStackException();

        int ret = stack[--N];
        if (ret < min)
        {
          int tmp = ret;
          ret = this.min;
          this.min = 2 * ret - tmp;
        }
    
        return ret;
    }

    public int peek() throws EmptyStackException
    {
        if (!this.isEmpty())
        {
            int ret = stack[N-1];
            if (ret < this.min)
            {
                int tmp = ret;
                ret = this.min;
            }

            return ret;
        }
        else
            throw new EmptyStackException();
    }

    private void resize(int capacity)
    {
        int [] copy = new int[capacity];
        for (int i = 0; i < N; i++)
            copy[i] = stack[i];
        stack = copy;
    }

    public static void main(String[] args)
    {
        // Test: push all the integers from the input, pop one by one and check
        // min value by calling getMin()
        // sample input:
        // 5 10 3 4 2 15

        Stack st = new Stack();

        Scanner in = new Scanner(System.in);
        while (in.hasNextInt())
        {
            int item = in.nextInt();
            st.push( item );
            System.out.println("pushed: " + item);
        }

        while (!st.isEmpty())
        {
            System.out.println("min: " + st.getMin() + " peek: " + st.peek() + " pop: " + st.pop());
        }

        return;
    }
}

Stack1.md

Design a stack that support getMin() function in O(1) time complexity with O(1) additional space. The stack support push(), pop(), peek(), and getMin() in O(1) time.