Count unhappy friends

Array Simulation

62.5% acceptance

Feb 25, 2026

304

887

You are given a list of preferences for n friends, where n is always even. For each person i, preferences[i] contains a list of friends sorted in the order of preference. All the friends are divided into pairs. A friend x is unhappy if x is paired with y and there exists a friend u who is paired with v but x prefers u over y, and u prefers x over v. Return the number of unhappy friends.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    // rank[x][y] = preference rank of y for x (lower = more preferred)
    let mut rank = vec![vec![0usize; n]; n];
    for (x, prefs) in preferences.iter().enumerate() {
      for (i, &y) in prefs.iter().enumerate() {
        rank[x][y as usize] = i;
      }
    }
    // partner[x] = the person x is paired with
    let mut partner = vec![0usize; n];
    for pair in &pairs {
      partner[pair[0] as usize] = pair[1] as usize;
      partner[pair[1] as usize] = pair[0] as usize;
    }

    let mut unhappy = 0;
    for x in 0..n {
      let y = partner[x];
      // x is unhappy if there exists u such that rank[x][u] < rank[x][y] and rank[u][x] < rank[u][partner[u]]
      for u in 0..n {
        if u == x || u == y {
          continue;
        }
        let v = partner[u];
        if rank[x][u] < rank[x][y] && rank[u][x] < rank[u][v] {
          unhappy += 1;
          break;
        }
      }
    }
    unhappy
  }
}