Maximum Population Year

You are given a 2D integer array logs where logs[i] = [birthi, deathi] represents the birth and death years of the ith person. A person is counted in the population of every year from their birth year up to (but not including) their death year. Return the earliest year with the maximum population.

This is LeetCode 1854: Maximum Population Year, an easy problem that is a clean introduction to the difference array technique. Instead of looping through every year a person is alive, you mark just the birth and death boundaries and let a prefix sum do the rest.

Why this problem matters

Maximum Population Year is one of the simplest problems that teaches the difference array pattern. The brute force approach loops through every year between each person's birth and death, incrementing a counter. If there are n people and the year range is m, that costs O(n * m). The difference array approach reduces this to O(n + m) by recording only the start and end of each person's lifetime.

This same pattern shows up in harder problems like Car Pooling, flight booking totals, and meeting room scheduling. Learning it here on an easy problem means you can apply it instantly when you see it in a medium or hard.

The problem also reinforces the connection between difference arrays and prefix sums. A difference array records changes at boundaries. A prefix sum reconstructs the actual values from those changes. Together they form one of the most versatile pairs of techniques in array problems.

The key insight

For each person [birth, death], you only need two operations on a difference array:

• Add +1 at the birth year (this person starts being alive)
• Subtract -1 at the death year (this person is no longer alive)

After processing all people, compute the prefix sum of the difference array. At each year, the running sum tells you exactly how many people are alive. Scan from left to right and return the first year where the population is at its maximum.

The critical detail is that a person is alive from birth to death - 1 inclusive. They are not alive in the death year. This is why you subtract at death, not at death + 1.

The solution

def maximumPopulation(logs):
    diff = [0] * 101  # years 1950 to 2050
    for birth, death in logs:
        diff[birth - 1950] += 1
        diff[death - 1950] -= 1

    max_pop = 0
    max_year = 1950
    current = 0
    for i in range(101):
        current += diff[i]
        if current > max_pop:
            max_pop = current
            max_year = 1950 + i
    return max_year

The solution has two phases. First, you build the difference array by iterating through every person and recording the +1 at birth and -1 at death. Second, you sweep through the array computing a running sum. This running sum is the population at each year. You track the maximum and the earliest year it occurs.

The problem constrains years to the range [1950, 2050], so a fixed-size array of 101 elements works. You offset each year by subtracting 1950 to get a 0-based index.

Visual walkthrough

The walkthrough uses logs = [[1,4],[2,6],[3,5]] for clarity. After building the difference array, the prefix sum reveals that year 3 has the maximum population of 3. Since no earlier year ties it, the answer is 3.

Complexity analysis

Time: O(n + m) where n is the number of people and m is the year range (101 in this problem). You iterate through all n people to build the difference array (O(n)), then sweep through m years to compute prefix sums (O(m)).

Space: O(m) for the difference array. Since the year range is fixed at 101 in this problem, you can treat this as O(1), but conceptually it scales with the year range.

The building blocks

1. Difference array for range updates

The difference array is a technique for applying range updates in O(1) per update. Instead of modifying every element in a range, you modify only the endpoints:

diff[start] += 1
diff[end] -= 1

After all updates, a prefix sum over diff gives you the actual values. This is the core building block behind maximum population year, car pooling, flight booking problems, and any scenario where you add a constant to a contiguous subarray many times.

2. Prefix sum scan

The prefix sum converts the difference array back into actual population counts:

current = 0
for i in range(len(diff)):
    current += diff[i]

At each step, current holds the sum of all differences up to that index, which equals the total number of people alive. The prefix sum is one of the most versatile building blocks in algorithm problems, appearing in subarray sums, range queries, and cumulative statistics.

3. Tracking the maximum during a scan

Rather than building the full prefix sum array and then scanning for the max, you can track the maximum in a single pass:

max_pop = 0
max_year = 1950
current = 0
for i in range(101):
    current += diff[i]
    if current > max_pop:
        max_pop = current
        max_year = 1950 + i

Using strict greater-than (>) instead of greater-than-or-equal (>=) ensures you keep the earliest year when there is a tie.

Edge cases

• One person: logs = [[1990, 2000]] means every year from 1990 to 1999 has population 1. Return 1990 since it is the earliest.
• All people share the same years: logs = [[2000, 2010], [2000, 2010]] gives population 2 for years 2000 through 2009. Return 2000.
• No overlap at all: each person lives in a completely separate range. The max population is 1 and the answer is the birth year of the person born earliest.
• Tie for max population: when multiple years share the same maximum, return the smallest year. The left-to-right scan with strict > handles this automatically.
• Person alive for exactly one year: [2000, 2001] means the person is alive only in year 2000. The +1 at 2000 and -1 at 2001 correctly captures this single year.

Common mistakes

1. Off-by-one at death year. The person is not alive in the death year. You subtract at death, not death - 1. A person with [1990, 2000] is alive during 1990 through 1999, so the -1 goes at index 2000.

2. Using >= instead of > for tracking the max. If you update the max year whenever the population is greater than or equal to the current max, you will return the latest year with the max population instead of the earliest. Use strict >.

3. Forgetting the year offset. The problem uses years in the range [1950, 2050]. If you forget to subtract 1950 when indexing into the difference array, you will need an array of size 2051 and waste space.

From understanding to recall

Maximum Population Year is a gentle introduction to difference arrays, but the details still matter. Where exactly do you subtract? Do you use > or >= for the max check? How do you convert between year and array index? These small decisions are exactly where interview mistakes happen.

Solving the problem once teaches you the concept. Revisiting it through spaced repetition turns the concept into a reflex. The next time you face a range-update problem, whether it is car pooling, flight bookings, or meeting room scheduling, you will not waste time rediscovering the difference array. You will jump straight to the two-line update and single-pass scan.

Related posts

• Range Sum Query Immutable - Prefix sums for fast range queries, the read-side counterpart to the difference array
• Car Pooling - The same difference array technique applied to tracking passengers at stops along a route
• Meeting Rooms II - Count overlapping intervals to find the minimum number of conference rooms

CodeBricks breaks the maximum population year LeetCode problem into its difference array and prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a range update question comes up in your interview, you do not hesitate. You just write it.