How hard is LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?

LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is rated Hard on LeetCode.

What is the time complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?

The Python solution on this page uses O(n + m) auxiliary space.

What topics does LeetCode 2508. Add Edges to Make Degrees of All Nodes Even cover?

LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is tagged Graph and Hash Table on LeetCode.

Add Edges to Make Degrees of All Nodes Even — LeetCode 2508 Python Solution

HardGraphHash Table

Problem: #2508
Pattern: Depth-First Search
Reading time: 4 min
Source: leetcode.com

The problem

There is an undirected graph consisting of n nodes numbered from 1 to n. You are given the integer n and a 2D array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi.

Example

Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output: true
Explanation: The above diagram shows a valid way of adding an edge.

Python solution

Python

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        g = defaultdict(set)
        for a, b in edges:
            g[a].add(b)
            g[b].add(a)
        vs = [i for i, v in g.items() if len(v) & 1]
        if len(vs) == 0:
            return True
        if len(vs) == 2:
            a, b = vs
            if a not in g[b]:
                return True
            return any(a not in g[c] and c not in g[b] for c in range(1, n + 1))
        if len(vs) == 4:
            a, b, c, d = vs
            if a not in g[b] and c not in g[d]:
                return True
            if a not in g[c] and b not in g[d]:
                return True
            if a not in g[d] and b not in g[c]:
                return True
            return False
        return False

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?: LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is rated Hard on LeetCode.
What is the time complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 2508. Add Edges to Make Degrees of All Nodes Even cover?: LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is tagged Graph and Hash Table on LeetCode.