Maximum Population Year solution and explanation
Google
9 more videos on this problem
1854 Maximum Population Year | Zero to FAANG Kunal | Assignment Solution | LeetcodeProgrammers Zone · 35:14 · 8K views
Maximum Population Year | Leetcode 1854 | 3 Approaches | Concepts & Questions - 3 | codestorywithMIKcodestorywithMIK · 28:40 · 6K views
1854. Maximum Population Year | LEETCODE EASYcode Explainer · 8:45 · 6K views
Maximum Population Year | LeetCode 1854 | LeetCode Weekly 240 | Java | HindiPepcoding · 20:39 · 5K views
LeetCode Weekly Contest 240 Question 1: Maximum Population YearCoding Ninjas Webinars and Contest Editorials · 10:16 · 4K views
1854. Maximum Population Year (Leetcode Easy)Programming Live with Larry · 3:00 · 2K views
Leetcode 1854 Maximum Population Year - Java Solution Using TreeMapAlgorithmicIQ · 9:23 · 1K views
LeetCode 1854 | Maximum Population Year | Counting Array | JavaSleepy Cracker · 5:10 · 980 views
Line Sweep Algorithm | Leetcode 1854 | Maximum Population Year | CodingSkoolam For Coding · 9:15 · 801 views
Leetcode 1854 Maximum Population Year | Prefix Sum #PrefixSum #Leetcode #datastructures | SurajCareer Campus Pro · 13:28 · 785 views
The problem
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 <= 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.
def maximumPopulation(logs):
years = [0] * 101
for birth, death in logs:
for y in range(birth, death):
years[y - 1950] += 1
max_population = max(years)
return 1950 + years.index(max_population)class Solution {
public int maximumPopulation(int[][] logs) {
int[] years = new int[101];
for (int[] log : logs) {
for (int y = log[0]; y < log[1]; y++) {
years[y - 1950]++;
}
}
int maxPopulation = 0;
int yearWithMaxPopulation = 0;
for (int i = 0; i < years.length; i++) {
if (years[i] > maxPopulation) {
maxPopulation = years[i];
yearWithMaxPopulation = i;
}
}
return yearWithMaxPopulation + 1950;
}
}#include <vector>
using namespace std;
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
int years[101] = {0};
for(auto& log : logs) {
for(int y = log[0]; y < log[1]; ++y) {
years[y - 1950]++;
}
}
int max_population = 0, earliest_year = 0;
for(int y = 0; y < 101; ++y) {
if(years[y] > max_population) {
max_population = years[y];
earliest_year = y;
}
}
return 1950 + earliest_year;
}
};function maximumPopulation(logs) {
const years = new Array(101).fill(0);
for (const [birth, death] of logs) {
for (let y = birth; y < death; y++) {
years[y - 1950]++;
}
}
const maxPopulation = Math.max(...years);
return 1950 + years.indexOf(maxPopulation);
}#include <stdio.h>
#include <string.h>
#define START_YEAR 1950
#define END_YEAR 2050
int maximumPopulation(int logs[][2], int logsSize) {
int population[END_YEAR - START_YEAR] = {0};
for (int i = 0; i < logsSize; i++) {
for (int y = logs[i][0]; y < logs[i][1]; y++) {
population[y - START_YEAR]++;
}
}
int maxPop = 0, year = 0;
for (int y = 0; y < (END_YEAR - START_YEAR); y++) {
if (population[y] > maxPop) {
maxPop = population[y];
year = y;
}
}
return year + START_YEAR;
}public class Solution {
public int MaximumPopulation(int[][] logs) {
int[] years = new int[101];
foreach (var log in logs) {
for (int y = log[0]; y < log[1]; y++) {
years[y - 1950]++;
}
}
int maxPop = 0, earliestYear = 0;
for (int y = 0; y < 101; y++) {
if (years[y] > maxPop) {
maxPop = years[y];
earliestYear = y;
}
}
return 1950 + earliestYear;
}
}The solution uses a Python list to tally populations for each possible year. It then iterates over each lifespan indicated in logs, adding to the yearly populations. Finally, it finds the maximum population and correlates that to the correct year to return.
Time Complexity: O(n * m), n is the count of logs, and m covers 101 years.
Space Complexity: O(m), utilizing an array for years 1950 - 2050.
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.
def maximumPopulation(logs):
delta = [0] * 101
for birth, death in logs:
delta[birth - 1950] += 1
delta[death - 1950] -= 1
max_population = current_population = 0
year_with_max_population = 0
for i in range(101):
current_population += delta[i]
if current_population > max_population:
max_population = current_population
year_with_max_population = i
return 1950 + year_with_max_populationclass Solution {
public int maximumPopulation(int[][] logs) {
int[] delta = new int[101];
for (int[] log : logs) {
delta[log[0] - 1950]++;
delta[log[1] - 1950]--;
}
int maxPopulation = 0, currentPopulation = 0, year = 0;
for (int i = 0; i < 101; i++) {
currentPopulation += delta[i];
if (currentPopulation > maxPopulation) {
maxPopulation = currentPopulation;
year = i;
}
}
return 1950 + year;
}
}#include <vector>
using namespace std;
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
int delta[101] = {0};
for (const auto& log : logs) {
delta[log[0] - 1950]++;
delta[log[1] - 1950]--;
}
int max_population = 0, current_population = 0, year = 0;
for (int y = 0; y < 101; ++y) {
current_population += delta[y];
if (current_population > max_population) {
max_population = current_population;
year = y;
}
}
return 1950 + year;
}
};function maximumPopulation(logs) {
const delta = new Array(101).fill(0);
logs.forEach(([birth, death]) => {
delta[birth - 1950]++;
delta[death - 1950]--;
});
let maxPopulation = 0, year = 0, currentPopulation = 0;
for (let i = 0; i < 101; i++) {
currentPopulation += delta[i];
if (currentPopulation > maxPopulation) {
maxPopulation = currentPopulation;
year = i;
}
}
return 1950 + year;
}#include <stdio.h>
#define YEAR_RANGE 101
#define START_YEAR 1950
int maximumPopulation(int logs[][2], int logsSize) {
int delta[YEAR_RANGE] = {0};
for (int i = 0; i < logsSize; i++) {
int birthYear = logs[i][0], deathYear = logs[i][1];
delta[birthYear - START_YEAR]++;
delta[deathYear - START_YEAR]--;
}
int maxPop = 0, currentPop = 0, year = 0;
for (int i = 0; i < YEAR_RANGE; i++) {
currentPop += delta[i];
if (currentPop > maxPop) {
maxPop = currentPop;
year = i;
}
}
return START_YEAR + year;
}public class Solution {
public int MaximumPopulation(int[][] logs) {
int[] delta = new int[101];
foreach (var log in logs) {
delta[log[0] - 1950]++;
delta[log[1] - 1950]--;
}
int maxPop = 0, currentPop = 0, year = 0;
for (int i = 0; i < 101; i++) {
currentPop += delta[i];
if (currentPop > maxPop) {
maxPop = currentPop;
year = i;
}
}
return 1950 + year;
}
}The delta approach in Python uses a list to mark starting and ending changes in population, reflecting calendar years minus 1950. The cumulative tally helps pinpoint the heavily populated year range effectively.
Time Complexity: O(n + m), where n is logs count and m fixed years check.
Space Complexity: O(m), with m indexing the limited array size for 101 years.
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.
function maximumPopulation(logs: number[][]): number {
const d: number[] = new Array(101).fill(0);
const offset = 1950;
for (const [birth, death] of logs) {
d[birth - offset]++;
d[death - offset]--;
}
let j = 0;
for (let i = 0, s = 0, mx = 0; i < d.length; ++i) {
s += d[i];
if (mx < s) {
mx = s;
j = i;
}
}
return j + offset;
}func maximumPopulation(logs [][]int) int {
d := [101]int{}
offset := 1950
for _, log := range logs {
a, b := log[0]-offset, log[1]-offset
d[a]++
d[b]--
}
var s, mx, j int
for i, x := range d {
s += x
if mx < s {
mx = s
j = i
}
}
return j + offset
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Year Population Counting | Time Complexity: O(n * m), n is the count of logs, and m covers 101 years. |
| Delta Population Technique | Time Complexity: O(n + m), where n is logs count and m fixed years check. |
| Difference Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Year Population Counting | O(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 |
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.