Passed before but get a TLE now


  • 3
    A

    I write me c++ solution using stranded union-find with "balance" feature (with a rank). It passed first time. However, after few days when I trying to solve this problem again. I got a TLE at the 1, 10000 test case. I have cope paste some of the top rank post int c++ language. they actually slow than mine. (and also got a TLE). I do not know why? I saw the Java solution with the same idea only takes 15ms.


  • 0

    I have just relaxed the constraint. Your solution is now accepted. Sorry about that.


  • 0
    A

    Thanks!
    Do you know why Java solutions are so outperform C++ solutions?


  • 0
    A
    class Solution {
        struct Node {
            pair<int, int> parent;
            int height;
            Node():parent(-1,-1), height(1) {}
        };
        // get_parent node;
        inline Node * get_parent (Node** ptable, Node* cur) {
            return &ptable[cur->parent.first][cur->parent.second];
        }
        inline bool is_empty(Node *n) {
            return n->parent.first == -1;
        }
        // find
        Node * find(Node** ptable, int i, int j) {
            Node * cur = &ptable[i][j];
            if (!is_empty(cur)) {
                Node * next = cur;
                do {
                    cur = next;
                    next = get_parent(ptable, cur);
                } while (cur != next);
            }
            return cur;
        }
        // merge, this should be called when non of the node is (-1,-1)
        Node * merge(Node**ptable, Node*n1, Node*n2, int &count) {
            if (n1 == n2 || is_empty(n2)) {
                return n1;
            }
            count--;
            if (n1->height < n2->height) {
                n1->parent = n2->parent;
                return n2;
            } else if (n1->height > n2->height) {
                n2->parent = n1->parent;
                return n1;
            } else {
                n2->height++;
                n1->parent = n2->parent;
                return n2;
            }
        }
        
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            Node** ptable = new Node*[m];
            for (int i=0; i<m; ++i) {
                ptable[i] = new Node[n];
            }
            vector<int> res;
            res.reserve(positions.size());
            int count=0;
            Node * n1, n2;
            for (const pair<int, int> &p : positions) {
                int i=p.first;
                int j=p.second;
                n1 = find(ptable, i, j);
                if (!is_empty(n1)) {
                    res.push_back(count);
                    continue;
                }
                count++;
                // set to itsefl
                n1->parent.first = i;
                n1->parent.second = j;
                
                // ^v<>;
                if (i>0) n1 = merge(ptable, n1, find(ptable, i-1, j), count);
                if (i+1<m) n1 = merge(ptable, n1, find(ptable, i+1, j), count);
                if (j>0) n1 = merge(ptable, n1, find(ptable, i, j-1), count);
                if (j+1<n) merge(ptable, n1, find(ptable, i, j+1), count);
                res.push_back(count);
            }
            
            for (int i = 0; i<m; ++i) {
                delete [] ptable[i];
            }
            delete [] ptable;
            return res;
        }
    };

  • 0

    Currently Java measures only the solution time, while C++ measures the entire time, including reading input and writing output. In future we will try to change this to measure only the solution time across all languages.


Log in to reply
 

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