algoadvance

Leetcode 1854. Maximum Population Year

Problem Statement

The problem “Maximum Population Year” requires us to determine the year between 1950 and 2050 that has the maximum population. We are given an array of logs where logs[i] = [birthi, deathi] indicates the birth and death years of the i-th person. The population includes the year of birth but not the year of death.

Requirements:

Clarifying Questions

  1. Q: Are the birth and death years inclusive?
    • A: The birth year is inclusive, but the death year is not. A person is considered alive in the birth year and up to but not including the death year.
  2. Q: How large can the input array logs be?
    • A: The typical constraint for LeetCode problems will apply, with up to (10^4) entries in the logs array.
  3. Q: Should we handle abnormal inputs, such as years outside 1950-2050?
    • A: No, the input will be constrained within the given boundaries.

Strategy

  1. Use an array populationChange with a size corresponding to the year range (e.g., index 0 for 1950 and index 100 for 2050).
  2. For each log entry [birthi, deathi], increment the array at the index representing birthi and decrement the array at the index representing deathi.
  3. Compute the running sum of the populationChange array to get the population for each year.
  4. Find the year with the maximum population. If multiple years have the same population, return the earliest one.

Code

public class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] populationChange = new int[101]; // From 1950 to 2050, hence 101 elements
        
        for (int[] log : logs) {
            int birth = log[0];
            int death = log[1];
            populationChange[birth - 1950]++;
            if (death <= 2050) {
                populationChange[death - 1950]--;
            }
        }
        
        int maxPopulation = 0;
        int maxYear = 1950;
        int currentPopulation = 0;
        
        for (int year = 0; year < 101; year++) {
            currentPopulation += populationChange[year];
            if (currentPopulation > maxPopulation) {
                maxPopulation = currentPopulation;
                maxYear = 1950 + year;
            }
        }
        
        return maxYear;
    }
}

Time Complexity

The time complexity of this solution is (O(n + m)) where:

Thus, this solution is linear relative to the number of entries, making it very efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI