Why my n^2 C++ always TLE?


  • 0
    F
    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            vector<unordered_set<int>> mapping(stones.size(), unordered_set<int>());
            mapping[0].insert(0);
            for (int i = 0;i < stones.size();++i) {
                for (int j = 0;j < i; ++j) {
                    int dis = stones[i] - stones[j];
                    if (mapping[j].count(dis) || mapping[j].count(dis - 1) || mapping[j].count(dis + 1)) {
                        mapping[i].insert(dis);
                    }
                }
            }
            return mapping.back().size() > 0;
        }
    };
    

    My code is as above, I have seen in the post that N^2 algorithm can pass the test case, but my O(N^2) algorithm always TLE, can anyone point out what is wrong with my algorithm?


  • 0
    M

    I think your code is O(n^3), because mapping[i].insert(dis) is O(n).


Log in to reply
 

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