Maximum Population Year
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 interval is half-open: a person born in 1993 who dies in 1999 is alive during years 1993, 1994, 1995, 1996, 1997, and 1998, but NOT 1999. The death year is excluded. Getting this boundary right is the difference between a correct and an off-by-one answer.
The year range is also small: 1950 to 2050, which is only 101 possible years. That bound lets us afford to check every year individually or use a fixed-size array indexed by year.
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
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.
With at most 101 years and 100 people, this nested loop does about 10,000 operations, which is well within limits. It also translates the problem statement directly 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.
The brute force rechecks every person for every year. The next approach records only the boundary events for each person and sweeps through them once.
Approach 2: Line Sweep (Difference Array)
Intuition
Each person creates 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 is the population for that year.
This is the line sweep or difference array technique. Rather than updating every year in a person's lifespan, we only mark where the population changes (the two boundaries), then compute the cumulative effect in a single pass.
We create an array of size 101 (covering years 1950 through 2050). For each person with birth year b and death year d, we add +1 at index b - 1950 and -1 at index d - 1950. A prefix sum over this array then gives the population at each year.
The death event must be placed at death, not death - 1. A person counts in year y exactly when birth <= y < death, so they should contribute to the running sum for [birth, death) and stop contributing at death. Placing +1 at birth and -1 at death makes the prefix sum increase from year birth onward and drop back at year death, which matches the half-open interval. If the -1 went at death - 1, the person would be dropped one year too early.
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).