Minimum Edge Weight Equilibrium Queries in a Tree

Hard
1712.

Minimum Edge Weight Equilibrium Queries in a Tree

Minimum Edge Weight Equilibrium Queries in a Tree is a hard coding problem on arrays, trees and graph, asked in Amazon and Google interviews.

An undirected tree has n nodes numbered 0 to n - 1. Each edges[i] = [u, v, w] is an edge between u and v with weight w, where 1 <= w <= 26.

For each query queries[j] = [a, b], find the minimum number of operations needed to make every edge on the path from a to b have the same weight. One operation changes the weight of one edge to any value.

Queries are independent: the tree returns to its original weights before each query. Return an array whose j-th entry answers queries[j].

Example 1

Input
n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
Output
[0,0,1,3]
Explanation
Path 2 → 6 has weights 1, 2, 2, 2: change the single 1. Path 0 → 6 has three 1s and three 2s: change three edges.

Example 2

Input
n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
Output
[1,2,2,3]
Explanation
Path 4 → 6 is 4–2–1–3–6 with weights 6, 6, 4, 6: change the 4.

Example 3

Input
n = 1, edges = [], queries = [[0,0]]
Output
[0]
Explanation
An empty path needs no changes.

Constraints

  • 1 <= n <= 10^4
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= u, v < n
  • 1 <= w <= 26
  • edges represents a valid tree
  • 1 <= queries.length <= 2 * 10^4
  • queries[j].length == 2
  • 0 <= a, b < n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[][]} queries
 * @return {number[]}
 */
var minOperationsQueries = function(n, edges, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Edge Weight Equilibrium Queries in a Tree — Solution

Minimum Edge Weight Equilibrium Queries in a Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Edge Weight Equilibrium Queries in a Tree is a hard coding problem on arrays, trees and graph, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Trees, Graph
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An undirected tree has n nodes numbered 0 to n - 1. Each edges[i] = [u, v, w] is an edge between u and v with weight w, where 1 <= w <= 26.

For each query queries[j] = [a, b], find the minimum number of operations needed to make every edge on the path from a to b have the same weight. One operation changes the weight of one edge to any value.

Queries are independent: the tree returns to its original weights before each query. Return an array whose j-th entry answers queries[j].

Example 1

Input: n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
Output: [0,0,1,3]
Explanation: Path 2 → 6 has weights 1, 2, 2, 2: change the single 1. Path 0 → 6 has three 1s and three 2s: change three edges.

Example 2

Input: n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
Output: [1,2,2,3]
Explanation: Path 4 → 6 is 4–2–1–3–6 with weights 6, 6, 4, 6: change the 4.

Example 3

Input: n = 1, edges = [], queries = [[0,0]]
Output: [0]
Explanation: An empty path needs no changes.

Constraints

  • 1 <= n <= 10^4
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= u, v < n
  • 1 <= w <= 26
  • edges represents a valid tree
  • 1 <= queries.length <= 2 * 10^4
  • queries[j].length == 2
  • 0 <= a, b < n

Hints for Minimum Edge Weight Equilibrium Queries in a Tree

  1. Hint 1

    For one path, keep the most common weight and change everything else: the answer is path length − (count of the most frequent weight).

  2. Hint 2

    There are only 26 possible weights. Root the tree and store, for every node, how many edges of each weight lie on its path from the root.

  3. Hint 3

    With l = LCA(a, b), the count of weight w on the path is cnt[a][w] + cnt[b][w] − 2·cnt[l][w], and the length is depth[a] + depth[b] − 2·depth[l]. Find the LCA with binary lifting.

How to solve Minimum Edge Weight Equilibrium Queries in a Tree

The cheapest way to equalise a path is to keep its most frequent weight. Because weights come from just 26 values, per-node prefix counts from the root let any path's weight histogram be assembled from three nodes: the two endpoints and their lowest common ancestor.

Approach

  1. BFS from node 0 to get each node's parent, depth and cnt[v][w] — the number of edges of weight w between the root and v (the parent's counts plus the edge into v).
  2. Build binary-lifting tables up[k][v] (the 2^k-th ancestor).
  3. For a query, lift the deeper endpoint to the other's depth, then lift both while their ancestors differ to find l.
  4. Path length len = depth[a] + depth[b] − 2·depth[l]; best kept weight m = max_w (cnt[a][w] + cnt[b][w] − 2·cnt[l][w]); answer len − m.

Why it works

The root-to-a and root-to-b paths both contain the root-to-l path; subtracting it twice leaves exactly the edges of the a–b path, so the histogram is exact. Changing every edge that differs from the kept weight is necessary and sufficient, and keeping the most frequent weight minimises the number of changes.

Complexity

  • Time — O((n + q) · (26 + log n))
  • Space — O(n · (26 + log n))

Pitfalls

  • When a == b the path is empty and the answer is 0.
  • Weights are 1-based (1 to 26); size the count table accordingly.
  • Per-query path walking is O(n) each — too slow for 2 · 10^4 queries on a long path; that is why the LCA is needed.

Reference solution

Python

from typing import List

def minOperationsQueries(n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    LOG = max(1, n.bit_length())
    up = [[0] * n for _ in range(LOG)]
    depth = [0] * n
    cnt = [[0] * 27 for _ in range(n)]
    seen = [False] * n
    seen[0] = True
    order = [0]
    for u in order:
        for v, w in adj[u]:
            if not seen[v]:
                seen[v] = True
                up[0][v] = u
                depth[v] = depth[u] + 1
                cnt[v] = cnt[u][:]
                cnt[v][w] += 1
                order.append(v)
    for k in range(1, LOG):
        prev, cur = up[k - 1], up[k]
        for v in range(n):
            cur[v] = prev[prev[v]]

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        diff = depth[a] - depth[b]
        for k in range(LOG):
            if diff >> k & 1:
                a = up[k][a]
        if a == b:
            return a
        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a, b = up[k][a], up[k][b]
        return up[0][a]

    res = []
    for a, b in queries:
        l = lca(a, b)
        length = depth[a] + depth[b] - 2 * depth[l]
        keep = max(cnt[a][w] + cnt[b][w] - 2 * cnt[l][w] for w in range(1, 27))
        res.append(length - keep)
    return res

Java

public static int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }
    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    int[][] up = new int[LOG][n];
    int[] depth = new int[n];
    int[][] cnt = new int[n][27];
    boolean[] seen = new boolean[n];
    int[] order = new int[n];
    int head = 0, tail = 0;
    order[tail++] = 0;
    seen[0] = true;
    while (head < tail) {
        int u = order[head++];
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (seen[v]) continue;
            seen[v] = true;
            up[0][v] = u;
            depth[v] = depth[u] + 1;
            cnt[v] = cnt[u].clone();
            cnt[v][e[1]]++;
            order[tail++] = v;
        }
    }
    for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
    int[] res = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int a = queries[q][0], b = queries[q][1];
        int x = a, y = b;
        if (depth[x] < depth[y]) { int t = x; x = y; y = t; }
        int diff = depth[x] - depth[y];
        for (int k = 0; k < LOG; k++) if (((diff >> k) & 1) == 1) x = up[k][x];
        if (x != y) {
            for (int k = LOG - 1; k >= 0; k--) if (up[k][x] != up[k][y]) { x = up[k][x]; y = up[k][y]; }
            x = up[0][x];
        }
        int l = x, keep = 0;
        for (int w = 1; w <= 26; w++) keep = Math.max(keep, cnt[a][w] + cnt[b][w] - 2 * cnt[l][w]);
        res[q] = depth[a] + depth[b] - 2 * depth[l] - keep;
    }
    return res;
}

C++

vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
    vector<vector<pair<int, int>>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back({e[1], e[2]}); adj[e[1]].push_back({e[0], e[2]}); }
    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    vector<vector<int>> up(LOG, vector<int>(n, 0));
    vector<int> depth(n, 0);
    vector<array<int, 27>> cnt(n);
    cnt[0].fill(0);
    vector<bool> seen(n, false);
    vector<int> order = {0};
    seen[0] = true;
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (auto& e : adj[u]) {
            int v = e.first, w = e.second;
            if (seen[v]) continue;
            seen[v] = true;
            up[0][v] = u;
            depth[v] = depth[u] + 1;
            cnt[v] = cnt[u];
            cnt[v][w]++;
            order.push_back(v);
        }
    }
    for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
    vector<int> res;
    for (auto& q : queries) {
        int a = q[0], b = q[1], x = a, y = b;
        if (depth[x] < depth[y]) swap(x, y);
        int diff = depth[x] - depth[y];
        for (int k = 0; k < LOG; k++) if ((diff >> k) & 1) x = up[k][x];
        if (x != y) {
            for (int k = LOG - 1; k >= 0; k--) if (up[k][x] != up[k][y]) { x = up[k][x]; y = up[k][y]; }
            x = up[0][x];
        }
        int l = x, keep = 0;
        for (int w = 1; w <= 26; w++) keep = max(keep, cnt[a][w] + cnt[b][w] - 2 * cnt[l][w]);
        res.push_back(depth[a] + depth[b] - 2 * depth[l] - keep);
    }
    return res;
}

JavaScript

var minOperationsQueries = function(n, edges, queries) {
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1], edges[e][2]);
        adj[edges[e][1]].push(edges[e][0], edges[e][2]);
    }
    var LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    var up = [], depth = new Array(n), cnt = new Array(n * 27), seen = new Array(n);
    for (var k = 0; k < LOG; k++) { up.push(new Array(n)); for (var z = 0; z < n; z++) up[k][z] = 0; }
    for (var a0 = 0; a0 < n; a0++) { depth[a0] = 0; seen[a0] = false; }
    for (var c0 = 0; c0 < n * 27; c0++) cnt[c0] = 0;
    seen[0] = true;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j += 2) {
            var v = adj[u][j], w = adj[u][j + 1];
            if (seen[v]) continue;
            seen[v] = true;
            up[0][v] = u;
            depth[v] = depth[u] + 1;
            for (var t = 0; t < 27; t++) cnt[v * 27 + t] = cnt[u * 27 + t];
            cnt[v * 27 + w]++;
            order.push(v);
        }
    }
    for (var k2 = 1; k2 < LOG; k2++) for (var x = 0; x < n; x++) up[k2][x] = up[k2 - 1][up[k2 - 1][x]];
    var lca = function(a, b) {
        if (depth[a] < depth[b]) { var tmp = a; a = b; b = tmp; }
        var diff = depth[a] - depth[b];
        for (var k = 0; k < LOG; k++) if ((diff >> k) & 1) a = up[k][a];
        if (a === b) return a;
        for (var k3 = LOG - 1; k3 >= 0; k3--) if (up[k3][a] !== up[k3][b]) { a = up[k3][a]; b = up[k3][b]; }
        return up[0][a];
    };
    var res = [];
    for (var q = 0; q < queries.length; q++) {
        var p = queries[q][0], r = queries[q][1], l = lca(p, r);
        var len = depth[p] + depth[r] - 2 * depth[l], keep = 0;
        for (var wt = 1; wt <= 26; wt++) {
            var c = cnt[p * 27 + wt] + cnt[r * 27 + wt] - 2 * cnt[l * 27 + wt];
            if (c > keep) keep = c;
        }
        res.push(len - keep);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Trees and Tree Traversals