Skip to main content
Talentd

Maximum Population Year - Solution & Explanation

EasyArrayCountingPrefix Sum17 min readAsked at: Amazon, Microsoft, Apple +4
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given birth and death years for multiple people. Each log [birth, death] means the person was alive from birth up to but not including death. The task is to determine the year with the highest population. If multiple years share the same population, return the earliest year.

Approach 1: Brute Force Year Population Counting (Time: O(n * R), Space: O(1))

This method directly simulates population counts for every year. For each year in the allowed range (1950–2050 in the problem constraints), iterate through all logs and count how many people are alive in that year. A person contributes to the count if birth ≤ year < death. Track the maximum population seen so far and update the answer when a larger count appears. The implementation is simple and relies only on basic iteration over an array of logs.

The key idea is straightforward counting: evaluate each year independently. While this works well given the small fixed year range, it becomes inefficient if the range grows large because every year scans all logs again. Time complexity is O(n * R) where n is the number of logs and R is the number of candidate years. Space complexity stays O(1) since only a few counters are maintained.

Approach 2: Delta Population Technique (Prefix Sum) (Time: O(n + R), Space: O(R))

The optimized solution treats population changes as events instead of recomputing counts every year. For each log, increment the population at birth and decrement it at death. This creates a difference array where each index represents how the population changes in that year. After recording all changes, run a cumulative sum across the years to reconstruct the population count at each point.

This is a classic application of the prefix sum pattern combined with simple counting. The insight is that births and deaths define boundaries where population changes, so tracking only those transitions avoids repeatedly scanning all logs. After computing the prefix sum, iterate once through the years to find the maximum population and return the earliest year where it occurs.

This approach runs in O(n + R) time: O(n) to record birth/death deltas and O(R) to compute the prefix sum across the year range. Space complexity is O(R) for the difference array. For problems involving frequent range updates and cumulative totals, the delta technique is a powerful pattern.

Recommended for interviews: Interviewers typically expect the delta population (prefix sum) approach. The brute force version demonstrates that you understand the population definition and boundary condition birth ≤ year < death. The prefix sum solution shows stronger algorithmic thinking by converting repeated counting into event-based updates and a single cumulative pass.

Approach 1: Brute Force Year Population Counting

This approach involves iterating over each year in the given range and counting how many people are alive each year. We then find and return the year with the maximum population count. Although this method may seem straightforward, it is inefficient for larger inputs due to the nested iteration over years.

This solution initializes an array to store population counts from 1950 to 2050. It then iterates over each person's birth-death range and increments the population for each year they are alive. Finally, it checks for the maximum population and returns the corresponding year.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of logs and m is the range of years (1950 to 2050).
Space Complexity: O(m), where m is the range of years (1950 to 2050).

Try this approach in the editor →

Approach 2: Delta Population Technique

This optimized method utilizes the concept of Delta Population. Instead of counting each year separately, we increase the population by one on a birth year and decrease it by one on the death year. We then compute the running sum of these changes across the year range to find peaks in population.

This solution utilizes an array to track changes in population for each year. By adding 1 to the birth year and subtracting 1 from the death year, we encode population changes directly. A running sum identifies the period of maximum population.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), n being the number of logs, m is fixed at 101 due to year constraints.
Space Complexity: O(m), utilizing a fixed array size for population deltas.

Try this approach in the editor →

Approach 3: Difference Array

We notice that the range of years is [1950,..2050]. Therefore, we can map these years to an array d of length 101, where the index of the array represents the value of the year minus 1950.

Next, we traverse logs. For each person, we increment d[birth_i - 1950] by 1 and decrement d[death_i - 1950] by 1. Finally, we traverse the array d, find the maximum value of the prefix sum, which is the year with the most population, and add 1950 to get the answer.

The time complexity is O(n), and the space complexity is O(C). Where n is the length of the array logs, and C is the range size of the years, i.e., 2050 - 1950 + 1 = 101.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Year Population Counting

Time Complexity: O(n * m), where n is the number of logs and m is the range of years (1950 to 2050).
Space Complexity: O(m), where m is the range of years (1950 to 2050).

Delta Population Technique

Time Complexity: O(n + m), n being the number of logs, m is fixed at 101 due to year constraints.
Space Complexity: O(m), utilizing a fixed array size for population deltas.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Year Population CountingO(n * R)O(1)Good for understanding the problem or when the year range is very small
Delta Population Technique (Prefix Sum)O(n + R)O(R)Best general solution when many intervals affect cumulative counts

Video Solution

1854 Maximum Population Year | Zero to FAANG Kunal | Assignment Solution | Leetcode • Programmers Zone • 8,539 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Population Year easy or hard?
Maximum Population Year is categorized as an Easy problem on LeetCode. The brute force solution is straightforward, while the prefix sum optimization introduces an important algorithmic pattern used in many interval and range update problems.
Maximum Population Year Python/Java solution
The solution is typically implemented using arrays and prefix sums in Python, Java, C++, or JavaScript. Record +1 at each birth year and -1 at each death year, compute the running total, and track the earliest year with the maximum population.
How to solve Maximum Population Year in O(n)?
Use the delta population technique. For each log, increment a counter at the birth year and decrement at the death year. Then compute a prefix sum across the years to reconstruct the population count. This processes each log once and scans the year range once, giving O(n + R) complexity.
What is the best approach for Maximum Population Year?
The delta population technique using a prefix sum array is the best approach. Instead of counting population for each year repeatedly, record +1 at birth and -1 at death, then compute cumulative sums to get the population per year. This reduces the complexity to O(n + R) where R is the year range.
Is Maximum Population Year asked at Google/Amazon/Meta?
This type of interval counting and prefix sum problem appears frequently in interviews at companies like Amazon and Google. Variations of range updates, event counting, and prefix sum arrays are common interview topics for entry-level and mid-level roles.
What data structure is used in Maximum Population Year?
The common implementation uses an array to store population changes by year. The optimized approach uses a difference array combined with prefix sums to efficiently compute cumulative population counts.
What is the time complexity of Maximum Population Year?
The brute force approach runs in O(n * R) time because it checks every log for every candidate year. The optimized prefix sum solution runs in O(n + R) time by storing population changes and computing a cumulative sum once across the year range.

Ready to solve this problem?

Practice Maximum Population Year with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shifting Letters II