Leetcode 1854: Maximum Population Year
You are given a 2D array
logs where each entry represents the birth and death years of a person. You need to determine the earliest year that has the maximum population, where population is defined as the number of people alive in a given year.Problem
Approach
Steps
Complexity
Input: The input consists of a 2D array `logs` where each element is a list `[birthi, deathi]`, representing the birth and death years of a person.
Example: [[1980, 1990], [1985, 1995], [1990, 2000]]
Constraints:
• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050
Output: Return the earliest year with the maximum population.
Example: 1990
Constraints:
Goal: The goal is to find the earliest year where the population is maximized. This involves counting the number of people alive in each year and finding the year with the highest population.
Steps:
• Use an array to track population changes by year. Increase the population at birth years and decrease it at death years.
• Accumulate population over the years and find the year with the maximum population.
• If there are multiple years with the same population, return the earliest year.
Goal: The array `logs` will contain up to 100 entries, and each person's birth and death years will be between 1950 and 2050.
Steps:
• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050
Assumptions:
• The input array `logs` will always contain valid birth and death years.
• Input: [[1980,1990], [1985,1995], [1990,2000]]
• Explanation: In this example, the population is maximized in the year 1990, as all three people are alive during that year. Hence, the earliest year with the maximum population is 1990.
Approach: To solve this problem, track population changes over time by incrementing the population at birth years and decrementing it at death years. Then, accumulate the population for each year and return the earliest year with the highest population.
Observations:
• We need to calculate population changes for each year and determine the year with the highest population.
• A simple way to approach this is by using an array to track changes in population by year.
Steps:
• Create an array of size 102 (to cover the range of years from 1950 to 2050).
• For each person in the `logs`, increment the population at their birth year and decrement it at their death year.
• Calculate the cumulative population for each year.
• Return the earliest year that has the maximum population.
Empty Inputs:
• There will always be at least one entry in the input array `logs`.
Large Inputs:
• The input array can have up to 100 entries, so the algorithm should handle this efficiently.
Special Values:
• Consider cases where multiple years have the same maximum population.
Constraints:
• Ensure that the solution can handle the range of years from 1950 to 2050 efficiently.
int maximumPopulation(vector<vector<int>>& logs) {
vector<int> sum(102, 0);
for(auto v: logs) {
sum[v[1] - 1950]--;
sum[v[0] - 1950]++;
}
for(int i = 1; i < 102; i++) {
sum[i] += sum[i - 1];
cout << sum[i] << " ";
}
int mx = 0, yr = 2050;
for(int i = 101; i >= 0; i--) {
if(sum[i] >= mx) {
yr = i + 1950;
mx = sum[i];
}
}
return yr;
}
1 : Function Definition
int maximumPopulation(vector<vector<int>>& logs) {
Defines the `maximumPopulation` function that takes a 2D vector `logs` representing the birth and death years of individuals.
2 : Variable Initialization
vector<int> sum(102, 0);
Initializes a vector `sum` of size 102 (for years 1950 to 2050) to track the population changes, with all values initially set to 0.
3 : Looping
for(auto v: logs) {
Iterates through each element `v` in the `logs` vector, where each element represents a pair of birth and death years.
4 : Array Manipulation
sum[v[1] - 1950]--;
Decreases the population at the death year (adjusted for the base year 1950).
5 : Array Manipulation
sum[v[0] - 1950]++;
Increases the population at the birth year (adjusted for the base year 1950).
6 : Looping
for(int i = 1; i < 102; i++) {
A loop that calculates the cumulative population for each year by adding the current value of `sum[i]` to `sum[i - 1]`.
7 : Array Manipulation
sum[i] += sum[i - 1];
Adds the population change at year `i` to the cumulative population up to that year.
8 : Variable Initialization
int mx = 0, yr = 2050;
Initializes `mx` to track the maximum population and `yr` to store the year with the maximum population, initially set to 2050.
9 : Looping
for(int i = 101; i >= 0; i--) {
Starts a loop that runs backward from year 2050 (index 101) to 1950 (index 0) to find the year with the maximum population.
10 : Conditional Check
if(sum[i] >= mx) {
Checks if the population at the current year `i` is greater than or equal to the current maximum population `mx`.
11 : Variable Update
yr = i + 1950;
Updates the year `yr` to the current year (adjusted back to the actual year) when a new maximum population is found.
12 : Variable Update
mx = sum[i];
Updates the maximum population `mx` to the current population at year `i`.
13 : Return
return yr;
Returns the year `yr` that has the maximum population.
Best Case: O(N)
Average Case: O(N)
Worst Case: O(N)
Description: The time complexity is O(N), where N is the number of people in the `logs` array, as we are iterating over each person's birth and death year.
Best Case: O(102)
Worst Case: O(102)
Description: The space complexity is O(102), as we use an array of fixed size to track population changes over the years.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus