Fix the Group

On the previous pages, we fixed values in arrays and nodes in trees. This page takes the same mindset into graphs — where the thing you fix is a connected component, a node's degree, or a structural property of the graph.

It also covers two bonus topics: absolute value tricks and combinatorics problems that use the fixing mindset in a more mathematical way.

Prerequisites: BFS/DFS, connected components, basic graph representation (adjacency list).

---

Pattern 1: Fix the Component (Complement Counting)

You've seen the complement trick on arrays (Bad Pairs on Page 2). On graphs, it's the same idea but scaled up.

The Problem

Count Unreachable Pairs: Given \(N\) nodes and some edges, count pairs of nodes that can't reach each other.

Counting "unreachable" pairs directly is painful — you'd have to check every pair and see if a path exists. But counting "reachable" pairs is easy: nodes in the same connected component can reach each other.

The Fix

\[\text{Unreachable Pairs} = \text{Total Pairs} - \text{Reachable Pairs}\]

Total pairs of \(N\) nodes: \(\frac{N(N-1)}{2}\).

Reachable pairs: for each component of size \(S\), all \(\frac{S(S-1)}{2}\) pairs inside it are reachable.

long long countUnreachable(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<bool> vis(n);
    long long total = (long long)n * (n - 1) / 2;
    long long reachable = 0;

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            // FIX: this connected component
            long long sz = 0;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop(); sz++;
                for (int v : adj[u]) {
                    if (!vis[v]) { vis[v] = true; q.push(v); }
                }
            }
            // CALCULATE: pairs within this component are reachable
            reachable += sz * (sz - 1) / 2;
        }
    }
    return total - reachable;
}

One BFS pass. \(O(N + E)\). The complement trick turned a hard counting problem into a trivial one.

---

Pattern 2: Fix the Node (Degree / In-Degree)

Some graph problems ask you to reason about a node's connections. The fix: look at each node's degree (number of edges) or in-degree (number of incoming edges).

Teaching Example: Min Vertices to Reach All Nodes

Problem: In a DAG, find the smallest set of starting nodes from which you can reach every other node.

Think about it: if a node has in-degree 0, no other node points to it. There's no way to reach it except by starting there. So it must be in the answer. And if a node has in-degree > 0, some other node reaches it — you don't need to start there.

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<int> inDeg(n, 0), ans;
    for (auto& e : edges) inDeg[e[1]]++;
    // FIX: each node
    // CALCULATE: if in-degree is 0, it must be a starting point
    for (int i = 0; i < n; ++i)
        if (inDeg[i] == 0) ans.push_back(i);
    return ans;
}

No DFS needed. Just count incoming edges.

Teaching Example: Maximal Network Rank

Problem: The "network rank" of two cities is the total number of roads connected to either city (minus the shared road, if they're directly connected). Find the maximum network rank.

Fix a pair of cities \((i, j)\). Their rank is deg[i] + deg[j] - connected[i][j]. Try all pairs.

int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    vector<int> deg(n);
    vector<vector<bool>> conn(n, vector<bool>(n));
    for (auto& r : roads) {
        deg[r[0]]++; deg[r[1]]++;
        conn[r[0]][r[1]] = conn[r[1]][r[0]] = true;
    }
    int best = 0;
    // FIX: pair of cities
    // CALCULATE: sum of degrees minus shared edge
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            best = max(best, deg[i] + deg[j] - (int)conn[i][j]);
    return best;
}

\(O(N^2)\) — fine for the given constraints. The insight isn't about speed here, it's about what to fix (the pair) and what to compute from the fix (degree sum minus overlap).

---

Pattern 3: Fix the Component Structure

Some problems ask about the internal structure of each component.

Teaching Example: Count Complete Components

Problem: A component is "complete" if every pair of nodes in it is directly connected. Count the complete components.

A component with \(S\) nodes is complete if it has exactly \(\frac{S(S-1)}{2}\) edges. So: find each component, count its nodes and edges, check.

int countCompleteComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<bool> vis(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            int nodes = 0, edgeCount = 0;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                nodes++;
                edgeCount += adj[u].size();  // count degree
                for (int v : adj[u])
                    if (!vis[v]) { vis[v] = true; q.push(v); }
            }
            // edgeCount counts each edge twice (once from each end)
            // FIX: component structure
            // CALCULATE: is it complete?
            if (edgeCount / 2 == nodes * (nodes - 1) / 2) ans++;
        }
    }
    return ans;
}

Same BFS-for-components pattern. The fix is the component; the calculation checks a structural property.

---

Absolute Value Tricks

Absolute value problems look messy, but they boil down to two ideas:

1. \(|x|\) creates cases. Expand into \(x\) and \(-x\) and handle each case.
2. \(|x - y|\) is distance. Think geometrically — find the closest point.

Trick 1: Case Expansion

Problem (LeetCode 1131): Maximize \(|A[i] - A[j]| + |B[i] - B[j]| + |i - j|\).

Three absolute values means \(2^3 = 8\) sign combinations. But by symmetry, only 4 are distinct. For each combination (say \(+, +, +\)):

\[A[i] + B[i] + i - (A[j] + B[j] + j)\]

This is maximized when one element has the maximum of the transformed value and another has the minimum. One pass per sign combination.

The general pattern: when you see multiple absolute values added together, fix the signs and turn it into a max-minus-min problem on a transformed array.

Trick 2: Binary Search on Answer

Problem: Partition an array into \(K\) subarrays to minimize the maximum subarray sum.

The phrase "minimize the maximum" almost always means binary search on the answer.

Fix a candidate limit \(X\). Ask: "Can I partition so that no subarray sum exceeds \(X\)?" This is a monotonic predicate — if you can do it with limit \(X\), you can do it with any limit \(> X\). So binary search works.

The feasibility check is greedy: scan left to right, keep adding elements to the current subarray. If the sum would exceed \(X\), start a new subarray. If you need more than \(K\) subarrays, the limit is too small.

bool canPartition(vector<int>& nums, int k, long long limit) {
    long long sum = 0;
    int parts = 1;
    for (int x : nums) {
        if (sum + x > limit) {
            // FIX: a partition boundary here
            sum = x;
            parts++;
        } else {
            sum += x;
        }
    }
    return parts <= k;
}
// Binary search: lo = max element, hi = total sum

Trick 3: Closest Value via Sorted Structure

Problem: Find the subarray whose absolute sum is closest to a target \(T\).

Subarray sum = \(P[j] - P[i]\). You want \(|P[j] - P[i] - T|\) minimized. Equivalently, you want \(P[i]\) as close to \(P[j] - T\) as possible.

Maintain a sorted set of prefix sums seen so far. For each new prefix \(P[j]\), use lower_bound to find the closest prefix to \(P[j] - T\) (and \(P[j] + T\) if you need \(|\text{abs}(\text{sum}) - T|\)).

The fix: the current prefix. The calculation: binary search in the sorted set of previous prefixes.

Trick 4: Fix One Element in Sorted Arrays

Problem: Given three sorted arrays and a threshold \(D\), count tuples \((i, j, k)\) where all pairwise absolute differences \(\le D\).

Fix \(A[i]\). Because the arrays are sorted, the valid values in \(B\) and \(C\) form contiguous ranges. Use two pointers or binary search to find those ranges.

Alternatively: merge all three arrays with tagged origins. Use a three-pointer approach — if max - min > D, advance the pointer holding the minimum.

---

Combinatorics: When Fixing Gives You a Formula

These problems don't need data structures. They need you to fix the right variable and count.

Stars and Bars

Problem (Count Sorted Vowel Strings): How many strings of length \(n\) use 5 vowels in non-decreasing order?

This is equivalent to distributing \(n\) items into 5 bins (one per vowel). Stars and Bars gives:

\[\binom{n + 4}{4} = \frac{(n+4)(n+3)(n+2)(n+1)}{24}\]

Fixing a System of Equations

Problem (Ways to Reach Position After K Steps): Starting at position startPos, taking exactly \(k\) steps (each \(+1\) or \(-1\)), how many ways to reach endPos?

Let \(R\) = right steps, \(L\) = left steps. Fix the system:

• \(R + L = k\) (total steps)
• \(R - L = \text{diff}\) (net displacement)

Solving: \(R = (k + \text{diff}) / 2\). If this isn't an integer, there's no solution. Otherwise, the answer is \(\binom{k}{R}\).

---

Practice Set

Warm-Up (Basic Graph Traversal)

1. 547. Number of Provinces — Fix node, count connected components
2. 1971. Find if Path Exists — Fix source, check reachability
3. 841. Keys and Rooms — Fix start room, BFS/DFS to count visitable rooms

Core Practice (Component Properties)

1. 2316. Count Unreachable Pairs * — Fix component, complement count
2. 1319. Operations to Make Network Connected — Fix graph, Calc components - 1
3. 1615. Maximal Network Rank * — Fix pair, Calc deg + deg - shared
4. 1557. Min Vertices to Reach All Nodes * — Fix node, Calc in-degree

Harder (Structural Checks + Search)

1. 2492. Min Score of Path — Fix component of node 1, find min edge
2. 2685. Count Complete Components * — Fix component, check edges == S*(S-1)/2
3. 797. All Paths From Source to Target — Fix path state, backtrack through DAG

Bonus: Combinatorics

1. 62. Unique Paths — Grid math: \(\binom{m+n-2}{m-1}\)
2. 118. Pascal's Triangle — Visualizing \(\binom{n}{r}\)
3. 2400. Ways to Reach Position After K Steps — Fix system of equations, then \(\binom{k}{R}\)
4. 1641. Count Sorted Vowel Strings — Stars and Bars
5. 1359. Count Valid Pickup and Delivery — Permutations with constraints

---

Solutions

Warm-Up

21. Number of Provinces

Standard DFS/BFS to count connected components in an adjacency matrix.

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size(), provinces = 0;
    vector<bool> vis(n);
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            // FIX: a starting node of a new component
            // CALCULATE: traverse entire component, increment count
            provinces++;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int j = 0; j < n; ++j)
                    if (isConnected[u][j] && !vis[j]) {
                        vis[j] = true; q.push(j);
                    }
            }
        }
    }
    return provinces;
}

22. Find if Path Exists

BFS/DFS from source, check if destination is visited.

bool validPath(int n, vector<vector<int>>& edges, int src, int dst) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> vis(n);
    queue<int> q;
    // FIX: source node
    q.push(src); vis[src] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == dst) return true;
        // CALCULATE: reachability
        for (int v : adj[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    return false;
}

23. Keys and Rooms

BFS from room 0. Keys in each room are edges.

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    int n = rooms.size(), visited = 0;
    vector<bool> vis(n);
    queue<int> q;
    q.push(0); vis[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); visited++;
        // FIX: current room
        // CALCULATE: unlock unvisited rooms
        for (int v : rooms[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    return visited == n;
}

Core Practice

24. Count Unreachable Pairs

Complement counting — taught in the main text above.

long long countPairs(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> vis(n);
    long long total = (long long)n * (n - 1) / 2, reachable = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            long long sz = 0;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop(); sz++;
                for (int v : adj[u])
                    if (!vis[v]) { vis[v] = true; q.push(v); }
            }
            reachable += sz * (sz - 1) / 2;
        }
    }
    return total - reachable;
}

25. Operations to Make Network Connected

You need at least \(N - 1\) edges total. If you have that many, the answer is (number of components) - 1.

int makeConnected(int n, vector<vector<int>>& connections) {
    if ((int)connections.size() < n - 1) return -1;
    vector<vector<int>> adj(n);
    for (auto& c : connections) {
        adj[c[0]].push_back(c[1]);
        adj[c[1]].push_back(c[0]);
    }
    // FIX: the graph
    // CALCULATE: number of connected components
    vector<bool> vis(n);
    int components = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            components++;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u])
                    if (!vis[v]) { vis[v] = true; q.push(v); }
            }
        }
    }
    return components - 1;
}

26. Maximal Network Rank

Taught in main text above — fix pair, compute degree sum minus shared edge.

int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    vector<int> deg(n);
    vector<vector<bool>> conn(n, vector<bool>(n));
    for (auto& r : roads) {
        deg[r[0]]++; deg[r[1]]++;
        conn[r[0]][r[1]] = conn[r[1]][r[0]] = true;
    }
    int best = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            best = max(best, deg[i] + deg[j] - (int)conn[i][j]);
    return best;
}

27. Min Vertices to Reach All Nodes

Taught above — nodes with in-degree 0 must be starting points.

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<int> inDeg(n, 0), ans;
    for (auto& e : edges) inDeg[e[1]]++;
    for (int i = 0; i < n; ++i)
        if (inDeg[i] == 0) ans.push_back(i);
    return ans;
}

Harder

28. Min Score of Path

The "score" of a path is the minimum edge weight on it. But any edge in the same component as nodes 1 and N can appear on some path. So the answer is just the minimum edge weight in the component containing node 1.

int minScore(int n, vector<vector<int>>& roads) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& r : roads) {
        adj[r[0]].push_back({r[1], r[2]});
        adj[r[1]].push_back({r[0], r[2]});
    }
    // FIX: the component containing node 0 (0-indexed for node 1)
    int ans = INT_MAX;
    vector<bool> vis(n);
    queue<int> q;
    q.push(0); vis[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adj[u]) {
            // CALCULATE: minimum edge weight in this component
            ans = min(ans, w);
            if (!vis[v]) { vis[v] = true; q.push(v); }
        }
    }
    return ans;
}

