LeetCode Solutions Blog

Maximum Population Year

Number: 1983

Difficulty: Easy

Paid? No

Problem Description

Given a list of logs where each log represents the birth and death years of a person, determine the earliest year with the maximum number of people alive. A person is considered alive in the inclusive range [birth, death-1] (i.e., they are not counted in the year of their death).

Key Insights

Use a difference array (or prefix sum technique) to mark changes in population over the years.
Increment the population counter at the birth year and decrement at the death year.
Traverse through the years (from 1950 to 2050) to compute the prefix sum, which gives the population for each year.
Track the maximum population and update the earliest year whenever a new maximum is found.

Space and Time Complexity

Time Complexity: O(R) where R is the range of years (a constant range from 1950 to 2050, so effectively O(1)). Space Complexity: O(R) for the difference array (again constant space with respect to input size).

Solution

We use a difference array technique to track the population changes. For each log, we increase the population count at the birth year and decrease it at the death year (since the person is not alive during the death year). We then iterate through the years from 1950 to 2050, accumulating the changes to compute the population per year. By tracking the maximum population encountered and choosing the earliest year with that population, we can determine the required answer.

Code Solutions

# Python solution using a difference array approach

def maximumPopulation(logs):
    # Define the start and end years based on problem constraints.
    start_year = 1950
    end_year = 2050
    # Create an array to hold the changes in population for each year.
    # We need an extra space to handle the last decrement.
    population_changes = [0] * (end_year + 2)
    
    # For each log, increment count at birth year and decrement count at death year.
    for birth, death in logs:
        population_changes[birth] += 1  # Person becomes alive in the birth year
        population_changes[death] -= 1  # Person is not alive in the death year
        
    max_population = 0  # To store maximum observed population
    max_year = start_year  # To store the corresponding earliest year
    current_population = 0  # Running total of the population
    
    # Iterate from start_year to end_year to compute population count per year.
    for year in range(start_year, end_year + 1):
        current_population += population_changes[year]
        # Update maximum and earliest year if a new maximum population is found.
        if current_population > max_population:
            max_population = current_population
            max_year = year
            
    return max_year

# Example usage:
logs = [[1950,1961],[1960,1971],[1970,1981]]
print(maximumPopulation(logs))  # Expected output: 1960