Determine if a simple graph exists

Array Binary Search Graph Theory Sorting Prefix Sum

47.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn simple_graph_exists(degrees: Vec<i32>) -> bool {
    // Erdős–Gallai theorem — O(n log n) with prefix sums + binary search
    let n = degrees.len();
    let mut d = degrees;
    let sum: i64 = d.iter().map(|&x| x as i64).sum();
    if sum % 2 != 0 {
      return false;
    }
    d.sort_unstable_by(|a, b| b.cmp(a));

    // prefix[i] = sum of d[0..i]
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + d[i] as i64;
    }

    let mut left_sum: i64 = 0;
    for k in 1..=n {
      left_sum += d[k - 1] as i64;
      // Find first index in d[k..] where d[i] < k (sorted descending)
      // boundary is the first index >= k such that d[index] < k
      let boundary = {
        let slice = &d[k..];
        let pos = slice.partition_point(|&x| x >= k as i32);
        k + pos
      };
      // sum of min(d[i], k) for i in k..n
      // = k * (boundary - k)  [indices where d[i] >= k]
      // + (prefix[n] - prefix[boundary])  [indices where d[i] < k]
      let right_sum = k as i64 * (boundary - k) as i64
        + (prefix[n] - prefix[boundary]);
      if left_sum > (k as i64) * (k as i64 - 1) + right_sum {
        return false;
      }
    }
    true
  }
}