Maximum Population Year - Video Solutions

Problem Overview: You are given birth and death years for multiple people. Each log [birth, death] means the person was alive from birth up to but not including death. The task is to determine the year with the highest population. If multiple years share the same population, return the earliest year.

Approach 1: Brute Force Year Population Counting (Time: O(n * R), Space: O(1))

This method directly simulates population counts for every year. For each year in the allowed range (1950–2050 in the problem constraints), iterate through all logs and count how many people are alive in that year. A person contributes to the count if birth ≤ year < death. Track the maximum population seen so far and update the answer when a larger count appears. The implementation is simple and relies only on basic iteration over an array of logs.

The key idea is straightforward counting: evaluate each year independently. While this works well given the small fixed year range, it becomes inefficient if the range grows large because every year scans all logs again. Time complexity is O(n * R) where n is the number of logs and R is the number of candidate years. Space complexity stays O(1) since only a few counters are maintained.

Approach 2: Delta Population Technique (Prefix Sum) (Time: O(n + R), Space: O(R))

The optimized solution treats population changes as events instead of recomputing counts every year. For each log, increment the population at birth and decrement it at death. This creates a difference array where each index represents how the population changes in that year. After recording all changes, run a cumulative sum across the years to reconstruct the population count at each point.

This is a classic application of the prefix sum pattern combined with simple counting. The insight is that births and deaths define boundaries where population changes, so tracking only those transitions avoids repeatedly scanning all logs. After computing the prefix sum, iterate once through the years to find the maximum population and return the earliest year where it occurs.

This approach runs in O(n + R) time: O(n) to record birth/death deltas and O(R) to compute the prefix sum across the year range. Space complexity is O(R) for the difference array. For problems involving frequent range updates and cumulative totals, the delta technique is a powerful pattern.

Recommended for interviews: Interviewers typically expect the delta population (prefix sum) approach. The brute force version demonstrates that you understand the population definition and boundary condition birth ≤ year < death. The prefix sum solution shows stronger algorithmic thinking by converting repeated counting into event-based updates and a single cumulative pass.