My Wrong code got AC


  • 0
    J
    class Solution {
        public:
            bool canJump(int A[], int n) {
                int start = 0;
                while(start < n)
                {
                    int furthest = start;
                    for(int i = start; i <= start + A[start]; i++)
                    {
                        furthest = max(furthest, A[i] + i);
                        if(furthest >= n-1)
                            return true;
                    }
                    if(furthest == start)  // couldn't proceed anymore and haven't reached end yet
                        return false;
                    
                    start = furthest;
                }
                return false;
            }
        };
    

    My code got AC, however for test case: [5,9,3,2,1,0,2,3,3,1,0,0], it gave wrong answer, just because I used wrong greedy strategy.


  • 0

    Thanks so much for your suggested test case. I've added your test case and your solution should get wrong answer now.


Log in to reply
 

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