Top K Frequent Elements LeetCode Solution

Problem Statement Top K Frequent Elements LeetCode Solution Says that – Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] …

Read more

Maximum Population Year LeetCode Solution

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 <= 100
  • 1950 <= 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.

Maximum Population Year Leetcode Solution

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 ind

Maximum 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

 

 

 

 

 

 

Maximum Population Year LeetCode Solution

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 …

Read more

Best Meeting Point LeetCode Solution

Problem Statement: Best Meeting Point Leetcode Solution says – Given a m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance. The total travel distance is the sum of the distances between the houses of the friends and the meeting point. The distance is calculated using Manhattan Distance, …

Read more

Minimum Path Sum Leetcode Solution

Problem Statement The Minimum Path Sum LeetCode Solution – “Minimum Path Sum” says that given a n x m grid consisting of non-negative integers and we need to find a path from top-left to bottom right, which minimizes the sum of all numbers along the path. We can only move …

Read more

Translate »