Abstract / Summary

Given yearly birth and death data, find the earliest year with the highest population.

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 64% (100k+ submissions).

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 maximumPopulation method receives a list of birth-death year pairs and returns the year that experiences the highest living population. It builds a year-wise delta map, walks through the years in chronological order, maintains a running count of alive people, and records the first year where this count reaches a new peak.

Key Steps

Accumulate yearly population changes

A dictionary named changes records how the population varies at each distinct year. For every [birth, death] pair the method increments the entry for the birth year and decrements the entry for the death year. This representation captures the net effect of all individuals without storing each person separately.

changes = defaultdict(int)
for birth, death in logs:
    changes[birth] += 1
    changes[death] -= 1

Process years in chronological order

The keys of changes are sorted, guaranteeing that the algorithm examines years from earliest to latest. As it iterates, a running total have is updated by adding the delta for the current year. This total reflects the exact number of people alive during that year.

have = 0
for year in sorted(changes):
    delta = changes[year]
    have += delta
    ...

Track the year with the maximum population

Two auxiliary variables, high and result, keep the highest observed population count and the corresponding year. Whenever the running total have exceeds high, both high and result are updated. Because the years are processed in order, the first year that reaches a new maximum is automatically selected.

    if high < have:
        high   = have
        result = year

Finally, the method returns result, the earliest year with the greatest number of living individuals.

return result

Edge Cases Handled

When a birth and death occur in the same year, the increment and decrement for that year cancel each other out, leaving the net delta at zero. The algorithm therefore correctly excludes such individuals from influencing the population count for that year.

If the input logs list is empty, the changes dictionary remains empty, the loop over sorted(changes) never executes, and the initial value of result (zero) is returned. This behavior gracefully handles the absence of data without raising errors.

The use of defaultdict(int) ensures that any year not previously seen is treated as having a delta of zero, eliminating the need for explicit existence checks.

Performance Optimizations

The solution avoids constructing an explicit array spanning the entire possible year range. Instead, it stores only the years that actually appear in the input, which reduces memory usage when the range is large but sparsely populated.

By applying a single pass to build the changes map and a second pass over the sorted keys, the algorithm achieves linear work relative to the number of distinct years, rather than the total span of years.

The choice of defaultdict eliminates conditional logic inside the accumulation loop, allowing the interpreter to execute the increment and decrement operations directly.

Sorting is performed on the set of keys rather than on the original list of logs, which limits the sorting cost to the number of unique years rather than the total number of records.

Overall, the method leverages a compact delta representation, ordered traversal, and built-in data structures to deliver an efficient solution for determining the year of maximum population.

Imagine a big, bustling park that spans many years. People are arriving and leaving all the time. This code acts like a helper who keeps a tally of the crowd.

First, the helper looks at a list of birthdays and the years people pass away. For every person, the helper marks down a plus one for the year they arrive and a minus one for the year they leave. It is a bit like keeping a tally on a chalkboard.

Next, the helper lines up all these years in order, starting from the very first one. As the helper walks through the timeline year by year, they keep track of how many people are currently in the park. If a new person arrives, the crowd total goes up. If someone leaves, the crowd total goes down.

While checking each year, the helper asks if the current crowd is the biggest one seen so far. If there are more people than ever before, the helper makes a tiny note of that year. By the time the helper finishes walking through every single year, the year with the very largest crowd is the answer found.

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

Time: loglinear
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++	Python	JS	Java			Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim						C
	everthis			JS
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

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