Abstract / Summary

Given employees with hierarchy links and importance values compute the total importance for an employee and all their subordinates.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Hash Table
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method getImportance. The method receives a list of Employee objects and an employee identifier, then computes the total importance value for that employee, including the importance contributed by all direct and indirect subordinates. The algorithm builds a dictionary for constant-time lookup, then uses a memoized recursive helper to aggregate importance values across the hierarchy.

Key Steps

Building a lookup table

all = { e.id : e for e in employees }

A dictionary named all is created where each key is an employee’s unique identifier and each value is the corresponding Employee instance. This enables O(1) access to any employee record during recursion, eliminating the need for repeated linear scans of the input list.

Defining a memoized recursive function

@cache
def deeper(i):
    return all[i].importance + sum(deeper(j) for j in all[i].subordinates)

The inner function deeper takes an employee identifier i. It retrieves the employee’s own importance and adds the sum of the importance values of all subordinates by recursively invoking itself. The @cache decorator (from functools) stores results of previous calls, so each employee’s total importance is computed only once even if the employee appears in multiple subordinate lists.

Initiating the computation

return deeper(id)

The public method returns the result of calling deeper with the target employee identifier, delivering the aggregated importance for the entire subordinate tree rooted at that employee.

Edge Cases Handled

When the target employee has no subordinates, all[i].subordinates is an empty collection. The generator expression inside sum yields no values, and sum returns zero, so the function correctly returns only the employee’s own importance.

If the employee hierarchy contains shared subordinates (i.e., a subordinate reports to more than one manager), the memoization ensures that the subordinate’s importance is calculated a single time and reused, preventing double counting in the final sum.

The dictionary construction gracefully handles an empty employees list; attempting to retrieve a non-existent identifier would raise a KeyError, which aligns with the expectation that the provided id must correspond to a valid employee in the input.

Performance Optimizations

The dictionary lookup eliminates repeated traversal of the employee list, turning what could be an O(n²) operation into O(n) for the initial setup.

Memoization via @cache transforms the recursive aggregation into a dynamic programming solution. Each employee’s total importance is computed once, and subsequent references retrieve the cached value in constant time. This reduces the overall number of recursive calls dramatically, especially in dense hierarchies where many managers share subordinates.

The use of a generator expression inside sum avoids constructing intermediate lists, keeping memory usage low while iterating over subordinate identifiers.

Collectively, these choices ensure that the algorithm scales efficiently with the size of the employee hierarchy, delivering fast results even for large organizational structures.

Imagine a big company full of people organized like a family tree. Each person has a special number that shows how much work they do and a list of friends who work under them.

The code starts by making a quick checklist so it can find any person instantly just by looking for their number.

Next, there is a helpful little robot named deeper. This robot is given a person's number. It looks at how much work that person does and writes it down. Then, it looks at the list of friends working under that person. For every friend, it asks itself the exact same question again to find out how much work they do, and then it asks about their friends, and so on. It keeps doing this until it reaches people who do not have anyone working under them.

The robot keeps a tiny notepad to remember the answers it finds. That way, if it ever needs to know the work total for the same person again, it already knows the answer and does not have to do all the work over. Finally, it adds every single piece of work it found to get one big total number.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++	JS	Python	Java		Go	TS
	LeetcodeHelp	C++		Python	Java
	Progiez	C++		Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim		JS
	everthis		JS
	fengvyi	C++
	halfrost						Go
	JoshCrozier		JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	lzl124631x	C++
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	JavaScript
everthis	JavaScript
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality