You are given an integer array degrees, where degrees[i] represents the desired degree of the ith vertex.
Your task is to determine if there exists an undirected simple graph with exactly these vertex degrees.
A simple graph has no self-loops or parallel edges between the same pair of vertices.
Return true if such a graph exists, otherwise return false.
Example 1:
Input: degrees = [3,1,2,2]
Output: true
Explanation:
One possible undirected simple graph is:
(0, 1), (0, 2), (0, 3), (2, 3)deg(0) = 3, deg(1) = 1, deg(2) = 2, deg(3) = 2.Example 2:
Input: degrees = [1,3,3,1]
Output: false
Explanation:
degrees[1] = 3 and degrees[2] = 3 means they must be connected to all other vertices.degrees[0] and degrees[3] to be at least 2, but both are equal to 1, which contradicts the requirement.false.
Constraints:
1 <= n == degrees.length <= 1050 <= degrees[i] <= n - 1Problem Overview: You are given an array representing vertex degrees. The task is to determine whether these degrees can correspond to a valid simple graph (no self‑loops and no multiple edges). In other words, decide if there exists a graph whose degree sequence exactly matches the given array.
Approach 1: Havel–Hakimi Simulation with Re-sorting (O(n^2 log n) time, O(n) space)
The direct way to validate a degree sequence is the Havel–Hakimi process. Sort the degrees in descending order, remove the largest degree d, and subtract 1 from the next d degrees. Repeat until all values become zero or a negative value appears. If a negative value occurs or d exceeds the number of remaining nodes, the sequence is invalid. This approach repeatedly sorts the array after each reduction, making it simple to implement but slower for large inputs.
Approach 2: Priority Queue Optimization (O(n^2 log n) time, O(n) space)
Instead of re-sorting the entire array every iteration, maintain the degrees in a max heap. Extract the largest degree, then decrement the next largest d elements and push them back into the heap. This avoids repeated full sorting operations but still performs many heap operations. It works well when you want a cleaner simulation of edge assignments in a graph construction process.
Approach 3: Erdős–Gallai Theorem with Sorting + Prefix Sum (O(n log n) time, O(n) space)
The optimal approach uses the Erdős–Gallai theorem. First sort the degree array in non‑increasing order using sorting. A necessary condition is that the total sum of degrees is even. Then verify the Erdős–Gallai inequality for every k: the sum of the first k degrees must be ≤ k(k−1) + Σ min(d_i, k) for the remaining vertices. Precompute prefix sums to evaluate the left side quickly and use binary search to find where degrees drop below k. This reduces repeated scanning and brings the complexity down to O(n log n).
Recommended for interviews: Start by mentioning the Havel–Hakimi process to demonstrate understanding of graphical sequences. Then implement the Erdős–Gallai validation with prefix sums and sorting. Interviewers prefer this method because it proves correctness mathematically and runs in O(n log n) time.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Havel–Hakimi with Re-sorting | O(n^2 log n) | O(n) | Best for understanding the graphical sequence process or quick brute-force validation. |
| Priority Queue Simulation | O(n^2 log n) | O(n) | When simulating graph edge assignments while avoiding repeated full sorting. |
| Erdős–Gallai with Prefix Sum | O(n log n) | O(n) | Optimal solution for large inputs and typical interview expectations. |
Practice Determine if a Simple Graph Exists with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor