Problem Statement

You are given a 2D integer array logs containing the birth and death years of n people. In logs array, logs[i] = [birth_i, death_i] indicates the birth and death years of the i^th person.

The population of a year is the number of people alive during that year. The i^th person is counted in year x's population if x is in the inclusive range [birth_i, death_i - 1].

Return the earliest year with the highest population.

Examples

Example 1:

• Input: logs = [[1980, 1990], [1975, 1985], [1985, 1995], [1990, 2000], [1999, 2020], [1994, 2032]]
• Expected Output: 1994
• Explanation: The population in the year 1994 was the highest. In that year, 3 people were alive (born in 1985, 1990, and 1994).

Example 2:

• Input: logs = [[1970, 1990], [1980, 2009], [1960, 1970], [1959, 1982]]
• Expected Output: 1980
• Explanation: The population in the year 1980 was the highest. In that year, three people were alive (born in 1970, 1980, and 1959).

Example 3:

• Input: logs = [[2000, 2010], [2005, 2015], [2010, 2020], [2015, 2025]]
• Expected Output: 2005
• Explanation: The population in the year 2005 was the highest. In that year, two people were alive (born in 2000, and 2005).

Constraints:

• 1 <= logs.length <= 100
• 1950 <= birth_i < death_i <= 2050

Solution

To solve this problem, we can use a counting approach to keep track of population changes over the years. This approach involves using a single array to count the number of people born and another to count the number of people who have died. By iterating through these arrays, we can compute the population for each year and determine the year with the highest population.

This approach is efficient because it avoids the need to sort the years, making it faster. Instead, we directly compute the population changes and keep track of the maximum population year. This counting method ensures that we process each birth and death year once, leading to an optimal solution.

Step-by-Step Algorithm

1. Initialize the Population Array:

   • Create an array population of size 101 to store population changes for each year from 1950 to 2050.

2. Record Births and Deaths:

   • For each log in logs:
     • Increment the population at the birth year index: population[log[0] - 1950]++.
     • Decrement the population at the death year index: population[log[1] - 1950]--.

3. Initialize Variables for Tracking Maximum Population:

   • maxPop to 0: This will keep track of the maximum population encountered.
   • maxYear to 1950: This will store the year with the maximum population.
   • currentPop to 0: This will track the current population while iterating through the years.

4. Calculate Maximum Population Year:

   • For each year from 0 to 100:
     • Add the population change for the current year to currentPop: currentPop += population[year]. It adds positive or negative value to the currentPop based on the number of births or deaths in the year.
     • If currentPop is greater than maxPop:
       • Update maxPop to currentPop.
       • Update maxYear to the current year: maxYear = 1950 + year.

5. Return the Result:

   • Return maxYear, which is the year with the maximum population.

Algorithm Walkthrough

Using the input: [[1980, 1990], [1975, 1985], [1985, 1995], [1990, 2000], [1999, 2020], [1994, 2032]]

1. Initialization:

   • population array of size 101 is initialized to all zeros.

2. Processing logs:

   • For [1980, 1990]:
     • Increment population[30] by 1. (population[1980 - 1950])
     • Decrement population[40] by 1. (population[1990 - 1950])
   • For [1975, 1985]:
     • Increment population[25] by 1. (population[1975 - 1950])
     • Decrement population[35] by 1. (population[1985 - 1950])
   • For [1985, 1995]:
     • Increment population[35] by 1. (population[1985 - 1950])
     • Decrement population[45] by 1. (population[1995 - 1950])
   • For [1990, 2000]:
     • Increment population[40] by 1. (population[1990 - 1950])
     • Decrement population[50] by 1. (population[2000 - 1950])
   • For [1999, 2020]:
     • Increment population[49] by 1. (population[1999 - 1950])
     • Decrement population[70] by 1. (population[2020 - 1950])
   • For [1994, 2032]:
     • Increment population[44] by 1. (population[1994 - 1950])
     • Decrement population[82] by 1. (population[2032 - 1950])

Final population array values at key years:

[0: 0, 25: 1, 30: 1, 35: 0, 40: 0, 44: 1, 45: -1, 49: 1, 50: -1, 70: -1, 82: -1]

3. Finding the maximum population year:

   • Year 1950:
     • currentPop = 0
   • Year 1975:
     • currentPop += population[25] (1) -> currentPop = 1
     • maxPop = 1, maxYear = 1975
   • Year 1980:
     • currentPop += population[30] (1) -> currentPop = 2
     • maxPop = 2, maxYear = 1980
   • Year 1985:
     • currentPop += population[35] (0) -> currentPop = 2
     • maxPop = 2, maxYear = 1980
   • Year 1990:
     • currentPop += population[40] (0) -> currentPop = 2
   • Year 1994:
     • currentPop += population[44] (1) -> currentPop = 3
     • maxPop = 3, maxYear = 1994
   • Year 1995:
     • currentPop += population[45] (-1) -> currentPop = 2
     • maxPop = 3, maxYear = 1994
   • Year 1999:
     • currentPop += population[49] (1) -> currentPop = 3
   • Year 2000:
     • currentPop += population[50] (-1) -> currentPop = 2
   • Year 2020:
     • currentPop += population[70] (-1) -> currentPop = 1
   • Year 2032:
     • currentPop += population[82] (-1) -> currentPop = 0

4. Final result:

   • The earliest year with the maximum population is 1994.

Code

Complexity Analysis

Time Complexity

The time complexity of the algorithm is O(N), where (N) is the number of entries in the logs. This is because we iterate through the logs to populate the population changes and then iterate through the years (which is a constant number of iterations, 101 to find the maximum population.

Space Complexity

The space complexity is O(1) (constant space) because we use a fixed-size array of 101 elements to store the population changes for each year. The size of this array does not change with the input size.