Maximum Population Year

Difficulty: Easy | Acceptance: 64.00% | Paid: No Topics: Array, Counting, Prefix Sum

You are given a 2D integer array logs where each logs[i] = [birthi, deathi] indicates the birth and death years of the ith person.

The population of some year x is the number of people alive during that year. The ith person is counted in year x’s population if x is in the inclusive range [birthi, deathi - 1]. Note that the person is not counted in the year they die.

Return the year with the maximum population. If there are multiple years with the maximum population, return the smallest year.

• Examples
• Constraints
• Brute Force Simulation
• Prefix Sum / Line Sweep

Examples

Example 1

Input:

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

Output:

1993

Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2

Input:

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

Output:

1960

Explanation: The maximum population is 2, and it had happened in years 1960 and 1970. The earlier year between them is 1960.

Constraints

1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050

Brute Force Simulation

Intuition Since the range of years is fixed and small (1950 to 2050), we can create an array representing each year and increment the count for every year a person is alive.

Steps

• Initialize an array population of size 101 (for years 1950 to 2050) with zeros.
• Iterate through each person in logs.
• For each person, iterate from their birth year to death - 1 year.
• Increment the corresponding index in the population array (index = year - 1950).
• Iterate through the population array to find the index with the maximum value.
• Return the year corresponding to that index (index + 1950).

from typing import List

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        # Array to store population count for years 1950 to 2050
        population = [0] * 101
        
        for birth, death in logs:
            # Increment population for each year the person is alive
            for year in range(birth, death):
                population[year - 1950] += 1
        
        max_pop = 0
        max_year = 1950
        
        # Find the earliest year with maximum population
        for i in range(101):
            if population[i] > max_pop:
                max_pop = population[i]
                max_year = i + 1950
                
        return max_year

Complexity

• Time: O(N * L) where N is the number of logs and L is the maximum lifespan (max 100). Effectively O(N).
• Space: O(1) as the array size is fixed (101).
• Notes: Simple to implement and very efficient given the constraints.

Prefix Sum / Line Sweep

Intuition Instead of iterating through every year of every person’s life, we can mark the start (+1) and end (-1) of a life. By calculating the running sum (prefix sum) of these changes, we can determine the population for each year in a single pass.

Steps

• Initialize an array changes of size 102 (1950 to 2051) with zeros.
• Iterate through each person in logs.
• Increment changes[birth - 1950] by 1.
• Decrement changes[death - 1950] by 1 (since the person is not alive in the death year).
• Iterate through the changes array, maintaining a running sum currentPop.
• Track the maximum population encountered and the corresponding year.
• Return the earliest year with the maximum population.

from typing import List

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        # Array to store population changes (delta)
        # Size 102 to accommodate index 2050 (death year)
        changes = [0] * 102
        
        for birth, death in logs:
            changes[birth - 1950] += 1
            changes[death - 1950] -= 1
        
        max_pop = 0
        current_pop = 0
        max_year = 1950
        
        # Calculate prefix sum to find population for each year
        for i in range(101):
            current_pop += changes[i]
            if current_pop > max_pop:
                max_pop = current_pop
                max_year = i + 1950
                
        return max_year

Complexity

• Time: O(N + Y) where N is the number of logs and Y is the number of years (101).
• Space: O(1) as the array size is fixed.
• Notes: More optimal than brute force if the year range was large, as it processes each life in O(1) time.