Maximum Population Year - Practice Coding Problems

Maximum Population Year - 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.

Input & Output

Example 1 — Basic Case

$ Input: logs = [[1993,1999],[2000,2010]]

› Output: 1993

💡 Note: Person 1 lived from 1993-1998 (not counting 1999). Person 2 lived from 2000-2009. Each year has population 1, so return earliest year 1993.

Example 2 — Overlapping Lives

$ Input: logs = [[1950,1961],[1960,1971],[1970,1981]]

› Output: 1960

💡 Note: Years 1960-1970 have 2 people alive (persons 1&2 overlap in 1960, persons 2&3 overlap in 1970). Return earliest year with max population: 1960.

Example 3 — Single Person

$ Input: logs = [[2000,2050]]

› Output: 2000

💡 Note: Only one person alive from 2000-2049. Population is 1 for all these years, return earliest: 2000.

Constraints

1 ≤ logs.length ≤ 100
1950 ≤ birth_i < death_i ≤ 2050

Visualization

Tap to expand

Understanding the Visualization

Input

Array of [birth, death] pairs for each person

Process

Track population changes using events

Output

Earliest year with maximum population

Key Takeaway

🎯 Key Insight: Use difference arrays to efficiently track population changes at specific events rather than checking every year

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a difference array to efficiently track population changes at birth and death events rather than checking every year individually. The prefix sum approach processes all population changes in O(n + y) time where n is the number of people and y is the year range. Time: O(n), Space: O(1) for the optimal solution.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × y)	O(1)	Check population count for every year from 1950 to 2050
Difference Array (Prefix Sum)	O(n + y)	O(y)	Use events to track population changes efficiently

Brute Force — Algorithm Steps

Iterate through each year from 1950 to 2050
For each year, count people alive by checking if year is in [birth, death-1]
Track maximum population and earliest year with max population

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Birth and death years for each person

Check Each Year

Count people alive in each year

Find Maximum

Return earliest year with max population

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int logs[][2], int n) {
    int maxPopulation = 0;
    int resultYear = 1950;
    
    for (int year = 1950; year <= 2050; year++) {
        int population = 0;
        for (int i = 0; i < n; i++) {
            int birth = logs[i][0];
            int death = logs[i][1];
            if (birth <= year && year < death) {
                population++;
            }
        }
        
        if (population > maxPopulation) {
            maxPopulation = population;
            resultYear = year;
        }
    }
    
    return resultYear;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int logs[1000][2];
    int n = 0;
    char *ptr = line + 1;
    
    while (*ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            logs[n][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            logs[n][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            n++;
        }
        ptr++;
    }
    
    int result = solution(logs, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × y)

For each of y years (101 years), we check all n people

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track max population and year

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler