Share a concise O(N) method in C++ which runs in 16ms.


  • 2
    W

    The main idea is to scan the array from the end. We hold a dist variable to store the distance of the current index from the last index, or the possible index to the end.

    class Solution {
    public:
        bool canJump(int A[], int n) {
            if (0 < n && n <= 1) {
    			return true;
    		}
    		int idx = n - 2, dist = 1;
    		while (idx >= 0) {
    			(A[idx] >= dist) ? (dist = 1) : ++dist;
    			--idx;
    		}
    		return dist == 1 ? true : false;
        }
    };

Log in to reply
 

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