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 a 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 Maximum population Year.
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. So the maximum population year is 1960.
Constraints:
1 <= logs.length <= 1001950 <= birthi< deathi<= 2050
ALGORITHM –
- In order to Find the Maximum Population Year. First, we will focus on the total number population in each year by checking in each interval of the given matrix and will find the maximum count and return the year of maximum value. If the count is the same then we simply return the previous year(earliest year).
Approach for Maximum Population Year LeetCode Solution
– First, we will create one array of size 101 because the constraints of years lie in the range 1950 to 2050.
– after that, we will run a loop from 0 to the length of logs and will increase the count of the array at index(logs[i][o]) by 1 and decrease the count of the array at index (logs[i][1]) by 1
– again we will run a loop from 0 to the length of the array and make one variable prev count and update each element of the array by array+prev and update prev by prev = array[i].
– at last, we will run a loop and find the maximum value in the array and return that particular index(index+1950). Hence find the maximum population year.
Code:
Maximum Population Year Python Leetcode Solution:
class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
arr = [0]*101
for i in range(len(logs)):
arr[logs[i][0]-1950] += 1
arr[logs[i][1]-1950] -= 1
previous = arr[0]
for i in range(1,101):
arr[i] += previous
previous = arr[i]
print(arr)
maxi = 0
ind = 0
for i in range(len(arr)):
if arr[i] > maxi:
maxi = arr[i]
ind = i + 1950
print(maxi)
return indMaximum Population Year Java Leetcode Solution:
class Solution {
public int maximumPopulation(int[][] logs) {
int[] arr = new int[101];
for(int i = 0;i < logs.length;i++){
arr[logs[i][0]-1950] +=1;
arr[logs[i][1]-1950] -=1;
}
int prev = arr[0];
for(int i=1;i<arr.length;i++){
arr[i] += prev;
prev = arr[i];
}
int ind = 0;
int maxi = 0;
for(int i=0;i<arr.length;i++){
if(maxi < arr[i]){
maxi = arr[i];
ind = i+1950;
}
}
return ind;
}
}Complexity Analysis of Maximum Population Year Leetcode Solution:
Time Complexity
The Time Complexity of the above solution is O(n).
Time Complexity
The Space Complexity of the above solution is O(1).
As we have made an array of length = 101. So we can consider it constant