Maximum Population Year

Easy
500.

Maximum Population Year

Maximum Population Year is an easy coding problem on arrays, prefix sum and counting, asked in Amazon interviews.

You are given a 2D array logs where logs[i] = [birth, death] records one person's birth and death years.

A person is counted as alive during every year y with birth <= y < death — the birth year counts, the death year does not.

Return the earliest year with the maximum population.

Example 1

Input
logs = [[1993,1999],[2000,2010]]
Output
1993
Explanation
Population is 1 in 1993-1998 and again in 2000-2009; 1993 is earliest.

Example 2

Input
logs = [[1950,1961],[1960,1971],[1970,1981]]
Output
1960
Explanation
1960 and 1970 both have 2 people alive; 1960 comes first.

Example 3

Input
logs = [[2008,2026]]
Output
2008

Constraints

  • 1 <= logs.length <= 100
  • 1950 <= birth < death <= 2050
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function(logs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Population Year — Solution in Python, Java & C++

Maximum Population Year solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.

Maximum Population Year is an easy coding problem on arrays, prefix sum and counting, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum, Counting
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 2D array logs where logs[i] = [birth, death] records one person's birth and death years.

A person is counted as alive during every year y with birth <= y < death — the birth year counts, the death year does not.

Return the earliest year with the maximum population.

Example 1

Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: Population is 1 in 1993-1998 and again in 2000-2009; 1993 is earliest.

Example 2

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 1960 and 1970 both have 2 people alive; 1960 comes first.

Example 3

Input: logs = [[2008,2026]]
Output: 2008

Constraints

  • 1 <= logs.length <= 100
  • 1950 <= birth < death <= 2050

Hints for Maximum Population Year

  1. Hint 1

    Counting every year for every person is fine at these limits, but there is a cleaner way.

  2. Hint 2

    Record +1 at the birth year and -1 at the death year in a difference array.

  3. Hint 3

    A running prefix sum over the years then gives the live population in each year.

How to solve Maximum Population Year

A birth/death pair is an interval. A difference array turns "add 1 across a range" into two point updates, after which one prefix sweep reveals the population of every year.

Approach

  1. Allocate a delta array indexed by year.
  2. For each log, do delta[birth] += 1 and delta[death] -= 1.
  3. Sweep years 1950 to 2050 accumulating alive += delta[y].
  4. Track the maximum and, because the sweep runs forward and only a strict improvement updates the answer, the earliest year that attains it.

Why it works

The prefix sum of the difference array at year y counts exactly the intervals covering y. The half-open convention [birth, death) matches the -1 being placed at death rather than death + 1.

Complexity

  • Time — O(n + Y) where Y is the year range
  • Space — O(Y)

Pitfalls

  • Decrementing at death + 1 counts people as alive in their death year.
  • Using >= when updating the best year returns the latest tie rather than the earliest.
  • The array must span up to 2050 inclusive — sizing it to 2050 exactly and writing delta[2050] overflows a 2050-length array.

Reference solution

Python

from typing import List

def maximumPopulation(logs: List[List[int]]) -> int:
    delta = [0] * 2101
    for b, d in logs:
        delta[b] += 1
        delta[d] -= 1
    alive = 0
    best = 0
    year = 1950
    for y in range(1950, 2051):
        alive += delta[y]
        if alive > best:
            best = alive
            year = y
    return year

Java

public static int maximumPopulation(int[][] logs) {
    int[] delta = new int[2101];
    for (int[] l : logs) {
        delta[l[0]]++;
        delta[l[1]]--;
    }
    int alive = 0, best = 0, year = 1950;
    for (int y = 1950; y <= 2050; y++) {
        alive += delta[y];
        if (alive > best) { best = alive; year = y; }
    }
    return year;
}

C++

int maximumPopulation(vector<vector<int>>& logs) {
    vector<int> delta(2101, 0);
    for (auto& l : logs) {
        delta[l[0]]++;
        delta[l[1]]--;
    }
    int alive = 0, best = 0, year = 1950;
    for (int y = 1950; y <= 2050; y++) {
        alive += delta[y];
        if (alive > best) { best = alive; year = y; }
    }
    return year;
}

JavaScript

var maximumPopulation = function(logs) {
    const delta = new Array(2101).fill(0);
    for (let i = 0; i < logs.length; i++) {
        delta[logs[i][0]]++;
        delta[logs[i][1]]--;
    }
    let alive = 0, best = 0, year = 1950;
    for (let y = 1950; y <= 2050; y++) {
        alive += delta[y];
        if (alive > best) { best = alive; year = y; }
    }
    return year;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum