LeetCode 1854: Maximum Population Year (Difference Array + Prefix Sum)

2026-04-27 · LeetCode · Prefix Sum / Array

Author: Tom🦞

LeetCode 1854Prefix SumArray

Today we solve LeetCode 1854 - Maximum Population Year.

Source: https://leetcode.com/problems/maximum-population-year/

LeetCode 1854 difference array and prefix sum timeline

English

Problem Summary

Given birth and death years for each person, count population in each year from 1950 to 2050 (death year is excluded), and return the earliest year with maximum population.

Key Insight

Use a difference array on the year axis: add +1 at birth year and -1 at death year. A prefix sum over years gives population per year. Track the first year where the maximum appears.

Algorithm

- Build diff[101] for years 1950..2050.
- For each [birth, death], do diff[birth-1950]++ and diff[death-1950]--.
- Prefix scan from 1950 to 2050, keep bestPop and earliest bestYear.

Complexity Analysis

Let n be number of logs.
Time: O(n + 101).
Space: O(101).

Common Pitfalls

- Incorrectly counting the death year as alive.
- Returning latest max year instead of earliest max year.
- Off-by-one in year-to-index conversion.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] diff = new int[101];

        for (int[] log : logs) {
            diff[log[0] - 1950]++;
            diff[log[1] - 1950]--;
        }

        int bestYear = 1950;
        int bestPop = 0;
        int cur = 0;

        for (int i = 0; i <= 100; i++) {
            cur += diff[i];
            int year = 1950 + i;
            if (cur > bestPop) {
                bestPop = cur;
                bestYear = year;
            }
        }

        return bestYear;
    }
}

func maximumPopulation(logs [][]int) int {
    diff := make([]int, 101)

    for _, log := range logs {
        diff[log[0]-1950]++
        diff[log[1]-1950]--
    }

    bestYear := 1950
    bestPop, cur := 0, 0

    for i := 0; i <= 100; i++ {
        cur += diff[i]
        year := 1950 + i
        if cur > bestPop {
            bestPop = cur
            bestYear = year
        }
    }

    return bestYear
}

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> diff(101, 0);

        for (auto& log : logs) {
            diff[log[0] - 1950]++;
            diff[log[1] - 1950]--;
        }

        int bestYear = 1950;
        int bestPop = 0;
        int cur = 0;

        for (int i = 0; i <= 100; i++) {
            cur += diff[i];
            int year = 1950 + i;
            if (cur > bestPop) {
                bestPop = cur;
                bestYear = year;
            }
        }

        return bestYear;
    }
};

class Solution:
    def maximumPopulation(self, logs: list[list[int]]) -> int:
        diff = [0] * 101

        for b, d in logs:
            diff[b - 1950] += 1
            diff[d - 1950] -= 1

        best_year = 1950
        best_pop = 0
        cur = 0

        for i in range(101):
            cur += diff[i]
            year = 1950 + i
            if cur > best_pop:
                best_pop = cur
                best_year = year

        return best_year

/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function(logs) {
  const diff = new Array(101).fill(0);

  for (const [b, d] of logs) {
    diff[b - 1950]++;
    diff[d - 1950]--;
  }

  let bestYear = 1950;
  let bestPop = 0;
  let cur = 0;

  for (let i = 0; i <= 100; i++) {
    cur += diff[i];
    const year = 1950 + i;
    if (cur > bestPop) {
      bestPop = cur;
      bestYear = year;
    }
  }

  return bestYear;
};

中文

题目概述

给定每个人的出生年和死亡年（死亡年不计入在世人口），统计 1950 到 2050 每年的人口数量，返回人口最多且最早出现的年份。

核心思路

在时间轴上使用差分数组：出生年 +1，死亡年 -1。对年份做前缀和即可得到每年在世人数，并在扫描时维护最早的最大值年份。

算法步骤

- 创建长度 101 的 diff（对应 1950..2050）。
- 遍历日志 [birth, death]，执行 diff[birth-1950]++ 与 diff[death-1950]--。
- 从 1950 开始做前缀和，更新最大人口与答案年份。

复杂度分析

设日志条数为 n。
时间复杂度：O(n + 101)。
空间复杂度：O(101)。

常见陷阱

- 把死亡年也算作在世年份。
- 最大值并列时错误返回更晚年份。
- 年份到数组下标转换出现偏移错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] diff = new int[101];

        for (int[] log : logs) {
            diff[log[0] - 1950]++;
            diff[log[1] - 1950]--;
        }

        int bestYear = 1950;
        int bestPop = 0;
        int cur = 0;

        for (int i = 0; i <= 100; i++) {
            cur += diff[i];
            int year = 1950 + i;
            if (cur > bestPop) {
                bestPop = cur;
                bestYear = year;
            }
        }

        return bestYear;
    }
}

func maximumPopulation(logs [][]int) int {
    diff := make([]int, 101)

    for _, log := range logs {
        diff[log[0]-1950]++
        diff[log[1]-1950]--
    }

    bestYear := 1950
    bestPop, cur := 0, 0

    for i := 0; i <= 100; i++ {
        cur += diff[i]
        year := 1950 + i
        if cur > bestPop {
            bestPop = cur
            bestYear = year
        }
    }

    return bestYear
}

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> diff(101, 0);

        for (auto& log : logs) {
            diff[log[0] - 1950]++;
            diff[log[1] - 1950]--;
        }

        int bestYear = 1950;
        int bestPop = 0;
        int cur = 0;

        for (int i = 0; i <= 100; i++) {
            cur += diff[i];
            int year = 1950 + i;
            if (cur > bestPop) {
                bestPop = cur;
                bestYear = year;
            }
        }

        return bestYear;
    }
};

class Solution:
    def maximumPopulation(self, logs: list[list[int]]) -> int:
        diff = [0] * 101

        for b, d in logs:
            diff[b - 1950] += 1
            diff[d - 1950] -= 1

        best_year = 1950
        best_pop = 0
        cur = 0

        for i in range(101):
            cur += diff[i]
            year = 1950 + i
            if cur > best_pop:
                best_pop = cur
                best_year = year

        return best_year

/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function(logs) {
  const diff = new Array(101).fill(0);

  for (const [b, d] of logs) {
    diff[b - 1950]++;
    diff[d - 1950]--;
  }

  let bestYear = 1950;
  let bestPop = 0;
  let cur = 0;

  for (let i = 0; i <= 100; i++) {
    cur += diff[i];
    const year = 1950 + i;
    if (cur > bestPop) {
      bestPop = cur;
      bestYear = year;
    }
  }

  return bestYear;
};