Problem Description

You are given a 2D integer array called logs where each logs[i] = [birth_i, death_i) represents the birth and death year of the i^th person. The population of a year y is the number of people alive during year y (i.e., birth_i ≤ y < death_i).

Your task is to return the earliest year with the maximum population.

• Each person is alive from birth_i (inclusive) to death_i (exclusive).
• You are guaranteed that there is exactly one such year with the maximum population.
• All years in logs are in the range [1950, 2050].

Thought Process

At first glance, you might consider counting the population for each year by iterating through every person and every year in their lifespan. This brute-force approach checks, for each year, how many people are alive, then finds the year with the maximum count.

However, this would be inefficient if the range of years or number of people was large. We need an optimized way to update population counts without iterating through every year for every person.

By recognizing that each birth increases the population and each death decreases it, we can efficiently track changes in population using a prefix sum or "sweep line" approach. This reduces the problem to a series of cumulative updates.

Solution Approach

To solve this efficiently, we use the following steps:

1. Initialize a population delta array:
   • Create an array (or map) to represent each year in the range [1950, 2050].
   • For each person's log, increment the population at their birth year and decrement it at their death year.
2. Apply cumulative sum:
   • Iterate through the years in order, maintaining a running sum of the population changes.
   • Track the maximum population and the earliest year it occurs.
3. Return the answer:
   • After processing all years, return the earliest year with the maximum population.

This approach is efficient because each person's lifespan only updates two entries (birth and death), and the cumulative sum aggregates these efficiently.

Example Walkthrough

Let's consider the input: logs = [[1993,1999],[2000,2010]]

1. For the first person (1993-1999):
   • Increment year 1993 by 1
   • Decrement year 1999 by 1
2. For the second person (2000-2010):
   • Increment year 2000 by 1
   • Decrement year 2010 by 1
3. Now, process years from 1950 to 2050, maintaining a running sum:
   • Years 1993-1998: population is 1
   • Years 1999: population drops to 0
   • Years 2000-2009: population is 1
   • Year 2010: population drops to 0
4. The maximum population is 1, and the earliest year it occurs is 1993.

Code Implementation

class Solution:
    def maximumPopulation(self, logs):
        delta = [0] * 101  # years 1950-2050
        for birth, death in logs:
            delta[birth - 1950] += 1
            delta[death - 1950] -= 1
        max_pop = year = curr = 0
        for i in range(101):
            curr += delta[i]
            if curr > max_pop:
                max_pop = curr
                year = 1950 + i
        return year
      

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        int delta[101] = {0}; // years 1950-2050
        for (auto& log : logs) {
            delta[log[0] - 1950]++;
            delta[log[1] - 1950]--;
        }
        int maxPop = 0, curr = 0, year = 1950;
        for (int i = 0; i < 101; ++i) {
            curr += delta[i];
            if (curr > maxPop) {
                maxPop = curr;
                year = 1950 + i;
            }
        }
        return year;
    }
};
      

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] delta = new int[101]; // years 1950-2050
        for (int[] log : logs) {
            delta[log[0] - 1950]++;
            delta[log[1] - 1950]--;
        }
        int maxPop = 0, curr = 0, year = 1950;
        for (int i = 0; i < 101; ++i) {
            curr += delta[i];
            if (curr > maxPop) {
                maxPop = curr;
                year = 1950 + i;
            }
        }
        return year;
    }
}
      

var maximumPopulation = function(logs) {
    let delta = new Array(101).fill(0); // years 1950-2050
    for (let [birth, death] of logs) {
        delta[birth - 1950]++;
        delta[death - 1950]--;
    }
    let maxPop = 0, curr = 0, year = 1950;
    for (let i = 0; i < 101; ++i) {
        curr += delta[i];
        if (curr > maxPop) {
            maxPop = curr;
            year = 1950 + i;
        }
    }
    return year;
};
      

Time and Space Complexity

• Brute-force approach:
  • For each year in [1950, 2050] (101 years), check every person to see if they are alive in that year (O(N) per year).
  • Total time complexity: O(N * 101), where N is the number of people.
  • Space complexity: O(1) extra, aside from input.
• Optimized approach (prefix sum / sweep line):
  • For each person, only two updates (birth and death), so O(N) time.
  • Cumulative sum over 101 years: O(101) time.
  • Total time complexity: O(N + 101), which is effectively O(N) for reasonable N.
  • Space complexity: O(101) = O(1) for the delta array.

Summary

This problem is elegantly solved by recognizing that population changes only at birth and death years, allowing us to use a prefix sum (or sweep line) approach. This reduces unnecessary computations and provides a fast, clear solution. By efficiently tracking population deltas and scanning through the years, we quickly identify the earliest year with the maximum population.