Maximum Population Year

easy difference array prefix sum

Problem

You are given a list of life spans, where logs[i] = [birth, death] for one person and every year lies in 1950..2050. A person is counted in the population of each year from their birth year up to, but not including, their death year. Return the earliest year that has the largest population.

Inputlogs = [[1993,1999],[1995,2008],[2000,2008],[1996,2005]]

Output1996

From 1996 to 1998 three people (born 1993, 1995 and 1996) are alive at once — the peak population of 3 — and 1996 is the earliest such year.

logs (birth:death, comma-separated)

def maximum_population(logs):
    delta = [0] * 101                  # one slot per year 1950..2050
    for birth, death in logs:
        delta[birth - 1950] += 1       # alive from the birth year
        delta[death - 1950] -= 1       # not counted in the death year
    best_year, best_pop, running = 1950, 0, 0
    for i in range(101):
        running += delta[i]            # population of year 1950 + i
        if running > best_pop:
            best_pop = running
            best_year = 1950 + i
    return best_year

function maximumPopulation(logs) {
  const delta = new Array(101).fill(0); // one slot per year 1950..2050
  for (const log of logs) {
    delta[log[0] - 1950] += 1;          // alive from the birth year
    delta[log[1] - 1950] -= 1;          // not counted in the death year
  }
  let bestYear = 1950, bestPop = 0, running = 0;
  for (let i = 0; i < 101; i++) {
    running += delta[i];                // population of year 1950 + i
    if (running > bestPop) {
      bestPop = running;
      bestYear = 1950 + i;
    }
  }
  return bestYear;
}

int maximumPopulation(int[][] logs) {
    int[] delta = new int[101];        // one slot per year 1950..2050
    for (int[] log : logs) {
        delta[log[0] - 1950] += 1;     // alive from the birth year
        delta[log[1] - 1950] -= 1;     // not counted in the death year
    }
    int bestYear = 1950, bestPop = 0, running = 0;
    for (int i = 0; i < 101; i++) {
        running += delta[i];           // population of year 1950 + i
        if (running > bestPop) {
            bestPop = running;
            bestYear = 1950 + i;
        }
    }
    return bestYear;
}

int maximumPopulation(vector<vector<int>>& logs) {
    int delta[101] = {0};              // one slot per year 1950..2050
    for (auto& log : logs) {
        delta[log[0] - 1950] += 1;     // alive from the birth year
        delta[log[1] - 1950] -= 1;     // not counted in the death year
    }
    int bestYear = 1950, bestPop = 0, running = 0;
    for (int i = 0; i < 101; i++) {
        running += delta[i];           // population of year 1950 + i
        if (running > bestPop) {
            bestPop = running;
            bestYear = 1950 + i;
        }
    }
    return bestYear;
}

Explanation

The brute force would count, for every year, how many people are alive in it — that is O(people × years). The key insight is that a person only changes the population twice: it goes up by one in their birth year and down by one in their death year (they are not counted in the year they die). So instead of counting everyone everywhere, we record just those change points in a difference array: delta[birth] += 1 and delta[death] -= 1.

A prefix sum over the difference array then reconstructs the population of every year. Sweeping the years in order with a running sum, running += delta[year] gives exactly the number of people alive in that year — every birth at or before it has added 1 and every death at or before it has subtracted 1.

While sweeping we track the best year. Using a strictly-greater comparison (running > best_pop) means we only switch when a year truly beats the current maximum, so ties keep the earlier year — which is exactly the "earliest year with the maximum population" the problem asks for.

Walking the default example [[1993,1999],[1995,2008],[2000,2008],[1996,2005]]: the marks are +1 at 1993, 1995, 1996 and 2000, −1 at 1999 and 2005, and −2 at 2008. The running sum climbs 1, 1, 2, 3 by 1996 — a new maximum of 3 — dips to 2 in 1999, returns to 3 in 2000 (not a new maximum, 3 is not greater than 3), and never exceeds 3. The answer is 1996.

Marking all people costs O(n) and the sweep costs O(Y) where Y = 101 is the fixed 1950..2050 year range. Since Y is a constant, the algorithm is effectively O(n) time with O(1) extra space — the 101-slot difference array does not grow with the input.

Time: O(n + Y), Y = 101 years Space: O(Y) = O(1)