Problem

You are given a 2D integer array logs where each logs[i] = [birth<sub>i</sub>, death<sub>i</sub>] indicates the birth and death years of the i<sup>th</sup> person.

The population of some year x is the number of people alive during that year. The i<sup>th</sup> person is counted in year x's population if x is in the inclusive range [birth<sub>i</sub>, death<sub>i</sub> - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

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 <= birth<sub>i</sub> < death<sub>i</sub> <= 2050

# Solution

This problem can be solved using a few different approaches. Here, I'll present two methods: a brute-force approach and an optimized approach using prefix sums.

## Brute-Force Approach

The simplest approach is to iterate through all possible years within the given range (1950 to 2050) and, for each year, count the number of people alive during that year. Keep track of the year with the maximum population and return the earliest one.

### Code

```python
def maximum_population_brute_force(logs):
    max_population = 0
    earliest_year = 2051  # Initialize to a value outside the range

    for year in range(1950, 2051):
        population = 0
        for birth, death in logs:
            if birth <= year < death:
                population += 1

        if population > max_population:
            max_population = population
            earliest_year = year
        elif population == max_population and year < earliest_year:
            earliest_year = year

    return earliest_year

Example

logs = [[1993, 1999], [2000, 2010]]
print(maximum_population_brute_force(logs))  # Output: 1993

Optimized Approach: Prefix Sums

A more efficient approach is to use the concept of prefix sums. We can create an array to store the population change for each year. For each log entry, we increment the population at the birth year and decrement it at the death year. Then, we can calculate the cumulative sum of this array to find the population for each year.

Code

def maximum_population_prefix_sums(logs):
    population_change = [0] * 101  # Representing years 1950 to 2050

    for birth, death in logs:
        population_change[birth - 1950] += 1
        population_change[death - 1950] -= 1

    max_population = 0
    earliest_year = 1950
    current_population = 0

    for year in range(101):
        current_population += population_change[year]
        if current_population > max_population:
            max_population = current_population
            earliest_year = year + 1950

    return earliest_year

Example

logs = [[1993, 1999], [2000, 2010]]
print(maximum_population_prefix_sums(logs))  # Output: 1993

Big(O) Run-time Analysis

Brute-Force Approach

• The outer loop iterates through 101 years (from 1950 to 2050).
• The inner loop iterates through the logs array.
• Therefore, the time complexity is O(N * Y), where N is the number of entries in logs and Y is the number of years (101).

Optimized Approach (Prefix Sums)

• The first loop iterates through the logs array, which takes O(N) time.
• The second loop iterates through 101 years, which takes O(Y) time.
• Therefore, the time complexity is O(N + Y), where N is the number of entries in logs and Y is the number of years (101).
• Since Y is constant (101), it simplifies to O(N).

Big(O) Space Usage Analysis

Brute-Force Approach

• The space complexity is O(1) because we are only using a few variables to store the maximum population and the earliest year.

Optimized Approach (Prefix Sums)

• We use an array population_change of size 101 to store the population change for each year.
• Therefore, the space complexity is O(Y), where Y is the number of years (101).
• Since Y is constant, it simplifies to O(1).

Edge Cases and Considerations

1. Empty logs array: If the logs array is empty, the maximum population will be 0, and the earliest year should be initialized to a default value (e.g., 1950).
2. Overlapping Lifespans: The code correctly handles overlapping lifespans by incrementing the population at the birth year and decrementing it at the death year.
3. Same Maximum Population: If multiple years have the same maximum population, the code returns the earliest year.
4. Invalid Input: The problem statement specifies that 1950 <= birth_i < death_i <= 2050. You might want to add input validation to handle cases where this constraint is violated.