Scale Engineer

Maximum Population Year

Easy
#1693Time: O(Y * N), where Y is the number of years in the range (e.g., 2050 - 1950 + 1) and N is the number of logs. We iterate through each year, and for each year, we iterate through all the logs.Space: O(1), as we only use a few variables to keep track of the maximum population and the result year, regardless of the input size.2 companies
Patterns
CountingPrefix Sum
Data structures
Array
Companies
PayPalZoho

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every possible year within the given range and, for each year, counting the number of people alive. It's a straightforward simulation of the population count over time.

Algorithm

  • Initialize maxPopulation = 0 and resultYear = 0.
  • Iterate through each year y from 1950 to 2050.
  • For each y, initialize currentPopulation = 0.
  • Iterate through each log [birth, death] in the input logs.
  • If y >= birth and y < death, increment currentPopulation.
  • After iterating through all logs, check if currentPopulation > maxPopulation.
  • If it is, update maxPopulation = currentPopulation and resultYear = y.
  • Return resultYear after the outer loop finishes.

Walkthrough

The core idea is to check each year from 1950 to 2050. For every year, we iterate through the entire logs array.

We maintain a counter for the current year's population. For each person's log [birth, death], we check if the current year falls within their lifespan [birth, death - 1].

If it does, we increment the population counter for the current year.

After checking all people for a given year, we compare the calculated population with the maximum population found so far. If the current year's population is greater, we update the maximum population and store the current year as the result.

Since the problem asks for the earliest year, we only update the result year when we find a strictly greater population. This ensures that if multiple years have the same maximum population, the first one we encounter (the earliest) is kept.

class Solution {    public int maximumPopulation(int[][] logs) {        int maxPopulation = 0;        int resultYear = 0;         // Iterate through each year from 1950 to 2050        for (int year = 1950; year <= 2050; year++) {            int currentPopulation = 0;            // For each year, check all logs            for (int[] log : logs) {                int birth = log[0];                int death = log[1];                // A person is alive if the current year is in [birth, death - 1]                if (year >= birth && year < death) {                    currentPopulation++;                }            }             // If we find a new maximum population, update our result            if (currentPopulation > maxPopulation) {                maxPopulation = currentPopulation;                resultYear = year;            }        }        return resultYear;    }}

Complexity

Time

O(Y * N), where Y is the number of years in the range (e.g., 2050 - 1950 + 1) and N is the number of logs. We iterate through each year, and for each year, we iterate through all the logs.

Space

O(1), as we only use a few variables to keep track of the maximum population and the result year, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space, making it memory-efficient.

Cons

  • Inefficient for a large range of years or a large number of logs, as it re-calculates the population for each year from scratch.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem