Solution For Maximum Population Year
The Maximum Population Year problem on LeetCode is:
You are given a list of people with their birth and death years. Find the year with the highest population. A person’s lifespan is defined as the number of years between their birth and death years. The year with the highest population is the one in which the maximum number of people were alive.
This can be solved using a simple algorithm:
Create a dictionary to store the count of people alive for each year between the minimum birth year and maximum death year.
Loop through the list of people and for each person, increment the count in the dictionary for each year they were alive.
Find the year with the highest population count in the dictionary.
Return the year with the highest population count.
Here is the python code that implements this algorithm:
def maxPopulationYear(people):
# Create a dictionary to store the count of people alive for each year
population = {}
for person in people:
# Increment the count for each year the person was alive
for year in range(person[0], person[1]):
if year in population:
population[year] += 1
else:
population[year] = 1
# Find the year with the highest population count
max_population = 0
max_year = 0
for year, count in population.items():
if count > max_population:
max_population = count
max_year = year
# Return the year with the highest population count
return max_year
The time complexity of this algorithm is O(N*M) where N is the number of people and M is the range between the minimum birth year and maximum death year. However, if we assume that M is a constant value, then the time complexity becomes O(N).
Overall, this is a simple and efficient solution to the Maximum Population Year problem on LeetCode.
Step by Step Implementation For Maximum Population Year
int maximumPopulationYear(int[][] birthYears, int[][] deathYears) { // sort the arrays by birth year Arrays.sort(birthYears, (a, b) -> a[0] - b[0]); Arrays.sort(deathYears, (a, b) -> a[0] - b[0]); // keep track of the current population and the max population int currPopulation = 0; int maxPopulation = 0; // keep track of the index of the birth year and death year arrays int b = 0; int d = 0; // iterate through the years from 1900 to 2000 for (int year = 1900; year <= 2000; year++) { // if the current year is equal to the birth year at the current index // in the birth year array, increment the population if (year == birthYears[b][0]) { currPopulation += birthYears[b][1]; b++; } // if the current year is equal to the death year at the current index // in the death year array, decrement the population if (year == deathYears[d][0]) { currPopulation -= deathYears[d][1]; d++; } // update the max population if necessary if (currPopulation > maxPopulation) { maxPopulation = currPopulation; } } // return the year with the maximum population return maxPopulation; }
# Enter your code here. Read input from STDIN. Print output to STDOUT # Find the year with the maximum population # We will keep track of the population for each year using a dictionary population = {} # We will go through each person's birth and death year and update the population dictionary accordingly for person in range(n): birth_year = int(input()) death_year = int(input()) for year in range(birth_year, death_year+1): if year in population: population[year] += 1 else: population[year] = 1 # We will find the year with the maximum population max_population = 0 max_year = 0 for year in population: if population[year] > max_population: max_population = population[year] max_year = year # Print the year with the maximum population print(max_year)
The maximum population year is the year with the most people alive. We can find the maximum population year by iterating through all the years and finding the year with the most people alive. var maximumPopulationYear = function(people) { var maxYear = 0; var maxPopulation = 0; for (var i = 0; i < people.length; i++) { var person = people[i]; var birthYear = person[0]; var deathYear = person[1]; var population = deathYear - birthYear + 1; if (population > maxPopulation) { maxYear = birthYear; maxPopulation = population; } } return maxYear; };
The following is a C++ solution for the leetcode problem maximum-population-year: int maximumPopulationYear(vector& years, vector & population) { int max_population = 0; int max_year = 0; for(int i = 0; i < years.size(); i++) { if(population[i] > max_population) { max_population = population[i]; max_year = years[i]; } } return max_year; }
public class Solution { public int MaxPopulationYear(int[][] data) { // your code goes here int max = 0; int year = 0; for(int i = 0; i < data.length; i++) { int population = data[i][0]; int birth = data[i][1]; int death = data[i][2]; if(population > max) { max = population; year = birth; } } return year; } }