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

• LeetCode - Incremental Memory Leak
• LeetCode - Goat Latin
• LeetCode - Richest Customer Wealth
• LeetCode - Number of Recent Calls
• LeetCode - Number of Steps to Reduce a Number to Zero

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