Maximum Population Year
Last Updated: March 29, 2026
Understanding the Problem
We have a list of people, each with a birth year and a death year. A person is alive during any year from their birth year up to (but not including) their death year. We need to find which year had the most people alive, and if there's a tie, return the earliest such year.
The key detail to notice is the half-open interval: a person born in 1993 who dies in 1999 is alive during years 1993, 1994, 1995, 1996, 1997, and 1998, but NOT 1999. This "alive during [birth, death - 1]" rule is the kind of off-by-one detail that trips people up, so it's worth nailing down before writing any code.
The year range is also very small: 1950 to 2050, which is only 101 possible years. That small range is a strong hint that we can afford to check every year individually or use a fixed-size array to track populations.
Key Constraints:
1 <= logs.length <= 100→ At most 100 people. Even an O(n * Y) brute force where Y is the year range (101 years) means about 10,000 operations. Anything works here.1950 <= birthi < deathi <= 2050→ The year range is fixed and tiny (101 years). We can use a fixed-size array indexed by year. This also guarantees every person is alive for at least one year.
Approach 1: Brute Force (Check Every Year)
Intuition
The simplest way to think about this: for each possible year in the range [1950, 2050], count how many people are alive. A person is alive in year y if birth <= y < death. Track which year has the highest count, and return the earliest one in case of ties.
Since the year range is tiny (101 years) and the number of people is small (at most 100), this nested loop is perfectly fine. It's the approach most people would naturally think of first, and it directly translates the problem statement into code.
Algorithm
- Initialize
maxPopulation = 0andresultYear = 0. - For each year
yfrom 1950 to 2050: - Count how many people have
birth <= yanddeath > y. - If this count is greater than
maxPopulation, updatemaxPopulationand setresultYear = y. - Return
resultYear.
Example Walkthrough
Code
- Time Complexity: O(Y * n). We check each of the Y = 101 years against each of the n people (up to 100). That's about 10,100 operations in the worst case.
- Space Complexity: O(1). We only use a few variables. No extra data structures.
This approach works but redundantly checks each person for every year. What if we recorded only the boundary events and swept through them once?
Approach 2: Line Sweep (Difference Array)
Intuition
Instead of counting the population year by year, think of each person as creating two events: a birth (population goes up by 1) and a death (population goes down by 1). If we record these events in an array and then sweep from left to right, accumulating the changes, the running total at each year gives us the population for that year.
This is the line sweep or difference array technique. It's one of the most useful patterns in competitive programming and interviews. The idea is simple: rather than updating every year in a person's lifespan, we only mark where changes happen (the boundaries), and then compute the cumulative effect in a single pass.
For this problem, we create an array of size 101 (covering years 1950 through 2050). For each person with birth year b and death year d, we do +1 at index b - 1950 and -1 at index d - 1950. Then a prefix sum over this array gives the population at each year.
The difference array captures the net change in population at each year. A birth at year b means one more person alive starting from year b. A death at year d means one fewer person alive starting from year d. When we take the prefix sum, each position accumulates all the births that happened up to that year minus all the deaths. That running total is exactly the number of people alive in that year.
We use death (not death - 1) for the -1 event because the problem says a person is NOT alive in their death year. The half-open interval [birth, death) naturally maps to +1 at birth and -1 at death.
Algorithm
- Create an integer array
deltaof size 101 (years 1950 to 2050), initialized to zeros. - For each person
[birth, death]inlogs: - Increment
delta[birth - 1950]by 1 (a person starts being alive). - Decrement
delta[death - 1950]by 1 (a person stops being alive). - Sweep left to right, maintaining a running sum. At each year, the running sum is the population.
- Track the maximum population and the earliest year that achieves it.
- Return that year.
Example Walkthrough
Code
- Time Complexity: O(n + Y). We iterate through the n people once to build the delta array (O(n)), then sweep through the Y = 101 years once (O(Y)). Since Y is constant, this is effectively O(n).
- Space Complexity: O(Y). We use a fixed-size array of 101 integers. Since Y is constant, this is effectively O(1).