My Simple AC Greedy C++ Solution, Is It Linear?


  • 0
    L

    My idea is simple. Just always choose the proper next position which can let me jump farthest. The outer loop depends on problem size n, but the inner loop depends on the values of the array. So whats the running complexity of this situation? Is it still linear?

    class Solution {
    public:
        int jump(int A[], int n) {
            if(n==1) return 0;
            int result=0;
            int pos=0; // Current position
            while(pos<n)
            {
                int max=0;
                int next=0;
                if(pos+A[pos]>=n-1) return result+1; // Could reach the destination from this position
                for(int i=1;i<=A[pos];i++) // Check the next A[pos] values and jump to max
                {
                    if((A[pos+i]+(i-1))>=max)
                    {
                        max=A[pos+i]+(i-1);
                        next=pos+i;
                    }
                }
                if(pos==next) return -1; // No solution
                pos=next;
                result++;
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.