LeetCode 1854. Maximum Population Year Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.

 

Constraints:

• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050

Solutions

Solution 1: Difference Array

We notice that the range of years is [1950,..2050]. Therefore, we can map these years to an array d of length 101, where the index of the array represents the value of the year minus 1950.

Next, we traverse logs. For each person, we increment d[birth_i - 1950] by 1 and decrement d[death_i - 1950] by 1. Finally, we traverse the array d, find the maximum value of the prefix sum, which is the year with the most population, and add 1950 to get the answer.

The time complexity is O(n), and the space complexity is O(C). Where n is the length of the array logs, and C is the range size of the years, i.e., 2050 - 1950 + 1 = 101.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def maximumPopulation(self, logs: List[List[int]]) -> int: d = [0] * 101 offset = 1950 for a, b in logs: a, b = a - offset, b - offset d[a] += 1 d[b] -= 1 s = mx = j = 0 for i, x in enumerate(d): s += x if mx < s: mx, j = s, i return j + offset(code-box)

class Solution { public int maximumPopulation(int[][] logs) { int[] d = new int[101]; final int offset = 1950; for (var log : logs) { int a = log[0] - offset; int b = log[1] - offset; ++d[a]; --d[b]; } int s = 0, mx = 0; int j = 0; for (int i = 0; i < d.length; ++i) { s += d[i]; if (mx < s) { mx = s; j = i; } } return j + offset; } }(code-box)

class Solution { public: int maximumPopulation(vector<vector<int>>& logs) { int d[101]{}; const int offset = 1950; for (auto& log : logs) { int a = log[0] - offset; int b = log[1] - offset; ++d[a]; --d[b]; } int s = 0, mx = 0; int j = 0; for (int i = 0; i < 101; ++i) { s += d[i]; if (mx < s) { mx = s; j = i; } } return j + offset; } };(code-box)

func maximumPopulation(logs [][]int) int { d := [101]int{} offset := 1950 for _, log := range logs { a, b := log[0]-offset, log[1]-offset d[a]++ d[b]-- } var s, mx, j int for i, x := range d { s += x if mx < s { mx = s j = i } } return j + offset }(code-box)

function maximumPopulation(logs: number[][]): number { const d: number[] = new Array(101).fill(0); const offset = 1950; for (const [birth, death] of logs) { d[birth - offset]++; d[death - offset]--; } let j = 0; for (let i = 0, s = 0, mx = 0; i < d.length; ++i) { s += d[i]; if (mx < s) { mx = s; j = i; } } return j + offset; }(code-box)

/** * @param {number[][]} logs * @return {number} */ var maximumPopulation = function (logs) { const d = new Array(101).fill(0); const offset = 1950; for (let [a, b] of logs) { a -= offset; b -= offset; d[a]++; d[b]--; } let j = 0; for (let i = 0, s = 0, mx = 0; i < 101; ++i) { s += d[i]; if (mx < s) { mx = s; j = i; } } return j + offset; };(code-box)