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 <= 1001950 <= birthi < deathi <= 2050In #1854 Maximum Population Year, you are given birth and death years for multiple people and must determine the year with the highest population. A straightforward idea is to simulate the population count for each year within the allowed range and track the maximum.
A more efficient method uses a counting / prefix sum technique. Instead of updating every year in a person's lifespan, record a +1 when someone is born and a -1 when they die (since the death year is not included). By storing these changes in a small array indexed by year and then computing a prefix sum, you can reconstruct the population for each year.
This approach avoids repeated range updates and processes the timeline in linear order. The result is found by scanning the prefix sums to locate the year with the maximum population. The method is efficient because the year range is small and fixed, leading to O(n + range) time complexity and constant extra space relative to the year span.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Year Simulation | O(n * range) | O(range) |
| Counting + Prefix Sum | O(n + range) | O(range) |
The Code Skool
Use these hints if you're stuck. Try solving on your own first.
For each year find the number of people whose birth_i ≤ year and death_i > year.
Find the maximum value between all years.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to efficiently compute cumulative population changes over time. Instead of updating every year in a person's lifespan, you record only the start and end changes and reconstruct totals with a single pass.
Yes, this problem is commonly used in interviews to test understanding of prefix sums, difference arrays, and range updates. It also evaluates a candidate's ability to optimize brute-force counting solutions.
A simple array works best because the year range is small and fixed. The array stores population changes, and a prefix sum pass reconstructs the population count for each year.
The optimal approach uses a counting array combined with a prefix sum. By marking population changes at birth and death years and computing cumulative sums, you can efficiently determine the year with the highest population.