Maximum Population Year — Solution in Python, Java & C++
Maximum Population Year solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Maximum Population Year is an easy coding problem on arrays, prefix sum and counting, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Prefix Sum, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a 2D array logs where logs[i] = [birth, death] records one person's birth and death years.
A person is counted as alive during every year y with birth <= y < death — the birth year counts, the death year does not.
Return the earliest year with the maximum population.
Example 1
Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: Population is 1 in 1993-1998 and again in 2000-2009; 1993 is earliest.
Example 2
Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 1960 and 1970 both have 2 people alive; 1960 comes first.
Example 3
Input: logs = [[2008,2026]]
Output: 2008
Constraints
1 <= logs.length <= 1001950 <= birth < death <= 2050
Hints for Maximum Population Year
Hint 1
Counting every year for every person is fine at these limits, but there is a cleaner way.
Hint 2
Record
+1at the birth year and-1at the death year in a difference array.Hint 3
A running prefix sum over the years then gives the live population in each year.
How to solve Maximum Population Year
A birth/death pair is an interval. A difference array turns "add 1 across a range" into two point updates, after which one prefix sweep reveals the population of every year.
Approach
- Allocate a
deltaarray indexed by year. - For each log, do
delta[birth] += 1anddelta[death] -= 1. - Sweep years 1950 to 2050 accumulating
alive += delta[y]. - Track the maximum and, because the sweep runs forward and only a strict improvement updates the answer, the earliest year that attains it.
Why it works
The prefix sum of the difference array at year y counts exactly the intervals covering y. The half-open convention [birth, death) matches the -1 being placed at death rather than death + 1.
Complexity
- Time —
O(n + Y) where Y is the year range - Space —
O(Y)
Pitfalls
- Decrementing at
death + 1counts people as alive in their death year. - Using
>=when updating the best year returns the latest tie rather than the earliest. - The array must span up to 2050 inclusive — sizing it to 2050 exactly and writing
delta[2050]overflows a 2050-length array.
Reference solution
Python
from typing import List
def maximumPopulation(logs: List[List[int]]) -> int:
delta = [0] * 2101
for b, d in logs:
delta[b] += 1
delta[d] -= 1
alive = 0
best = 0
year = 1950
for y in range(1950, 2051):
alive += delta[y]
if alive > best:
best = alive
year = y
return yearJava
public static int maximumPopulation(int[][] logs) {
int[] delta = new int[2101];
for (int[] l : logs) {
delta[l[0]]++;
delta[l[1]]--;
}
int alive = 0, best = 0, year = 1950;
for (int y = 1950; y <= 2050; y++) {
alive += delta[y];
if (alive > best) { best = alive; year = y; }
}
return year;
}C++
int maximumPopulation(vector<vector<int>>& logs) {
vector<int> delta(2101, 0);
for (auto& l : logs) {
delta[l[0]]++;
delta[l[1]]--;
}
int alive = 0, best = 0, year = 1950;
for (int y = 1950; y <= 2050; y++) {
alive += delta[y];
if (alive > best) { best = alive; year = y; }
}
return year;
}JavaScript
var maximumPopulation = function(logs) {
const delta = new Array(2101).fill(0);
for (let i = 0; i < logs.length; i++) {
delta[logs[i][0]]++;
delta[logs[i][1]]--;
}
let alive = 0, best = 0, year = 1950;
for (let y = 1950; y <= 2050; y++) {
alive += delta[y];
if (alive > best) { best = alive; year = y; }
}
return year;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum