Code Logo

Maximum Population Year

Published at24 Jul 2026
Created by
Easy 0 views
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

Find the year with the maximum population from logs of birth and death years. Use a difference array approach: mark +1 for birth years and -1 for death years. Then compute running sum to get population for each year, tracking the year with the maximum.

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

The difference array records changes at each year boundary. The running sum computes the actual population. This avoids O(n * range) pairwise comparison.

Time O(n + range), Space O(range).

Best Answers

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;
    }
}