Determine if a Simple Graph Exists - Solution & Explanation

Q: Is Determine if a Simple Graph Exists easy or hard?

This problem is typically classified as Medium. The challenge is recognizing that the degree sequence must satisfy graphical sequence conditions and implementing the Erdős–Gallai inequality efficiently with sorting and prefix sums.

Q: Determine if a Simple Graph Exists Python/Java solution

Most implementations follow the Erdős–Gallai theorem: sort the array, compute prefix sums, and validate inequalities. The logic translates directly across Python, Java, C++, and Go since it relies on array operations, sorting, and simple arithmetic checks.

Q: How to solve Determine if a Simple Graph Exists in O(n log n)?

Sort the degrees in descending order and compute prefix sums. First check that the total degree sum is even. Then apply the Erdős–Gallai inequality for each k using prefix sums and binary search to compute the right side efficiently. If all inequalities hold, the sequence represents a valid simple graph.

Q: What is the best approach for Determine if a Simple Graph Exists?

The most efficient method uses the Erdős–Gallai theorem. After sorting the degree sequence in non‑increasing order, verify the theorem's inequality using prefix sums and binary search. This approach runs in O(n log n) time and O(n) space and avoids repeatedly modifying the degree list like simulation methods.

Q: Is Determine if a Simple Graph Exists asked at Google/Amazon/Meta?

Graphical sequence validation problems appear in interviews at companies that test graph theory fundamentals, including Google, Amazon, and Meta. Variants may ask you to verify degree sequences, construct graphs, or simulate Havel–Hakimi reductions.

Q: What data structure is used in Determine if a Simple Graph Exists?

Common implementations use arrays for the degree sequence, sorting for ordering, prefix sums for fast range calculations, and sometimes a max heap when simulating Havel–Hakimi. Graph theory concepts drive the logic even though the algorithm mostly manipulates arrays.

Q: What is the time complexity of Determine if a Simple Graph Exists?

The optimal solution runs in O(n log n) time due to sorting and binary search operations when checking the Erdős–Gallai conditions. Space complexity is O(n) for storing the sorted array and prefix sums. Simulation approaches such as Havel–Hakimi typically take O(n^2 log n).

MediumPremiumFree on FleetCodeArray Binary Search Graph Sorting3 min read

Practice this problem

Problem Statement

You are given an integer array degrees, where degrees[i] represents the desired degree of the i^th 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:

Edges: (0, 1), (0, 2), (0, 3), (2, 3)
Degrees: 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.
This requires degrees[0] and degrees[3] to be at least 2, but both are equal to 1, which contradicts the requirement.
Thus, the answer is false.

Constraints:

1 <= n == degrees.length <= 10⁵
0 <= degrees[i] <= n - 1

Approach Overview

Problem 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

Detailed Complexity Analysis

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.

Frequently Asked Questions

Is Determine if a Simple Graph Exists easy or hard?

This problem is typically classified as Medium. The challenge is recognizing that the degree sequence must satisfy graphical sequence conditions and implementing the Erdős–Gallai inequality efficiently with sorting and prefix sums.

Determine if a Simple Graph Exists Python/Java solution

Most implementations follow the Erdős–Gallai theorem: sort the array, compute prefix sums, and validate inequalities. The logic translates directly across Python, Java, C++, and Go since it relies on array operations, sorting, and simple arithmetic checks.

How to solve Determine if a Simple Graph Exists in O(n log n)?

Sort the degrees in descending order and compute prefix sums. First check that the total degree sum is even. Then apply the Erdős–Gallai inequality for each k using prefix sums and binary search to compute the right side efficiently. If all inequalities hold, the sequence represents a valid simple graph.

What is the best approach for Determine if a Simple Graph Exists?

The most efficient method uses the Erdős–Gallai theorem. After sorting the degree sequence in non‑increasing order, verify the theorem's inequality using prefix sums and binary search. This approach runs in O(n log n) time and O(n) space and avoids repeatedly modifying the degree list like simulation methods.

Is Determine if a Simple Graph Exists asked at Google/Amazon/Meta?

Graphical sequence validation problems appear in interviews at companies that test graph theory fundamentals, including Google, Amazon, and Meta. Variants may ask you to verify degree sequences, construct graphs, or simulate Havel–Hakimi reductions.

What data structure is used in Determine if a Simple Graph Exists?

Common implementations use arrays for the degree sequence, sorting for ordering, prefix sums for fast range calculations, and sometimes a max heap when simulating Havel–Hakimi. Graph theory concepts drive the logic even though the algorithm mostly manipulates arrays.

What is the time complexity of Determine if a Simple Graph Exists?

The optimal solution runs in O(n log n) time due to sorting and binary search operations when checking the Erdős–Gallai conditions. Space complexity is O(n) for storing the sorted array and prefix sums. Simulation approaches such as Havel–Hakimi typically take O(n^2 log n).

Ready to solve this problem?

Practice Determine if a Simple Graph Exists with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance47.5%

Approaches0

Reading time3 min