algoadvance

Leetcode 1854. Maximum Population Year

Problem Statement

The problem is from LeetCode: “1854. Maximum Population Year.”

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] 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. A person is considered alive during the year x if birth_i <= x < death_i. Note that the person is not alive during the year of their death.

Return the year with the maximum population. If there are multiple years with the same maximum population, return the smallest such year.

Example

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

Clarifying Questions

1. Q: What is the range of years we should consider? A: All years in the logs. Generally, the problems consider years within a reasonable human lifespan.

2. Q: Are the birth and death years inclusive? A: A person is considered alive during the year of birth and up to but not including the year of death.

3. Q: How large can the input be? A: Logs are typically reasonably small due to constraints in competitive programming. Let’s assume n (number of logs) to be in the range of 1 <= n <= 100.

Strategy

1. Use a difference array to count the change in the population over the years.
2. Traverse the difference array to find the year with the maximum population.
3. Utilize an array that spans the possible years to store population changes efficiently.

Steps:

1. Initialize an array, population_changes, large enough to cover all possible years given in the logs.
2. Iterate through each log, updating the population changes for the birth and death years.
3. Use a prefix sum approach to calculate the population year by year.
4. Traverse through the years to find the year with the maximum population.

Code

#include <vector>
#include <algorithm>
using namespace std;

int maxPopulationYear(vector<vector<int>>& logs) {
    const int START_YEAR = 1950;
    const int END_YEAR = 2050;
    vector<int> population_changes(END_YEAR - START_YEAR + 1, 0);

    for(const auto& log : logs) {
        population_changes[log[0] - START_YEAR]++;
        population_changes[log[1] - START_YEAR]--;
    }
    
    int max_population = 0;
    int max_population_year = START_YEAR;
    int current_population = 0;

    for(int year = START_YEAR; year <= END_YEAR; ++year) {
        current_population += population_changes[year - START_YEAR];
        if(current_population > max_population) {
            max_population = current_population;
            max_population_year = year;
        }
    }
    
    return max_population_year;
}

Time Complexity

• Time Complexity: O(n + (end_year - start_year)) where n is the number of logs, and (end_year - start_year) is the range from 1950 to 2050. Since the range is constant, this simplifies to O(n).
• Space Complexity: O(1) extra space outside of the input and the difference array of fixed size.

This approach is efficient and accommodates the provided constraints gracefully.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?