Maximum Population Year LeetCode Solution - The Coding Shala

Home >> LeetCode >> Maximum Population Year

 In this post, we will learn how to solve LeetCode's Maximum Population Year Problem and will implement its solution in Java.

Maximum Population Year Problem

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 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 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. The earlier year between them is 1960.

Practice this problem on LeetCode.

LeetCode - Maximum Population Year Java Solution

Approach 1

We can use an array to store the count of persons alive during the given range. 

Java Program: 

class Solution {
    public int maximumPopulation(int[][] logs) {
        // years are between 1950 to 2050
        // we can counts all the alive persons in array of size 101
        
        int[] persons =  new int[101];
        
        // take start and end year from logs
        for(int i = 0; i < logs.length; i++) {
            int start = logs[i][0];
            int end = logs[i][1];
            
            // increase count of persons array in this range
            for(int j = start - 1950; j < end - 1950; j++) {
                persons[j]++;
            }
        }
        
        // find maximum population
        int result = -1;
        int year = -1;
        System.out.println(persons[58]);
        for(int i = 0; i < 101; i++) {
            if(persons[i] > result) {
                result = persons[i];
                year = i;
            }
        }
        
        return year + 1950;
    }
}

Approach 2

The above approach can be improved using Line Sweep Algorithm.

We don't need to store count in the array from start to end. We can just add +1 at the year start index and -1 at the end year index. We can use an array of size 101 or 2051.

In the next step find prefix sum in array the traverse the array and return index that has the maximum value.

Time Complexity: O(n)

Java Program: 

// line sweep algorithm
class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] arr = new int[101];
        
        for(int i = 0; i < logs.length; i++) {
            int start = logs[i][0] - 1950;
            int end = logs[i][1] - 1950;
            arr[start]++;
            arr[end]--;
        }
        
        int res = 0;
        int max = arr[0];
        for(int i = 1; i < 101; i++) {
            arr[i] += arr[i-1];
            if(arr[i] > max) {
                max = arr[i];
                res = i;
            }
        }
        return res+1950;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala