Maximum Population Year LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Bloomberg Cisco eBay Facebook Google Microsoft
ArrayViews 4366

Problem Statement:

Maximum Population Year Leetcode Solution says that – 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 the 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:

Input:

 logs = [[1993,1999],[2000,2010]]

Output:

 1993

Explanation:

 The maximum population is 1, and 1993 is the earliest year with this population.

Approach:

Idea:

At first, the problem seems to be a bit difficult, but if you will see the constraints then we can simply brute force the solution. The idea is to check for all the possible years, i.e., find the year for which the maximum number of people were alive.

We will iterate using two loops. One will iterate over all the years ranging from 1950 to 2050 and another loop will be iterating over the logs list. For each year we will check if the current year >= log->birth and year < log->death. This way we will count the population of that year.

Code:

Leetcode Maximum Population Year C++ Solution:

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        int ans = -1;
        int year = 0;
        for(int i=1950;i<2051;i++){
            int population = 0;
            for(int j=0;j<logs.size();j++){
                if(i>=logs[j][0] and i<logs[j][1]){
                    population++;
                }
            }
            if(population!=0 and ans<population){
                ans = population;
                year = i;
            }
        }
        return year;
    }
};

Leetcode Maximum Population Year Python Solution:

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        ans = -1
        year = 0
        for i in range(1950,2051):
            population = 0
            for j in range(len(logs)):
                if i>=logs[j][0] and i<logs[j][1]:
                    population+=1
            if population!=0 and ans<population:
                ans = population
                year = i
        return year

 

Complexity Analysis of Maximum Population Year Leetcode Solution:

  • Time Complexity: The time complexity of the above code is O(n^2) where n in the worst case can be equal to 100. There are two inner loops and both run in O(n) time in the worst case, hence O(n^2) complexity.
  • Space Complexity: The space complexity of the above code is O(1) because we not are using any extra space. Here, we are working with variables only and we aren’t using any extra array to store any kind of information hence, space complexity remains O(1) constant extra space.

Reference: https://en.wikipedia.org/wiki/Array_data_structure

Translate »