LeetCode 1854 - Maximum Population Year

The problem asks us to determine the year with the highest population given a list of birth and death years. Each element in the input logs is a pair [birthi, deathi] representing the inclusive start of life at birthi and exclusive end at deathi.

leetcodeeasyarraycountingprefix-sum

LeetCode Problem 1854

Difficulty: 🟢 Easy
Topics: Array, Counting, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the year with the highest population given a list of birth and death years. Each element in the input logs is a pair [birthi, deathi] representing the inclusive start of life at birthi and exclusive end at deathi. In other words, a person is considered alive from their birth year up to the year before they die. The input size is modest, with up to 100 people and years ranging from 1950 to 2050, giving a maximum span of 101 years. The output should be the earliest year in which the population reaches its maximum.

Important points to note are that birth years are strictly less than death years, and years outside the 1950-2050 range are not possible. Edge cases include when all people are born in the same year, when populations peak in multiple years, or when births and deaths are consecutive.

Approaches

A brute-force approach would simulate each year from 1950 to 2050, counting how many people are alive in that year by iterating through the logs. This guarantees correctness but involves iterating through all years for each person, resulting in a time complexity of O(101 * n), which is acceptable here due to small constraints but not elegant.

A better approach uses the prefix sum or difference array technique. We can record changes in population: increment at each birth year and decrement at each death year. Then a cumulative sum over the years quickly reveals the population for each year. This approach leverages the fact that the year range is small, allowing O(n + Y) time, where Y is the number of years (101). This approach is efficient and easy to implement.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * 101) O(1) Count alive people for each year
Optimal (Prefix Sum) O(n + 101) O(101) Track population changes and compute cumulative sums

Algorithm Walkthrough

  1. Initialize an array population of size 101 (for years 1950-2050) to zeros. Each index i corresponds to year 1950 + i.
  2. Iterate over each person's log [birth, death]. Increment population[birth - 1950] by 1 to indicate a new birth and decrement population[death - 1950] by 1 to indicate a death (exclusive).
  3. Initialize variables max_population to 0 and earliest_year to 1950. These track the current highest population and the year it occurs.
  4. Compute the prefix sum over population. For each year, add the previous year's population to get the cumulative population. If the current population exceeds max_population, update max_population and earliest_year.
  5. Return earliest_year as the result.

Why it works: By recording population increments and decrements and computing cumulative sums, we correctly track the number of people alive in each year. The first year to reach the maximum population is naturally captured by iterating from 1950 onward.

Python Solution

from typing import List

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        population = [0] * 101  # Index 0 -> 1950, Index 100 -> 2050
        
        for birth, death in logs:
            population[birth - 1950] += 1
            population[death - 1950] -= 1
        
        max_population = 0
        earliest_year = 1950
        current_population = 0
        
        for i in range(101):
            current_population += population[i]
            if current_population > max_population:
                max_population = current_population
                earliest_year = 1950 + i
        
        return earliest_year

The implementation first converts the years to array indices by subtracting 1950. It accumulates population changes in the population array. Then, by scanning from 1950 onward, it calculates the cumulative population and updates the earliest year with the maximum population.

Go Solution

func maximumPopulation(logs [][]int) int {
    population := make([]int, 101) // 1950-2050

    for _, log := range logs {
        birth, death := log[0], log[1]
        population[birth-1950]++
        population[death-1950]--
    }

    maxPop := 0
    earliestYear := 1950
    currentPop := 0

    for i := 0; i < 101; i++ {
        currentPop += population[i]
        if currentPop > maxPop {
            maxPop = currentPop
            earliestYear = 1950 + i
        }
    }

    return earliestYear
}

In Go, slices are used to store the population changes. The implementation mirrors Python closely. Go requires explicit slice initialization with make, and integer arithmetic is safe here since the population is within reasonable bounds.

Worked Examples

Example 1

logs = [[1993,1999],[2000,2010]]

Year Population change Cumulative population
1993 +1 1
1994 0 1
1995 0 1
...
1999 -1 0
2000 +1 1

Maximum population is 1, earliest year is 1993.

Example 2

logs = [[1950,1961],[1960,1971],[1970,1981]]

Year Population
1950 1
1960 2
1970 2

Maximum is 2, earliest year is 1960.

Complexity Analysis

Measure Complexity Explanation
Time O(n + 101) O(n) to process logs, O(101) to scan population array
Space O(101) Fixed-size array for population differences

The complexity is efficient due to the small, fixed range of years. The approach scales linearly with the number of people, which is acceptable given the constraints.

Test Cases

# Provided examples
assert Solution().maximumPopulation([[1993,1999],[2000,2010]]) == 1993  # earliest with max population
assert Solution().maximumPopulation([[1950,1961],[1960,1971],[1970,1981]]) == 1960

# Edge cases
assert Solution().maximumPopulation([[1950,1951]]) == 1950  # single person
assert Solution().maximumPopulation([[1950,1960],[1950,1960]]) == 1950  # same birth years
assert Solution().maximumPopulation([[1990,2000],[1991,2001],[1992,2002]]) == 1992  # overlapping births
Test Why
[[1993,1999],[2000,2010]] Tests simple disjoint intervals
[[1950,1961],[1960,1971],[1970,1981]] Tests overlapping intervals and earliest selection
[[1950,1951]] Tests minimum input
[[1950,1960],[1950,1960]] Tests multiple same-year births
[[1990,2000],[1991,2001],[1992,2002]] Tests overlapping with maximum in middle year

Edge Cases

The first edge case is when all people are born and die in consecutive years. A naive algorithm might miscount the end year as inclusive, but using death - 1950 ensures exclusivity. The second edge case is when multiple years have the same maximum population; the algorithm must pick the earliest, which is handled by iterating from 1950 onward. The third edge case is the smallest possible input, a single person, which the array-based approach naturally handles without special conditions.