Problem Description

You are given information about the birth and death years of multiple people in a 2D array called logs. Each entry logs[i] = [birth_i, death_i] tells you when the i-th person was born and when they died.

Your task is to find which year had the highest population alive. When counting the population for any given year x:

• A person is counted as alive in year x if x is within the range [birth_i, death_i - 1]
• This means a person is alive from their birth year up to (but not including) their death year
• A person who dies in year x is NOT counted in that year's population

If multiple years have the same maximum population, return the earliest year.

For example, if a person has [birth=1950, death=1960], they are counted as alive in years 1950, 1951, 1952, ..., 1959, but NOT in 1960.

The solution uses a difference array technique to efficiently track population changes. Since all years fall within the range [1950, 2050], we can use an array of size 101 where index i represents year 1950 + i. For each person, we mark +1 at their birth year and -1 at their death year. By computing the prefix sum of this array, we can find the population at each year and identify the year with maximum population.

Intuition

The naive approach would be to check each year from 1950 to 2050 and count how many people were alive in that year by iterating through all the logs. This would take O(100 * n) time where n is the number of people.

However, we can think about this problem differently. Instead of counting the population for each year individually, we can track the changes in population. When someone is born, the population increases by 1. When someone dies, the population decreases by 1.

This leads us to the key insight: we only need to mark the events (births and deaths) and then calculate the running population. If we mark +1 for each birth year and -1 for each death year, then the population at any year is simply the sum of all the marks up to that year.

For example, if person A lives from 1950-1955 and person B lives from 1952-1957:

• At year 1950: +1 (A born)
• At year 1952: +1 (B born)
• At year 1955: -1 (A dies)
• At year 1957: -1 (B dies)

The population at any year is the cumulative sum up to that point:

• 1950-1951: population = 1
• 1952-1954: population = 2
• 1955-1956: population = 1
• 1957 onwards: population = 0

This technique is called a "difference array" because we're storing the differences (changes) rather than the actual values. By computing the prefix sum of these differences, we reconstruct the actual population values efficiently in just one pass.

Learn more about Prefix Sum patterns.

Solution Approach

Following the difference array approach, here's how we implement the solution:

1. Initialize the difference array: Create an array d of size 101 to cover all possible years from 1950 to 2050. Each index i represents year 1950 + i. Initialize all values to 0.

2. Mark population changes: For each person in logs:

   • Convert birth and death years to array indices by subtracting 1950 (the offset)
   • Increment d[birth - 1950] by 1 (person becomes alive)
   • Decrement d[death - 1950] by 1 (person dies)

3. Calculate running population: Traverse the array d while maintaining:

   • s: the running sum (current population)
   • mx: the maximum population seen so far
   • j: the index (year) with maximum population

   For each index i:

   • Add d[i] to the running sum s
   • If current population s exceeds mx, update both mx and j

4. Return the result: Add 1950 back to index j to get the actual year

The code implementation:

d = [0] * 101                    # Difference array for years 1950-2050
offset = 1950
for a, b in logs:
    a, b = a - offset, b - offset # Convert to array indices
    d[a] += 1                     # Birth: population increases
    d[b] -= 1                     # Death: population decreases

s = mx = j = 0                    # Running sum, max population, best year
for i, x in enumerate(d):
    s += x                        # Update running population
    if mx < s:                    # Found new maximum
        mx, j = s, i              # Update max and year
return j + offset                 # Convert index back to actual year

This solution runs in O(n) time where n is the number of people, and uses O(1) space since the array size is fixed at 101.

Example Walkthrough

Let's walk through a small example with 3 people:

• Person A: [1952, 1956] (alive in years 1952, 1953, 1954, 1955)
• Person B: [1954, 1958] (alive in years 1954, 1955, 1956, 1957)
• Person C: [1953, 1955] (alive in years 1953, 1954)

Step 1: Initialize difference array We create an array d of size 101 (for years 1950-2050). Initially all zeros.

Step 2: Mark population changes For each person, we mark births (+1) and deaths (-1):

• Person A: d[1952-1950] += 1 → d[2] = 1, and d[1956-1950] -= 1 → d[6] = -1
• Person B: d[1954-1950] += 1 → d[4] = 1, and d[1958-1950] -= 1 → d[8] = -1
• Person C: d[1953-1950] += 1 → d[3] = 1, and d[1955-1950] -= 1 → d[5] = -1

Our difference array now looks like (showing only relevant indices):

Index: 0  1  2  3  4  5  6  7  8
Value: 0  0  1  1  1 -1 -1  0 -1
Year:  50 51 52 53 54 55 56 57 58

Step 3: Calculate running population We traverse the array, maintaining a running sum:

• Index 0-1: sum = 0 (no one alive)
• Index 2: sum = 0 + 1 = 1 (Person A born, population = 1)
• Index 3: sum = 1 + 1 = 2 (Person C born, population = 2)
• Index 4: sum = 2 + 1 = 3 (Person B born, population = 3) ← Maximum!
• Index 5: sum = 3 + (-1) = 2 (Person C dies, population = 2)
• Index 6: sum = 2 + (-1) = 1 (Person A dies, population = 1)
• Index 7: sum = 1 + 0 = 1 (no change)
• Index 8: sum = 1 + (-1) = 0 (Person B dies, population = 0)

The maximum population is 3, occurring at index 4.

Step 4: Return result Index 4 corresponds to year 1950 + 4 = 1954

We can verify: In 1954, all three people are alive (A: 1952-1955, B: 1954-1957, C: 1953-1954), giving us the maximum population of 3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array logs. The algorithm iterates through the logs array once to populate the difference array d with O(n) operations, then iterates through the fixed-size array d of length 101 with O(101) = O(1) operations. Since O(n) + O(1) = O(n), the overall time complexity is O(n).

The space complexity is O(C), where C is the range size of the years, calculated as 2050 - 1950 + 1 = 101. The algorithm creates a fixed-size array d of length 101 to track population changes across all possible years in the given range. Additional variables (s, mx, j, offset) use O(1) space. Therefore, the total space complexity is O(C) = O(101) = O(1) in terms of absolute complexity, but more precisely expressed as O(C) to reflect the dependency on the year range.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Death Year Handling

The most common mistake is misunderstanding when a person is considered alive. Many developers incorrectly count a person as alive during their death year.

Wrong approach:

# INCORRECT: Person counted as alive in death year
population_changes[birth_index] += 1
population_changes[death_index + 1] -= 1  # Wrong! Goes beyond array bounds

Correct approach:

# Person is NOT alive in their death year
population_changes[birth_index] += 1
population_changes[death_index] -= 1  # Correct: person dies at start of death year

2. Array Index Out of Bounds

When dealing with edge cases like death year 2050, attempting to mark death_index + 1 would cause an index error since our array only goes up to index 100.

Solution: The problem constraints ensure death years are within [1950, 2050], and since people aren't alive in their death year, we mark the death year itself (not death_year + 1), avoiding boundary issues.

3. Tie-Breaking Logic Error

When multiple years have the same maximum population, using <= instead of < in the comparison would return the latest year instead of the earliest.

Wrong approach:

if max_population <= current_population:  # Returns latest year
    max_population = current_population
    year_with_max_population = year_index

Correct approach:

if max_population < current_population:  # Returns earliest year
    max_population = current_population
    year_with_max_population = year_index

4. Forgetting the Base Year Offset

A subtle bug occurs when forgetting to add back the base year (1950) when returning the result, leading to returning an index instead of the actual year.

Wrong: return year_with_max_population
Correct: return year_with_max_population + base_year