Maximum Population Year

Published at24 Jul 2026

Like0

You are given a list of logs where each log [birth, death] indicates a person born in birth and died in death. Population in a year is the number of people alive in that year. A person is counted in year x if birth <= x < death (not including death year). Find the earliest year with the maximum population.

The years range from 1950 to 2050 (101 years). Use a difference array of size 101: for each person, increment at birth-1950 and decrement at death-1950. Then compute prefix sums to get population at each year. Track the year with max population.

This is a classic prefix sum / difference array DP problem. The O(n) prefix sum over a fixed range gives O(n) time overall. Edge cases include all people in the same year range or a single person.

The difference array technique (marking birth and death years) combined with prefix sums efficiently computes population per year without iterating each year per person. This O(n + 101) approach works well for the fixed 101-year range from 1950 to 2050.

The difference array marks population changes at specific years. Each birth adds a person (+1) and each death removes one (-1). After building this array, a single prefix sum scan computes the actual population for each of the 101 years, and we track the year with the maximum population.

Example Input & Output

Example 1

Input

[[2000,2050]]

Output

2000

Explanation

Single person born 2000.

Example 2

Input

[[1950,1951]]

Output

1950

Explanation

Single person born 1950.

Example 3

Input

[[1980,1990],[1985,1995]]

Output

1985

Explanation

Both alive 1985-1989, max=2 at 1985.

Example 4

Input

[[1950,1961],[1960,1971],[1970,1981]]

Output

1960

Explanation

1960: persons 1&2 alive=2.

Example 5

Input

[[1993,1999],[2000,2010]]

Output

1993

Explanation

1993: person1 alive=1; 2000: person2 alive=1. Earliest max=1993.

Algorithm Flow

Recommendation Algorithm Flow for Maximum Population Year

Solution Approach

Create diff[101], for each log: diff[birth-1950]++, diff[death-1950]--. Prefix sum over diff, track max.

function solution(logs) {
  var years = new Array(101).fill(0);
  for (var i = 0; i < logs.length; i++) {
    years[logs[i][0] - 1950]++;
    if (logs[i][1] < 2050) years[logs[i][1] - 1950]--;
  }
  var maxPop = 0, cur = 0, best = 1950;
  for (var i = 0; i < 101; i++) {
    cur += years[i];
    if (cur > maxPop) { maxPop = cur; best = 1950 + i; }
  }
  return best;
}

Time O(n), Space O(1) fixed 101.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

class Solution {
    public int solution(int[][] logs) {
        int[] years = new int[101];
        for (int[] l : logs) {
            years[l[0] - 1950]++;
            if (l[1] < 2050) years[l[1] - 1950]--;
        }
        int maxPop = 0, cur = 0, best = 1950;
        for (int i = 0; i < 101; i++) {
            cur += years[i];
            if (cur > maxPop) { maxPop = cur; best = 1950 + i; }
        }
        return best;
    }
}

javascript

function solution(logs) {
  var years = new Array(101).fill(0);
  for (var i = 0; i < logs.length; i++) {
    years[logs[i][0] - 1950]++;
    if (logs[i][1] < 2050) years[logs[i][1] - 1950]--;
  }
  var maxPop = 0, cur = 0, best = 1950;
  for (var i = 0; i < 101; i++) {
    cur += years[i];
    if (cur > maxPop) { maxPop = cur; best = 1950 + i; }
  }
  return best;
}

php

<?php
function solution($logs) {
    $years = array_fill(0, 101, 0);
    foreach ($logs as $l) {
        $years[$l[0] - 1950]++;
        if ($l[1] < 2050) $years[$l[1] - 1950]--;
    }
    $maxPop = 0; $cur = 0; $best = 1950;
    foreach ($years as $i => $ch) {
        $cur += $ch;
        if ($cur > $maxPop) { $maxPop = $cur; $best = 1950 + $i; }
    }
    return $best;
}

python

def solution(logs):
    years = [0] * 101
    for birth, death in logs:
        years[birth - 1950] += 1
        if death < 2050:
            years[death - 1950] -= 1
    max_pop = 0
    cur = 0
    best = 1950
    for i, change in enumerate(years):
        cur += change
        if cur > max_pop:
            max_pop = cur
            best = 1950 + i
    return best

rust

fn solution(logs: Vec<Vec<i32>>) -> i32 {
    let mut years = vec![0i32; 101];
    for l in &logs {
        years[(l[0] - 1950) as usize] += 1;
        if l[1] < 2050 { years[(l[1] - 1950) as usize] -= 1; }
    }
    let mut max_pop = 0i32;
    let mut cur = 0i32;
    let mut best = 1950i32;
    for i in 0..101 {
        cur += years[i];
        if cur > max_pop { max_pop = cur; best = 1950 + i as i32; }
    }
    best
}

typescript

function solution(logs: number[][]): number {
    var years: number[] = [];
    for (var i = 0; i < 101; i++) years.push(0);
    for (var i = 0; i < logs.length; i++) {
        years[logs[i][0] - 1950]++;
        if (logs[i][1] < 2050) years[logs[i][1] - 1950]--;
    }
    var maxPop = 0, cur = 0, best = 1950;
    for (var i = 0; i < 101; i++) {
        cur += years[i];
        if (cur > maxPop) { maxPop = cur; best = 1950 + i; }
    }
    return best;
}

Related Dynamic Programming Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Maximum Population Year

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Dynamic Programming Challenges

Garden Lantern Seating Ways

Festival Glow Step Combinations

Evening Harmony Partition Count

Twilight Lantern Garden

Lantern Vowel Pathways

Celestial Pattern Synthesis

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.