Add Edges to Make Degrees of All Nodes Even

Hard
1705.

Add Edges to Make Degrees of All Nodes Even

Add Edges to Make Degrees of All Nodes Even is a hard coding problem on hash table and graph, asked in Amazon and Google interviews.

An undirected graph has n nodes numbered 1 to n; each edges[i] = [a, b] is an edge between a and b. The graph may be disconnected.

You may add at most two new edges. A new edge must not join a node to itself and must not repeat an edge that already exists (including one you added).

Return true if you can make the degree of every node even this way, and false otherwise. The degree of a node is the number of edges touching it.

Example 1

Input
n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output
true
Explanation
Only nodes 4 and 5 have odd degree, and they are not yet joined: adding the edge [4,5] makes every degree even.

Example 2

Input
n = 4, edges = [[1,2],[3,4]]
Output
true
Explanation
Add [1,3] and [2,4]: every node now has degree 2.

Example 3

Input
n = 4, edges = [[1,2],[1,3],[1,4]]
Output
false
Explanation
All four nodes have odd degree, and every way to pair them up needs an edge that already exists.

Constraints

  • 3 <= n <= 10^5
  • 2 <= edges.length <= 10^5
  • edges[i].length == 2
  • 1 <= a, b <= n
  • a != b
  • there are no repeated edges
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
 * @return {boolean}
 */
var isPossible = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Add Edges to Make Degrees of All Nodes Even — Solution

Add Edges to Make Degrees of All Nodes Even solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Add Edges to Make Degrees of All Nodes Even is a hard coding problem on hash table and graph, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Hash Table, 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 graph has n nodes numbered 1 to n; each edges[i] = [a, b] is an edge between a and b. The graph may be disconnected.

You may add at most two new edges. A new edge must not join a node to itself and must not repeat an edge that already exists (including one you added).

Return true if you can make the degree of every node even this way, and false otherwise. The degree of a node is the number of edges touching it.

Example 1

Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output: true
Explanation: Only nodes 4 and 5 have odd degree, and they are not yet joined: adding the edge [4,5] makes every degree even.

Example 2

Input: n = 4, edges = [[1,2],[3,4]]
Output: true
Explanation: Add [1,3] and [2,4]: every node now has degree 2.

Example 3

Input: n = 4, edges = [[1,2],[1,3],[1,4]]
Output: false
Explanation: All four nodes have odd degree, and every way to pair them up needs an edge that already exists.

Constraints

  • 3 <= n <= 10^5
  • 2 <= edges.length <= 10^5
  • edges[i].length == 2
  • 1 <= a, b <= n
  • a != b
  • there are no repeated edges

Hints for Add Edges to Make Degrees of All Nodes Even

  1. Hint 1

    An added edge changes the parity of exactly its two endpoints, so only the nodes of odd degree matter — and there is always an even number of them.

  2. Hint 2

    With two edges you can fix at most four odd nodes. More than four: impossible. Zero: already done.

  3. Hint 3

    Four odd nodes a, b, c, d: try the three ways to pair them, each pair needing a missing edge. Two odd nodes a, b: either join them directly, or find a third node joined to neither and connect it to both.

How to solve Add Edges to Make Degrees of All Nodes Even

Adding an edge flips the parity of its two endpoints, so the problem is about the set of odd-degree nodes. With at most two edges, only 0, 2 or 4 odd nodes can be fixed, and each case is a constant number of edge-existence checks.

Approach

  1. Count degrees and collect the odd nodes.
  2. None odd: return true. More than four odd: return false.
  3. Two odd nodes a, b: if a–b is not an edge, add it. Otherwise look for any node c (not a or b) adjacent to neither; adding a–c and b–c fixes both while c gains 2.
  4. Four odd nodes: return whether one of the pairings {ab, cd}, {ac, bd}, {ad, bc} uses two missing edges.

Why it works

Every odd node needs an odd number of new edges touching it, so two edges can serve at most four odd nodes. With four, both edges must join odd nodes in disjoint pairs — exactly the three pairings. With two, either one edge joins them, or two edges meet at a common third node (any other shape would leave a new odd node).

