# Maximum Population Year
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-population-year)
Canonical: https://scaleengineer.com/dsa/problems/maximum-population-year
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Zoho](https://scaleengineer.com/companies/zoho)
---
## 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.

**Constraints:**

* `1 <= logs.length <= 100`
* `1950 <= birthi < deathi <= 2050`

# Approaches
## Brute Force Iteration
This approach involves iterating through every possible year within the given range and, for each year, counting the number of people alive. It's a straightforward simulation of the population count over time.
**Time:** O(Y * N), where Y is the number of years in the range (e.g., 2050 - 1950 + 1) and N is the number of logs. We iterate through each year, and for each year, we iterate through all the logs. · **Space:** O(1), as we only use a few variables to keep track of the maximum population and the result year, regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space, making it memory-efficient.
**Cons:** Inefficient for a large range of years or a large number of logs, as it re-calculates the population for each year from scratch.
### Explanation
The core idea is to check each year from 1950 to 2050. For every year, we iterate through the entire `logs` array.

We maintain a counter for the current year's population. For each person's log `[birth, death]`, we check if the current year falls within their lifespan `[birth, death - 1]`.

If it does, we increment the population counter for the current year.

After checking all people for a given year, we compare the calculated population with the maximum population found so far. If the current year's population is greater, we update the maximum population and store the current year as the result.

Since the problem asks for the *earliest* year, we only update the result year when we find a *strictly* greater population. This ensures that if multiple years have the same maximum population, the first one we encounter (the earliest) is kept.

```java
class Solution {
    public int maximumPopulation(int[][] logs) {
        int maxPopulation = 0;
        int resultYear = 0;

        // Iterate through each year from 1950 to 2050
        for (int year = 1950; year <= 2050; year++) {
            int currentPopulation = 0;
            // For each year, check all logs
            for (int[] log : logs) {
                int birth = log[0];
                int death = log[1];
                // A person is alive if the current year is in [birth, death - 1]
                if (year >= birth && year < death) {
                    currentPopulation++;
                }
            }

            // If we find a new maximum population, update our result
            if (currentPopulation > maxPopulation) {
                maxPopulation = currentPopulation;
                resultYear = year;
            }
        }
        return resultYear;
    }
}
```
### Algorithm
- Initialize `maxPopulation = 0` and `resultYear = 0`.
- Iterate through each year `y` from 1950 to 2050.
- For each `y`, initialize `currentPopulation = 0`.
- Iterate through each log `[birth, death]` in the input `logs`.
- If `y >= birth` and `y < death`, increment `currentPopulation`.
- After iterating through all logs, check if `currentPopulation > maxPopulation`.
- If it is, update `maxPopulation = currentPopulation` and `resultYear = y`.
- Return `resultYear` after the outer loop finishes.

## Difference Array (Sweep Line)
A more efficient approach uses a difference array, a technique often associated with sweep-line algorithms. Instead of calculating the population for each year from scratch, we record the changes in population at birth and death years. A birth year marks a +1 change, and a death year marks a -1 change. By calculating a running sum of these changes, we can find the population for any year efficiently.
**Time:** O(N + Y), where N is the number of logs and Y is the range of years. We make one pass through the logs (O(N)) to populate the difference array and one pass through the year range (O(Y)) to find the maximum population. · **Space:** O(Y), where Y is the range of years. We need an auxiliary array of size Y (101 in this case) to store the population changes for each year.
**Pros:** Significantly more time-efficient than the brute-force approach.; Scales well with a larger number of logs or a wider year range.
**Cons:** Requires extra space proportional to the range of years.
### Explanation
The constraints specify that years are within the range [1950, 2050]. We can create an array, let's call it `populationChanges`, of size 101 (or slightly larger to be safe) to represent this range. The index `i` of this array will correspond to the year `1950 + i`.

We first iterate through the `logs` array. For each person `[birth, death]`:
- We increment the value at the index corresponding to their birth year (`birth - 1950`).
- We decrement the value at the index corresponding to their death year (`death - 1950`).

This `populationChanges` array now stores the net change in population for each year.

Next, we iterate through the `populationChanges` array from the beginning, maintaining a `currentPopulation` running sum.

For each year (index `i`), we add `populationChanges[i]` to `currentPopulation`. This gives us the total population for the year `1950 + i`.

We compare this `currentPopulation` with our `maxPopulation` seen so far. If it's greater, we update `maxPopulation` and the `resultYear`.

This method processes all birth and death events in two separate passes, which is much faster than the nested loop structure of the brute-force approach.

```java
class Solution {
    public int maximumPopulation(int[][] logs) {
        // The years range from 1950 to 2050. We need an array to cover this range.
        // The size will be 2051 - 1950 = 101.
        int[] populationChanges = new int[101];
        int minYear = 1950;

        // Record the change in population for each birth and death year.
        for (int[] log : logs) {
            int birthYear = log[0];
            int deathYear = log[1];
            populationChanges[birthYear - minYear]++;
            populationChanges[deathYear - minYear]--;
        }

        int maxPopulation = 0;
        int currentPopulation = 0;
        int resultYear = 0;

        // Iterate through the years to find the year with max population.
        for (int i = 0; i < populationChanges.length; i++) {
            currentPopulation += populationChanges[i];
            if (currentPopulation > maxPopulation) {
                maxPopulation = currentPopulation;
                resultYear = minYear + i;
            }
        }

        return resultYear;
    }
}
```
### Algorithm
- Create an integer array `populationChanges` of size 101, initialized to all zeros. This array will map years 1950-2050 to indices 0-100.
- Iterate through each log `[birth, death]` in `logs`.
- For each log, increment `populationChanges[birth - 1950]` and decrement `populationChanges[death - 1950]`.
- Initialize `maxPopulation = 0`, `resultYear = 1950`, and `currentPopulation = 0`.
- Iterate from `i = 0` to `100` (representing years 1950 to 2050).
- Add `populationChanges[i]` to `currentPopulation`.
- If `currentPopulation > maxPopulation`, update `maxPopulation = currentPopulation` and `resultYear = 1950 + i`.
- Return `resultYear`.

# Solutions
### Java

```java
class Solution {
public
  int maximumPopulation(int[][] logs) {
    int[] d = new int[101];
    final int offset = 1950;
    for (var log : logs) {
      int a = log[0] - offset;
      int b = log[1] - offset;
      ++d[a];
      --d[b];
    }
    int s = 0, mx = 0;
    int j = 0;
    for (int i = 0; i < d.length; ++i) {
      s += d[i];
      if (mx < s) {
        mx = s;
        j = i;
      }
    }
    return j + offset;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} logs * @return {number} */ var maximumPopulation =
  function (logs) {
    const d = new Array(101).fill(0);
    const offset = 1950;
    for (let [a, b] of logs) {
      a -= offset;
      b -= offset;
      d[a]++;
      d[b]--;
    }
    let j = 0;
    for (let i = 0, s = 0, mx = 0; i < 101; ++i) {
      s += d[i];
      if (mx < s) {
        mx = s;
        j = i;
      }
    }
    return j + offset;
  };

```

### CPP

```cpp
class Solution {
public:
  int maximumPopulation(vector<vector<int>> &logs) {
    int d[101]{};
    const int offset = 1950;
    for (auto &log : logs) {
      int a = log[0] - offset;
      int b = log[1] - offset;
      ++d[a];
      --d[b];
    }
    int s = 0, mx = 0;
    int j = 0;
    for (int i = 0; i < 101; ++i) {
      s += d[i];
      if (mx < s) {
        mx = s;
        j = i;
      }
    }
    return j + offset;
  }
};

```

### Python

```python
class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int: d = [0] * 101 offset = 1950 for a, b in logs: a, b = a - offset, b - offset d[a] += 1 d[b] -= 1 s = mx = j = 0 for i, x in enumerate(d): s += x if mx < s: mx, j = s, i return j + offset

```