Skip to content

1854. Maximum Population Year 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int maximumPopulation(vector<vector<int>>& logs) {
    constexpr int kMinYear = 1950;
    constexpr int kMaxYear = 2050;
    int ans = 0;
    int maxPopulation = 0;
    int runningPopulation = 0;
    // population[i] := the population of year i
    vector<int> population(kMaxYear + 1);

    for (const vector<int>& log : logs) {
      const int birth = log[0];
      const int death = log[1];
      ++population[birth];
      --population[death];
    }

    for (int year = kMinYear; year <= kMaxYear; ++year) {
      runningPopulation += population[year];
      if (runningPopulation > maxPopulation) {
        maxPopulation = runningPopulation;
        ans = year;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int maximumPopulation(int[][] logs) {
    final int kMinYear = 1950;
    final int kMaxYear = 2050;
    int ans = 0;
    int maxPopulation = 0;
    int runningPopulation = 0;
    // population[i] := the population of year i
    int[] population = new int[kMaxYear + 1];

    for (int[] log : logs) {
      final int birth = log[0];
      final int death = log[1];
      ++population[birth];
      --population[death];
    }

    for (int year = kMinYear; year <= kMaxYear; ++year) {
      runningPopulation += population[year];
      if (runningPopulation > maxPopulation) {
        maxPopulation = runningPopulation;
        ans = year;
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def maximumPopulation(self, logs: list[list[int]]) -> int:
    kMinYear = 1950
    kMaxYear = 2050
    ans = 0
    maxPopulation = 0
    runningPopulation = 0
    # population[i] := the population of year i
    population = [0] * (kMaxYear + 1)

    for birth, death in logs:
      population[birth] += 1
      population[death] -= 1

    for year in range(kMinYear, kMaxYear + 1):
      runningPopulation += population[year]
      if runningPopulation > maxPopulation:
        maxPopulation = runningPopulation
        ans = year

    return ans