{x}
blog image

Maximum Population Year

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.

 

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

Solution Explanation: Maximum Population Year

The problem asks to find the earliest year with the maximum population given birth and death years of people. A naive approach would involve iterating through all years and counting the living population for each year, which would have a time complexity of O(n*y), where 'n' is the number of people and 'y' is the range of years. However, a more efficient solution exists using a difference array.

Approach: Difference Array

The core idea is to leverage the difference array technique to efficiently calculate the population for each year. Instead of directly counting the population for each year, we track the changes in population.

  1. Initialization: Create a difference array d of size 101 (representing years 1950 to 2050). We initialize all elements to 0.

  2. Processing Logs: Iterate through the logs array. For each person [birth, death]:

    • Increment d[birth - 1950] by 1. This represents the increase in population at the birth year.
    • Decrement d[death - 1950] by 1. This represents the decrease in population at the death year (note that people are not counted in their death year).

  3. Prefix Sum: Iterate through the difference array d and calculate the prefix sum. The prefix sum at index i represents the population in year 1950 + i.

  4. Finding Maximum Population Year: While calculating the prefix sum, track the maximum population and the corresponding year. Return the earliest year with the maximum population.

Time Complexity: O(n + C), where n is the number of people (length of logs) and C is the range of years (101 in this case). The dominant operations are iterating through logs and calculating the prefix sum, both linear in their respective input sizes.

Space Complexity: O(C), dominated by the size of the difference array d. Since C is a constant (101), the space complexity can be considered O(1).

Code Examples:

The provided code snippets in Python, Java, C++, Go, TypeScript, and JavaScript all implement this difference array approach. They follow these steps closely: initialize the difference array, process the logs to populate the difference array with population changes, compute the prefix sum, and find the earliest year with maximum population. The offset (1950) is used to map years to indices in the difference array.

Example Walkthrough (Python):

Let's trace the Python code with logs = [[1950, 1961], [1960, 1971], [1970, 1981]].

  1. d is initialized as [0] * 101.
  2. Processing the first log [1950, 1961]: d[0] += 1 (d[0] becomes 1), d[11] -= 1 (d[11] becomes -1).
  3. Processing the second log [1960, 1971]: d[10] += 1 (d[10] becomes 1), d[21] -= 1 (d[21] becomes -1).
  4. Processing the third log [1970, 1981]: d[20] += 1 (d[20] becomes 1), d[31] -= 1 (d[31] becomes -1).
  5. The prefix sum calculation finds that the maximum population (2) occurs at index 10 (year 1960), which is then returned.

This approach efficiently solves the problem in linear time, avoiding the need to iterate through all possible years for each person.