Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lejafilip

· 8 months ago

Code:

class Solution {
    class DSU
    {
        public:
        
        DSU(int n):id(n), sz(n, 1)
        {
            std::ranges::iota(id, 0);
        }

        int find(int val)
        {
            int v = val;
            while(v != id[v])
            {
                v = id[v];
            }

            int next = id[val];
            while(next != v)
            {
                next = id[val];
                id[val] = v;
                val = next;
            }

            return v;
        }

        void unify(int val1, int val2)
        {
            int root1 = find(val1);
            int root2 = find(val2);

            if(root1 == root2)
            {
                return;
            }

            if(sz[root1] < sz[root2])
            {