29. Count Complete Components

Taught in main text — check edges == S*(S-1)/2 per component.

int countCompleteComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> vis(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            int nodes = 0, edgeCnt = 0;
            queue<int> q;
            q.push(i); vis[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                nodes++;
                edgeCnt += adj[u].size();
                for (int v : adj[u])
                    if (!vis[v]) { vis[v] = true; q.push(v); }
            }
            if (edgeCnt / 2 == nodes * (nodes - 1) / 2) ans++;
        }
    }
    return ans;
}

30. All Paths From Source to Target

DAG — no cycles, so DFS with backtracking finds all paths.

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<vector<int>> ans;
    vector<int> path;
    int target = graph.size() - 1;

    function<void(int)> dfs = [&](int u) {
        path.push_back(u);
        if (u == target) ans.push_back(path);
        else {
            // FIX: current path state
            // CALCULATE: extend to each neighbor
            for (int v : graph[u]) dfs(v);
        }
        path.pop_back();  // backtrack
    };

    dfs(0);
    return ans;
}

Bonus: Combinatorics

31. Unique Paths

Total steps = \((m-1) + (n-1)\). Choose which \((m-1)\) of them go down. Answer: \(\binom{m+n-2}{m-1}\).

int uniquePaths(int m, int n) {
    // FIX: total steps
    // CALCULATE: combinations
    long ans = 1;
    for (int i = 1; i <= m - 1; ++i)
        ans = ans * (n - 1 + i) / i;
    return ans;
}

32. Pascal's Triangle

Each inner value is the sum of the two values above it.

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> r(numRows);
    for (int i = 0; i < numRows; ++i) {
        r[i].resize(i + 1, 1);
        // FIX: row i
        // CALCULATE: inner values from parents
        for (int j = 1; j < i; ++j)
            r[i][j] = r[i - 1][j - 1] + r[i - 1][j];
    }
    return r;
}

33. Ways to Reach Position After K Steps

Fix the system: \(R + L = k\), \(R - L = \text{diff}\). Solve for \(R\). Answer is \(\binom{k}{R}\).

int numberOfWays(int startPos, int endPos, int k) {
    int diff = abs(endPos - startPos);
    if (diff > k || (k - diff) % 2 != 0) return 0;
    // FIX: system of equations
    // CALCULATE: R = (k + diff) / 2, answer = kCr
    int r = (k + diff) / 2;
    long long res = 1, mod = 1e9 + 7;
    // Compute C(k, r) % mod
    vector<long long> fact(k + 1), inv(k + 1);
    fact[0] = 1;
    for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i % mod;
    // Fermat's little theorem for modular inverse
    auto power = [&](long long base, long long exp, long long m) {
        long long res = 1;
        for (base %= m; exp > 0; exp >>= 1) {
            if (exp & 1) res = res * base % m;
            base = base * base % m;
        }
        return res;
    };
    inv[k] = power(fact[k], mod - 2, mod);
    for (int i = k - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
    return fact[k] % mod * inv[r] % mod * inv[k - r] % mod;
}

34. Count Sorted Vowel Strings

Stars and Bars: distribute \(n\) characters into 5 vowel bins.

int countVowelStrings(int n) {
    // FIX: 5 vowels, length n
    // CALCULATE: (n+4) choose 4
    return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
}

35. Count Valid Pickup and Delivery

For \(n\) orders, you place \(2n\) events. Order \(i\): pickup must come before delivery. Formula: \(n! \times (1 \times 3 \times 5 \times \ldots \times (2n-1))\).

int countOrders(int n) {
    long long ans = 1, mod = 1e9 + 7;
    // FIX: order i
    // CALCULATE: ways to place pickup and delivery
    for (int i = 1; i <= n; ++i)
        ans = ans * i % mod * (2 * i - 1) % mod;
    return ans;
}

---

Wrapping Up Session 1

Across these four pages, you've learned one core move applied everywhere:

Page	What You Fix	Data Structure
The Fixing Mindset	The philosophy	None — just thinking
Fix the Equation	Values, remainders, complements	Arrays + hash maps
Fix the Structure	Edges, nodes, paths	Trees + stacks
Fix the Group	Components, degrees, structure	Graphs

The technique scales from Two Sum to graph component analysis. The thinking is always the same: pick one thing, hold it still, see what the rest of the problem has to be.

---