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^52 <= edges.length <= 10^5edges[i].length == 21 <= a, b <= na != bthere are no repeated edges
Hints for Add Edges to Make Degrees of All Nodes Even
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.
Hint 2
With two edges you can fix at most four odd nodes. More than four: impossible. Zero: already done.
Hint 3
Four odd nodes
a, b, c, d: try the three ways to pair them, each pair needing a missing edge. Two odd nodesa, 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
- Count degrees and collect the odd nodes.
- None odd: return
true. More than four odd: returnfalse. - Two odd nodes
a, b: ifa–bis not an edge, add it. Otherwise look for any nodec(notaorb) adjacent to neither; addinga–candb–cfixes both whilecgains 2. - 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 FalseJava
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