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

Counting Prefix Sum

Data structures

Array

Companies

PayPal Zoho

Prompt

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i^th person.

The population of some year x is the number of people alive during that year. The i^th person is counted in year x's population if x is in the inclusive range [birth_i, death_i - 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 <= birth_i < death_i <= 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.

1class Solution {2    public int maximumPopulation(int[][] logs) {3        int maxPopulation = 0;4        int resultYear = 0;5 6        // Iterate through each year from 1950 to 20507        for (int year = 1950; year <= 2050; year++) {8            int currentPopulation = 0;9            // For each year, check all logs10            for (int[] log : logs) {11                int birth = log[0];12                int death = log[1];13                // A person is alive if the current year is in [birth, death - 1]14                if (year >= birth && year < death) {15                    currentPopulation++;16                }17            }18 19            // If we find a new maximum population, update our result20            if (currentPopulation > maxPopulation) {21                maxPopulation = currentPopulation;22                resultYear = year;23            }24        }25        return resultYear;26    }27}

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.

A more efficient approach uses a difference array, a technique often associated with sweep-line algorithms. Instead of calculating the population for each year from scratch, we record the changes in population at birth and death years. A birth year marks a +1 change, and a death year marks a -1 change. By calculating a running sum of these changes, we can find the population for any year efficiently.

Algorithm

Create an integer array populationChanges of size 101, initialized to all zeros. This array will map years 1950-2050 to indices 0-100.
Iterate through each log [birth, death] in logs.
For each log, increment populationChanges[birth - 1950] and decrement populationChanges[death - 1950].
Initialize maxPopulation = 0, resultYear = 1950, and currentPopulation = 0.
Iterate from i = 0 to 100 (representing years 1950 to 2050).
Add populationChanges[i] to currentPopulation.
If currentPopulation > maxPopulation, update maxPopulation = currentPopulation and resultYear = 1950 + i.
Return resultYear.

Walkthrough

The constraints specify that years are within the range [1950, 2050]. We can create an array, let's call it populationChanges, of size 101 (or slightly larger to be safe) to represent this range. The index i of this array will correspond to the year 1950 + i.

We first iterate through the logs array. For each person [birth, death]:

We increment the value at the index corresponding to their birth year (birth - 1950).
We decrement the value at the index corresponding to their death year (death - 1950).

This populationChanges array now stores the net change in population for each year.

Next, we iterate through the populationChanges array from the beginning, maintaining a currentPopulation running sum.

For each year (index i), we add populationChanges[i] to currentPopulation. This gives us the total population for the year 1950 + i.

We compare this currentPopulation with our maxPopulation seen so far. If it's greater, we update maxPopulation and the resultYear.

This method processes all birth and death events in two separate passes, which is much faster than the nested loop structure of the brute-force approach.

1class Solution {2    public int maximumPopulation(int[][] logs) {3        // The years range from 1950 to 2050. We need an array to cover this range.4        // The size will be 2051 - 1950 = 101.5        int[] populationChanges = new int[101];6        int minYear = 1950;7 8        // Record the change in population for each birth and death year.9        for (int[] log : logs) {10            int birthYear = log[0];11            int deathYear = log[1];12            populationChanges[birthYear - minYear]++;13            populationChanges[deathYear - minYear]--;14        }15 16        int maxPopulation = 0;17        int currentPopulation = 0;18        int resultYear = 0;19 20        // Iterate through the years to find the year with max population.21        for (int i = 0; i < populationChanges.length; i++) {22            currentPopulation += populationChanges[i];23            if (currentPopulation > maxPopulation) {24                maxPopulation = currentPopulation;25                resultYear = minYear + i;26            }27        }28 29        return resultYear;30    }31}

Complexity

Time

O(N + Y), where N is the number of logs and Y is the range of years. We make one pass through the logs (O(N)) to populate the difference array and one pass through the year range (O(Y)) to find the maximum population.

Space

O(Y), where Y is the range of years. We need an auxiliary array of size Y (101 in this case) to store the population changes for each year.

Trade-offs

Pros

Significantly more time-efficient than the brute-force approach.
Scales well with a larger number of logs or a wider year range.

Cons

Requires extra space proportional to the range of years.

Solutions

Solution

1class Solution {2public3  int maximumPopulation(int[][] logs) {4    int[] d = new int[101];5    final int offset = 1950;6    for (var log : logs) {7      int a = log[0] - offset;8      int b = log[1] - offset;9      ++d[a];10      --d[b];11    }12    int s = 0, mx = 0;13    int j = 0;14    for (int i = 0; i < d.length; ++i) {15      s += d[i];16      if (mx < s) {17        mx = s;18        j = i;19      }20    }21    return j + offset;22  }23}

1/** * @param {number[][]} logs * @return {number} */ var maximumPopulation =2  function (logs) {3    const d = new Array(101).fill(0);4    const offset = 1950;5    for (let [a, b] of logs) {6      a -= offset;7      b -= offset;8      d[a]++;9      d[b]--;10    }11    let j = 0;12    for (let i = 0, s = 0, mx = 0; i < 101; ++i) {13      s += d[i];14      if (mx < s) {15        mx = s;16        j = i;17      }18    }19    return j + offset;20  };

1class Solution {2public:3  int maximumPopulation(vector<vector<int>> &logs) {4    int d[101]{};5    const int offset = 1950;6    for (auto &log : logs) {7      int a = log[0] - offset;8      int b = log[1] - offset;9      ++d[a];10      --d[b];11    }12    int s = 0, mx = 0;13    int j = 0;14    for (int i = 0; i < 101; ++i) {15      s += d[i];16      if (mx < s) {17        mx = s;18        j = i;19      }20    }21    return j + offset;22  }23};

1class Solution:2    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

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 problem