[Leetcode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis:

Since it is sorted array, binary search may be the hint. Let m be the middle index of array num, if num[0] < num[m], then first part is sorted, the minimum element would be either num[0] or the minimum of the second part, which can be computed recursively. Similarly, if num[m] < num[n], second part is sorted, the minimum element would be either num[m] or the minimum of the first part. 

 int findMin(vector<int> &num) {
        int b = 0;
        int e = num.size() - 1;
        int minValue = INT_MAX;
        while(b <= e) {
            int m = b + (e- b)/2;
            //it is sorted from b to m
            if (num[b] <= num[m]) {
                minValue = min(num[b], minValue);
                b = m + 1;
            }
            else {
                minValue = min(num[m], minValue);
                e = m-1;
            }
        }
        return minValue;
    }

[Leetcode] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Analysis:

Apparently, we need to use extra space to store the minimum element of the stack. We can use one stack s to store the pushed element and another stack sMin to store minimum elements appearing so far. Whenever an element x is pushed, if it is less than current minimum (at the top of sMin stack), push x to the sMin; otherwise, the top of the sMin is the minimum and we push it to sMin;

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x < sMin.top())
            sMin.push(x);
        else
            sMin.push(sMin.top());
    }

    void pop() {
        s.pop();
        sMin.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

However, it could not pass Leetcode oj as Memory Limit Exceeded.  By looking at the solution again, we notice that if x is greater than minimum value, there is no need to push the sMin top value. Just do some special handle when popping the element: if the element is greater than minimum, do not pop sMin.

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x <= sMin.top())
            sMin.push(x);
    }

    void pop() {
        if (s.top() <= sMin.top())
            sMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

In addition, we notice that if all the pushed elements are the same, there are still spaces wasted. It is possible to have a better solution so that few spaces needed for sMin.