[C++][Jump Game Array] with and without stack O(n)


#1

with Stack

int Solution::canJump(vector<int> &A) {
    int len = A.size();
    if(len == 1)    return true;
    stack<int> st;
    for(int i=0; i<len; i++) {
        if(A[i] == 0){
            if(st.empty())                      return false;
            if((st.top()+A[st.top()]) <= i)     return false;
        }
        else
            if(st.empty())                              st.push(i);
            else if((st.top()+A[st.top()]) < (i+A[i]))  st.push(i);
    }
    return true;
}

without Stack

int Solution::canJump(vector<int> &A) {
    int len = A.size(), count = 0;
    int validUpto = A[0];
    for(int i=1; i<len; i++) {
        if(i > validUpto)   return 0;
        validUpto = max(validUpto, A[i]+i);
    }
    return true;
}