Problem

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 that they die.

Return the earliest year with the maximum population.

Examples

Example 1:

1
2
3

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:

1
2
3
4
5

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

Solution

Method 1 - Track the max pop

To solve the problem:

  1. Observation:
    • Each person contributes to population from their birth year (birthi) to one year before their death (deathi - 1).
    • To efficiently compute populations across years, we can utilise a difference array approach.
  2. Approach:
    • Step 1: Initialise an array (population) large enough to encompass all possible years, assuming a bounded range of years.
    • Step 2: For each person:
      • Increment the population for birthi.
      • Decrement the population for deathi (marking the end of their contribution).
    • Step 3: Perform a prefix sum over the population array to calculate the population for individual years.
    • Step 4: Iterate over the population array to identify the year with the maximum population. If there are ties, select the earliest year.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {

    public int maximumPopulation(int[][] logs) {
        int[] population = new int[2051]; // Array to keep track of year populations (max year range 1950-2050 inclusive)

        for (int[] log : logs) {
            int birthYr = log[0];
            int deathYr = log[1];
            population[birthYr]++; // Increment population when person is born
            population[deathYr]--; // Decrement population in year they stop contributing
        }

        int ans = 0, maxPop = 0, currPop = 0;
        for (int year = 1950; year < 2051; year++) {
            currPop += population[year]; // Prefix sum to calculate population during year
            if (currPop > maxPop) {
                maxPop = currPop;
                ans = year; // Update earliest year with maximum population
            }
        }

        return ans; // Return the earliest year with maximum population
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        population: List[int] = [0] * 2051  # Array to store year-wise population change (max year range 1950-2050)

        for birth, death in logs:
            population[birth] += 1  # Increment population for birth year
            population[death] -= 1  # Decrement population for death year

        ans: int = 0
        max_pop: int = 0
        curr_pop: int = 0
        for year in range(1950, 2051):
            curr_pop += population[year]  # Calculate current population using prefix sum
            if curr_pop > max_pop:
                max_pop = curr_pop
                ans = year  # Update answer with earliest year having maximum population
        
        return ans  # Return the earliest year with maximum population

Complexity

  • ⏰ Time complexity: O(n + R):
    • O(n) to process all logs to update the difference array.
    • O(R) for prefix sum and finding maximum population, where R is the range of years.
  • 🧺 Space complexity: O(R):
    • Array size corresponds to the number of years covered (usually within range [1950, 2050]).