Complexity

  • Time — O(n + m)
  • Space — O(n + m)

Pitfalls

  • With two odd nodes that are already adjacent, the third node must avoid both of them, not just one.
  • The graph can be disconnected; the third node may come from any component.
  • Store edges in a set (or scan adjacency) so each existence check is cheap — never test all pairs.

Reference solution

Python

from typing import List

def isPossible(n: int, edges: List[List[int]]) -> bool:
    adj = [set() for _ in range(n + 1)]
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    odd = [v for v in range(1, n + 1) if len(adj[v]) % 2 == 1]
    if not odd:
        return True
    if len(odd) == 2:
        a, b = odd
        if b not in adj[a]:
            return True
        return any(c != a and c != b and c not in adj[a] and c not in adj[b] for c in range(1, n + 1))
    if len(odd) == 4:
        a, b, c, d = odd

        def free(x, y):
            return y not in adj[x]

        return (free(a, b) and free(c, d)) or (free(a, c) and free(b, d)) or (free(a, d) and free(b, c))
    return False

Java

public static boolean isPossible(int n, int[][] edges) {
    List<Set<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new HashSet<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    List<Integer> odd = new ArrayList<>();
    for (int v = 1; v <= n; v++) if (adj.get(v).size() % 2 == 1) odd.add(v);
    if (odd.isEmpty()) return true;
    if (odd.size() == 2) {
        int a = odd.get(0), b = odd.get(1);
        if (!adj.get(a).contains(b)) return true;
        for (int c = 1; c <= n; c++)
            if (c != a && c != b && !adj.get(a).contains(c) && !adj.get(b).contains(c)) return true;
        return false;
    }
    if (odd.size() == 4) {
        int a = odd.get(0), b = odd.get(1), c = odd.get(2), d = odd.get(3);
        Set<Integer> A = adj.get(a), B = adj.get(b), C = adj.get(c);
        return (!A.contains(b) && !C.contains(d)) || (!A.contains(c) && !B.contains(d)) || (!A.contains(d) && !B.contains(c));
    }
    return false;
}

C++

bool isPossible(int n, vector<vector<int>>& edges) {
    vector<unordered_set<int>> adj(n + 1);
    for (auto& e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); }
    vector<int> odd;
    for (int v = 1; v <= n; v++) if (adj[v].size() % 2 == 1) odd.push_back(v);
    auto freeEdge = [&](int x, int y) { return adj[x].count(y) == 0; };
    if (odd.empty()) return true;
    if (odd.size() == 2) {
        int a = odd[0], b = odd[1];
        if (freeEdge(a, b)) return true;
        for (int c = 1; c <= n; c++)
            if (c != a && c != b && freeEdge(a, c) && freeEdge(b, c)) return true;
        return false;
    }
    if (odd.size() == 4) {
        int a = odd[0], b = odd[1], c = odd[2], d = odd[3];
        return (freeEdge(a, b) && freeEdge(c, d)) || (freeEdge(a, c) && freeEdge(b, d)) || (freeEdge(a, d) && freeEdge(b, c));
    }
    return false;
}

JavaScript

var isPossible = function(n, edges) {
    var adj = [];
    for (var i = 0; i <= n; i++) adj.push(new Set());
    for (var e = 0; e < edges.length; e++) { adj[edges[e][0]].add(edges[e][1]); adj[edges[e][1]].add(edges[e][0]); }
    var odd = [];
    for (var v = 1; v <= n; v++) if (adj[v].size % 2 === 1) odd.push(v);
    var free = function(x, y) { return !adj[x].has(y); };
    if (odd.length === 0) return true;
    if (odd.length === 2) {
        var a = odd[0], b = odd[1];
        if (free(a, b)) return true;
        for (var c = 1; c <= n; c++) if (c !== a && c !== b && free(a, c) && free(b, c)) return true;
        return false;
    }
    if (odd.length === 4) {
        var p = odd[0], q = odd[1], r = odd[2], s = odd[3];
        return (free(p, q) && free(r, s)) || (free(p, r) && free(q, s)) || (free(p, s) && free(q, r));
    }
    return false;
};

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

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Graph Data Structure