Maximum number of accepted invitations

Array Depth-First Search Graph Theory Matrix

52.4% acceptance

Mar 31, 2026

236

There are m boys and n girls in a class attending an upcoming party. You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the ith boy can invite the jth girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy. Return the maximum possible number of accepted invitations.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_invitations(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut match_girl = vec![-1i32; n];
    let mut result = 0;
    for boy in 0..m {
      let mut visited = vec![false; n];
      if Self::dfs(&grid, boy, &mut match_girl, &mut visited) {
        result += 1;
      }
    }
    result
  }

  fn dfs(grid: &[Vec<i32>], boy: usize, match_girl: &mut [i32], visited: &mut [bool]) -> bool {
    for girl in 0..grid[0].len() {
      if grid[boy][girl] == 1 && !visited[girl] {
        visited[girl] = true;
        if match_girl[girl] == -1 || Self::dfs(grid, match_girl[girl] as usize, match_girl, visited) {
          match_girl[girl] = boy as i32;
          return true;
        }
      }
    }
    false
  }
}