Why my code behaves not that bad ? Actually it behaves pretty good which I don't understand...


  • 0
    M

    Hi All, so I have a solution run in 36 ms and beats 80 %. While i don't understand why it behaves faster than I thought. Because theoretically this algorithm should behave O(n^n) in worst case but it doesn't. I even tried the large input case mentioned in this thread. But it still run in 0ms.

    Anyway, so my algorithm is to find whether there is a stone can reach the end. To answer this question, iterate all stones before end, from end-1th to the 0th and for every stone i, we then keep asking whether there is a stone can reach to i.

    To answer whether there is a stone can reach i, we need to first calculate what is step required to reach i and find whether we have such a stone. For example:

    [0,1,3,5,6,8,12,17]

    If we want to reach 17, the end, let's first check end-1 which is 12, since distance between 12 to 17 is 5, we then ask "do we have a stone can reach 12 with either 4, 5 or 6 steps. Then we find stone 8 (4 steps) and 6 (6 steps) can do that. We then keep asking same question to 8 and 6. For 8, the distance to 12 is 4, so we ask "do we have a stone can reach 8 with either 3, 4, or 5 steps", for 6, the distance to 12 is 6, so we ask "do we have a stone can reach 6 with either 5,6 or 7 steps?" and so on until we reach to the first one.

    Since the end will ask every stones before it so it loops (n-1) times, and for each DoWeHave[i] question, the time taken should be 1 * 2 * 3 * ... i so the run time complexity (worst case) should beO(n^n).

    My plan was to make the logic correct first, then do some memorization optimization when I got TLE but I passed all the test cased even with the large one and I just confused why. Did I calculate the time complexity wrong? or this question was intended to use a O(n^n) algorithm. Any hint will be appreciated. Below is my code:

    class Solution {
    public:
        bool doWeHave(vector<int>& stones, unordered_map<int,int>& dict, int end, int step1, int step2, int step3) {
            if (end == 0) {
                if (step1 == 0 || step2 == 0 || step3 == 0) {
                    return true;
                }
                else {
                    return false;
                }
            }
            else if (end == 1) {
                if (step1 == 1 || step2 == 1 || step3 == 1) {
                    return true;
                }
                else {
                    return false;
                }
            }
            else {
                int current = stones[end];
                if (step1 > 0 && dict.find(current - step1) != dict.end()) {
                    int index = dict[current-step1], dist = stones[end] - stones[index];
                    if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
                        return true;
                    }
                }
                if (step2 > 0 && dict.find(current - step2) != dict.end()) {
                    int index = dict[current-step2], dist = stones[end] - stones[index];
                    if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
                        return true;
                    }
                }
                if (step3 > 0 && dict.find(current - step3) != dict.end()) {
                    int index = dict[current-step3],dist = stones[end] - stones[index];
                    if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
                        return true;
                    }
                }
                return false;
            }
        }
        bool canCross(vector<int>& stones) {
            int len = stones.size();
            if (len == 1) {
                return true;
            }
            
            else {
                unordered_map<int,int> dict;
                for (int i = 0; i < len; i++) {
                    dict[stones[i]] = i;
                }
                int dest = stones[len-1];
                for (int i = len-2; i >= 0; i--) {
                    int current = stones[i];
                    int step1 = dest-current-1, step2 = dest-current, step3 = dest-current+1;
                    if (doWeHave(stones, dict, i, step1, step2, step3)) {
                        return true;
                    }
                }
                return false;
            }
        }
    };
    

Log in to reply
 

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