Leetcode - Max Level Party Invites

Hard

Jan 13, 2026

#graph

#dp

#dfs

Max Level Party Invites

You are given a list of n employees each assigned a level between 0 and 10. The employees and their levels are represented as an array of integers, levels, where the index, i, is the employee's identifier and the value levels[i] is their level.

You are also provided a reporting_chain which represents the reporting structure of employees where each entries first value is the manager and the second value in that entry is their direct report.

For example, a reporting_chain that consists of [[0, 1], [0, 2], [1, 3]] would indicate:

Employee 0 manages Employee 1 Employee 0 manages Employee 2 Employee 1 manages Employee 3

You are tasked with inviting people from this company to a party, however, the constraint is the if an employee is invited, none of their direct reports can be invited.

Following this constraint, return the max sum of levels possible given a selection of employees to invite.

Example 1:

Input: levels = [10, 9, 9, 5, 5, 5, 6], reporting_chain = [[0, 1], [0,2], [1, 3], [1, 4], [1, 5], [2, 6]]
Output: 31
Explanation: If we invite 0 (level 10), employee 1 (level 9) and 2 (level 9) cannot be invited. Inviting the rest is fine and thus the best sum is 31.

Example 2:

Input: levels = [8, 6, 7, 4, 5], reporting_chain = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 20
Explanation: Invite 0, 2, 4. Skip 1, 3.

Example 3:

Input: levels = [10, 9], reporting_chain = [[0, 1]]
Output: 10
Explanation: No other employees

Notes

Intuition

This is a tree DP problem similar to "House Robber III." For each employee, we compute two values: the maximum sum if we invite them (must skip their direct reports) and if we skip them (can choose either for reports).

Implementation

Build an adjacency list from the reporting chain and identify root employees (those without managers). DFS with memoization computes (invite, skip) pairs bottom-up. If we invite an employee, add their level plus the skip values of all reports. If we skip, add max(invite, skip) of each report. Process all roots and sum the maximum of invite/skip for each tree.

Edge-cases

The graph may be a forest (multiple disconnected trees). Track which nodes have parents to identify all roots and process each independently.

Time: O(n) — each node processed exactly once via memoization
Space: O(n) — adjacency list and memoization cache

Complexity

Solution

from typing import List, Tuple, Dict
from collections import defaultdict

class Solution:
    def maxLevelPartyInvites(self, levels: List[int], reporting_chain: List[List[int]]) -> int:
        n = len(levels)
        reports = defaultdict(list)
        # Create adjacency list and mark parents to extract roots later
        has_parent = [False] * n
        for manager, report in reporting_chain:
            reports[manager].append(report)
            has_parent[report] = True


        memo: Dict[int, Tuple[int, int]] = {}
        def dfs(employee: int) -> Tuple[int, int]:
            if employee in memo:
                return memo[employee]

            invite_employee = levels[employee]
            skip_employee = 0
            for report in reports[employee]:
                invite_report, skip_report = dfs(report)
                invite_employee += skip_report # if u is invited, sum if v is not invited (skip_v)
                skip_employee += max(invite_report, skip_report) # if u is skipped, we can choose to invite v or not

            memo[employee] = (invite_employee, skip_employee)
            return memo[employee]

        # Only start DFS on roots because otherwise we can miss nodes or double count them
        root_employees = [i for i in range(n) if not has_parent[i]]
        total = 0
        for root_employee in root_employees:
            invite, skip = dfs(root_employee)
            total += max(invite, skip)
        return total;

if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()