# Find the year with the highest population (most efficient solution)

7.5k Views

Given two arrays; `\$births` containing a list of birth years indicating when someone was born, and `\$deaths` containing a list of death years indicating when someone died, how can we find the year on which the population was highest?

For example given the following arrays:

``````\$births = [1984, 1981, 1984, 1991, 1996];
\$deaths = [1991, 1984];
``````

The year on which the population was highest should be `1996`, because `3` people were alive during that year, which was the highest population count of all those years.

Here's the running math on that:

```| Birth | Death | Population |
|-------|-------|------------|
| 1981  |       | 1          |
| 1984  |       | 2          |
| 1984  | 1984  | 2          |
| 1991  | 1991  | 2          |
| 1996  |       | 3          |
```

# Assumptions

We can safely assume that the year on which someone is born the population can increase by one and the year on which someone died the population can decrease by one. So in this example, 2 people were born on 1984 and 1 person died on 1984, meaning the population increased by 1 on that year.

We can also safely assume that the number of deaths will never exceed the number of births and that no death can occur when the population is at 0.

We can also safely assume that the years in both `\$deaths` and `\$births` will never be negative or floating point values (they're always positive integers greater than 0).

We cannot assume that the arrays will be sorted or that there won't be duplicate values, however.

# Requirements

We must write a function to return the year on which the highest population occurred, given these two arrays as input. The function may return `0`, `false`, `""`, or `NULL` (any falsey value is acceptable) if the input arrays are empty or if the population was always at 0 throughout. If the highest population occurred on multiple years the function may return the first year on which the highest population was reached or any subsequent year.

For example:

``````\$births = [1997, 1997, 1997, 1998, 1999];
\$deaths = [1998, 1999];

/* The highest population was 3 on 1997, 1998 and 1999, either answer is correct */
``````

My best attempt at doing this would be the following:

``````function highestPopulationYear(Array \$births, Array \$deaths): Int {

sort(\$births);
sort(\$deaths);

\$nextBirthYear = reset(\$births);
\$nextDeathYear = reset(\$deaths);

\$years = [];
if (\$nextBirthYear) {
\$years[] = \$nextBirthYear;
}
if (\$nextDeathYear) {
\$years[] = \$nextDeathYear;
}

if (\$years) {
\$currentYear = max(0, ...\$years);
} else {
\$currentYear = 0;
}

\$maxYear = \$maxPopulation = \$currentPopulation = 0;

while(current(\$births) !== false || current(\$deaths) !== false || \$years) {

while(\$currentYear === \$nextBirthYear) {
\$currentPopulation++;
\$nextBirthYear = next(\$births);
}

while(\$currentYear === \$nextDeathYear) {
\$currentPopulation--;
\$nextDeathYear = next(\$deaths);
}

if (\$currentPopulation >= \$maxPopulation) {
\$maxPopulation = \$currentPopulation;
\$maxYear = \$currentYear;
}

\$years = [];

if (\$nextBirthYear) {
\$years[] = \$nextBirthYear;
}
if (\$nextDeathYear) {
\$years[] = \$nextDeathYear;
}
if (\$years) {
\$currentYear = min(\$years);
} else {
\$currentYear = 0;
}
}

return \$maxYear;
}
``````

The algorithm above should work in polynomial time given it is at worst `O(((n log n) * 2) + k)` where `n` is number of elements to be sorted from each array and `k` is number of birth years (since we know that `k` is always `k >= y`) where `y` is number of death years. However, I'm not sure if there is a more efficient solution.

My interests are purely in an improved Big O of computational complexity upon the existing algorithm. Memory complexity is of no concern. Nor is the runtime optimization. At least it's not a primary concern. Any minor/major runtime optimizations are welcome, but not the key factor here.

• 2
• The question is seeking the most efficient solution, not necessarily any working solution. I think that's perfectly valid on SO.
• I'm not saying it's not valid on SO (I would have voted to close in that case), I am just wondering if you may get more of a response on CR.
• 1
• @NigelRen I don't see the harm in trying. Though I would like to leave this open for a few days. If it doesn't get an answer I will put a bounty on it.
• 2
• SO itself has a lot of your problem question if you search for birth death keywords. A cheap improvement would be to improve the sort: make an array of length the span of birth/death (each cell is a date holding for value 0 by default). add 1 or substract 1 to the cell regarding birth and death, then cumulatively sum and keep the max sum found

I think we can have `O(n log n)` time with `O(1)` additional space by first sorting, then maintaining a current population and global maximum as we iterate. I tried to use the current year as a reference point but the logic still seemed a bit tricky so I'm not sure it's completely worked out. Hopefully, it can give an idea of the approach.

JavaScript code (counterexamples/bugs welcome)

``````function f(births, deaths){
births.sort((a, b) => a - b);
deaths.sort((a, b) => a - b);

console.log(JSON.stringify(births));
console.log(JSON.stringify(deaths));

let i = 0;
let j = 0;
let year = births[i];
let curr = 0;
let max = curr;

while (deaths[j] < births[0])
j++;

while (i < births.length || j < deaths.length){
while (year == births[i]){
curr = curr + 1;
i = i + 1;
}

if (j == deaths.length || year < deaths[j]){
max = Math.max(max, curr);
console.log(`year: \${ year }, max: \${ max }, curr: \${ curr }`);

} else if (j < deaths.length && deaths[j] == year){
while (deaths[j] == year){
curr = curr - 1;
j = j + 1;
}
max = Math.max(max, curr);
console.log(`year: \${ year }, max: \${ max }, curr: \${ curr }`);
}

if (j < deaths.length && deaths[j] > year && (i == births.length || deaths[j] < births[i])){
year = deaths[j];
while (deaths[j] == year){
curr = curr - 1;
j = j + 1;
}
console.log(`year: \${ year }, max: \${ max }, curr: \${ curr }`);
}

year = births[i];
}

return max;
}

var input = [
[[1997, 1997, 1997, 1998, 1999],
[1998, 1999]],
[[1, 2, 2, 3, 4],
[1, 2, 2, 5]],
[[1984, 1981, 1984, 1991, 1996],
[1991, 1984, 1997]],
[[1984, 1981, 1984, 1991, 1996],
[1991, 1982, 1984, 1997]]
]

for (let [births, deaths] of input)
console.log(f(births, deaths));``````
• 1. thx for teaching me existence of Y-fast trie. Regarding algo: no need to check the max after decreasing. Only after incrementing. Last while block is unnecesary: consider sorting two sorted list: you just need the head of both (i,j), pick the head of each, and advance the smaller one. `if(birth_i < death_j){//increment stuff + check max} else{//decrement}; birth_i||=infty; death_j||=infty`. Also you can iterate up to `min(birthSize, deathSize)`. if min is birth, stop. if min is death (suspicious..), stop and check `(max + birth.length-i)`
• 1
• @grodzi I did start out considering merge sort but concluded this needs extra handling because of how duplicates as well as the order of birth vs death affects the count. The last while loop seems necessary to me when there are death years unmatched by birth years. You are correct that the max in that loop is unnecessary.
• 1
• @???????? Use bucket sort for linear time.
• 1
• I already stated this idea in my answer, "If the year range, m, is on the order of n, we could store the counts for each year in the range and have O(n) time complexity."
• 2
• this is not efficiency, I don't know why give you the reward hahaha

We can solve this in linear time with bucket sort. Let's say the size of the input is n, and the range of years is m.

``````O(n): Find the min and max year across births and deaths.
O(m): Create an array of size max_yr - min_yr + 1, ints initialized to zero.
Treat the first cell of the array as min_yr, the next as min_yr+1, etc...
O(n): Parse the births array, incrementing the appropriate index of the array.
arr[birth_yr - min_yr] += 1
O(n): Ditto for deaths, decrementing the appropriate index of the array.
arr[death_yr - min_yr] -= 1
O(m): Parse your array, keeping track of the cumulative sum and its max value.
``````

The running time is O(n+m), and the additional space needed is O(m).

This is a linear solution in n if m is O(n); i.e., if the range of years isn't growing more quickly than the number of births and deaths. This is almost certainly true for real world data.

• 2
• I'll note that because your granularity is year, there is some ambiguity. in that we're effectively measuring population as of the year-end, and there may be some other point of time mid-year where the population is higher due to the timing of births and deaths.
• There is no ambiguity there. As clearly stated in the question you can safely assume that the year on which someone is born or dead that it counts as of that year.
• 2
• How is this linear time if we have to parse an "array of size max_yr - min_yr + 1" ? (cc @Sherif)
• @Dave: is the complexity not O(2n) for points 1 and 2? 1. iterate once through all births+death: `O(n): Find the min and max year across births and deaths` 2. iterate again through all births+death: `O(n): Parse the births+death array, incrementing the appropriate index of the array` then you do: O(m): Parse your array, keeping track of the cumulative sum and its max value. (you don't need to parse this array - you can keep track of MAX while incrementing the indices in 2)
• 1
• @Sherif Implementation is left as an exercise for the reader... It's trivial anyway. Is anything not clear?

First aggregate the births and deaths into a map (`year => population change`), sort that by key, and calculate the running population over that.

This should be approximately `O(2n + n log n)`, where `n` is the number of births.

``````\$births = [1984, 1981, 1984, 1991, 1996];
\$deaths = [1991, 1984];

function highestPopulationYear(array \$births, array \$deaths): ?int
{
\$indexed = [];

foreach (\$births as \$birth) {
\$indexed[\$birth] = (\$indexed[\$birth] ?? 0) + 1;
}

foreach (\$deaths as \$death) {
\$indexed[\$death] = (\$indexed[\$death] ?? 0) - 1;
}

ksort(\$indexed);

\$maxYear = null;
\$max = \$current = 0;

foreach (\$indexed as \$year => \$change) {
\$current += \$change;
if (\$current >= \$max) {
\$max = \$current;
\$maxYear = \$year;
}
}

return \$maxYear;
}

var_dump(highestPopulationYear(\$births, \$deaths));
``````
• As I see: With n = number of events (births + deaths) and m = number of event years (years with births or deaths) this would be actually O(n + m log m). If n >> m - this can be considered as O(n). If you have billions of births and deaths in a period of (say) 100 years - sorting an array with 100 elements (`ksort(\$indexed)`) becomes irrelevant.
• 2
• You could process the births with `\$indexed = array_count_values(\$births);`.

I solved this problem with a memory requirement of `O(n+m)` [in worst case, best case `O(n)`]

and, time complexity of `O(n logn)`.

Here, `n & m` are the length of `births` and `deaths` arrays.

I don't know PHP or javascript. I've implemented it with Java and the logic is very simple. But I believe my idea can be implemented in those languages as well.

Technique Details:

I used java `TreeMap` structure to store births and deaths records.

`TreeMap` inserts data sorted (key based) as (key, value) pair, here key is the year and value is the cumulative sum of births & deaths (negative for deaths).

We don't need to insert deaths value that happened after the highest birth year.

Once the TreeMap is populated with the births & deaths records, all the cumulative sums are updated and store the maximum population with year as it progressed.

Sample input & output: 1

``````Births: [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906]

Deaths: [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915]

Year counts Births: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1911=2, 1914=1, 1919=2}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1910=-1, 1911=0, 1912=-1, 1913=-1, 1914=-2, 1915=-2, 1919=2}

Yearwise population: {1900=2, 1901=3, 1903=4, 1904=5, 1906=6, 1908=9, 1909=10, 1910=9, 1911=9, 1912=8, 1913=7, 1914=5, 1915=3, 1919=5}

maxPopulation: 10
yearOfMaxPopulation: 1909
``````

Sample input & output: 2

``````Births: [1906, 1901, 1911, 1902, 1905, 1911, 1902, 1905, 1910, 1912, 1900, 1900, 1904, 1913, 1904]

Deaths: [1917, 1908, 1918, 1915, 1907, 1907, 1917, 1917, 1912, 1913, 1905, 1914]

Year counts Births: {1900=2, 1901=1, 1902=2, 1904=2, 1905=2, 1906=1, 1910=1, 1911=2, 1912=1, 1913=1}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1902=2, 1904=2, 1905=1, 1906=1, 1907=-2, 1908=-1, 1910=1, 1911=2, 1912=0, 1913=0}

Yearwise population: {1900=2, 1901=3, 1902=5, 1904=7, 1905=8, 1906=9, 1907=7, 1908=6, 1910=7, 1911=9, 1912=9, 1913=9}

maxPopulation: 9
yearOfMaxPopulation: 1906
``````

Here, deaths occurred (`1914 & later`) after the last birth year `1913`, was not counted at all, that avoids unnecessary computations.

For a total of `10 million` data (births & deaths combined) and over `1000 years range`, the program took about `3 sec.` to finish.

If same size data with `100 years range`, it took `1.3 sec`.

All the inputs are randomly taken.

``````\$births = [1984, 1981, 1984, 1991, 1996];
\$deaths = [1991, 1984];
\$years = array_unique(array_merge(\$births, \$deaths));
sort(\$years);

\$increaseByYear = array_count_values(\$births);
\$decreaseByYear = array_count_values(\$deaths);
\$populationByYear = array();

foreach (\$years as \$year) {
\$increase = \$increaseByYear[\$year] ?? 0;
\$decrease = \$decreaseByYear[\$year] ?? 0;
\$previousPopulationTally = end(\$populationByYear);
\$populationByYear[\$year] = \$previousPopulationTally + \$increase - \$decrease;
}

\$maxPopulation = max(\$populationByYear);
\$maxPopulationYears = array_keys(\$populationByYear, \$maxPopulation);

\$maxPopulationByYear = array_fill_keys(\$maxPopulationYears, \$maxPopulation);
print_r(\$maxPopulationByYear);
``````

This will account for the possibility of a tied year, as well as if a year of someone's death does not correspond to someone's birth.

• 1
• This answer makes no attempt to provide the academic Big O explanation that is requested by the OP.

Memory wise it is to keep `currentPopulation` and `currentYear` calculated. Starting by sorting both `\$births` and `\$deaths` arrays is a very good point, because bubble sorting is not that heavy task, yet allows to cut some corners:

``````<?php

\$births = [1997, 1999, 2000];
\$deaths = [2000, 2001, 2001];

function highestPopulationYear(array \$births, array \$deaths): Int {

// sort takes time, but is neccesary for futher optimizations
sort(\$births);
sort(\$deaths);

// first death year is a first year where population might decrase
// sorfar max population
\$currentYearComputing = \$deaths[0];

// year before first death has potential of having the biggest population
\$maxY = \$currentYearComputing-1;

// calculating population at the begining of the year of first death, start maxPopulation
\$population = \$maxPop = count(array_splice(\$births, 0, array_search(\$deaths[0], \$births)));

// instead of every time empty checks: `while(!empty(\$deaths) || !empty(\$births))`
// we can control a target time. It reserves a memory, but this slot is decreased
// every iteration.
\$iterations = count(\$deaths) + count(\$births);

while(\$iterations > 0) {
while(current(\$births) === \$currentYearComputing) {
\$population++;
\$iterations--;
array_shift(\$births); // decreasing memory usage
}

while(current(\$deaths) === \$currentYearComputing) {
\$population--;
\$iterations--;
array_shift(\$deaths); // decreasing memory usage
}

if (\$population > \$maxPop) {
\$maxPop = \$population;
\$maxY = \$currentYearComputing;
}

// In \$iterations we have a sum of birth/death events left. Assuming all
// are births, if this number added to currentPopulation will never exceed
// current maxPoint, we can break the loop and save some time at cost of
// some memory.
if (\$maxPop >= (\$population+\$iterations)) {
break;
}

\$currentYearComputing++;
}

return \$maxY;
}

echo highestPopulationYear(\$births, \$deaths);

``````

not really keen on diving into Big O thing, left it to you.

Also, if you rediscover `currentYearComputing` every loop, you can change loops into `if` statements and leave with just one loop.

``````    while(\$iterations > 0) {

\$changed = false;

if(current(\$births) === \$currentYearComputing) {
// ...
\$changed = array_shift(\$births); // decreasing memory usage
}

if(current(\$deaths) === \$currentYearComputing) {
// ...
\$changed = array_shift(\$deaths); // decreasing memory usage
}

if (\$changed === false) {
\$currentYearComputing++;
continue;
}
``````

I fill very comfortable of this solution, the complexity Big O is n + m

``````<?php
function getHighestPopulation(\$births, \$deaths){
\$max = [];
\$currentMax = 0;
\$tmpArray = [];

foreach(\$deaths as \$key => \$death){
if(!isset(\$tmpArray[\$death])){
\$tmpArray[\$death] = 0;
}
\$tmpArray[\$death]--;
}
foreach(\$births as \$k => \$birth){
if(!isset(\$tmpArray[\$birth])){
\$tmpArray[\$birth] = 0;
}
\$tmpArray[\$birth]++;
if(\$tmpArray[\$birth] > \$currentMax){
\$max = [\$birth];
\$currentMax = \$tmpArray[\$birth];
} else if (\$tmpArray[\$birth] == \$currentMax) {
\$max[] = \$birth;
}
}

return [\$currentMax, \$max];
}

\$births = [1997, 1997, 1997, 1998, 1999];
\$deaths = [1998, 1999];

print_r (getHighestPopulation(\$births, \$deaths));
?>
``````
• 2
• Shouldn't `\$tmpArray--` be `\$tmpArray[\$death]--`? Also please test with `\$births=[1997,1997,1998]; \$deaths=[];` - Does it return `1998` as it should?
• This code not only fails in the complex edge cases, but it even fails in the simplest of cases like given the input arrays `\$births = [3,1,2,1,3,3,2]` and `\$deaths = [2,3,2,3,3,3]` I would expect to get back `2` as the highest population year, yet your code returns `1`. In fact your code failed 9 out of 15 of my unit tests. I not only can't accept this as the most efficient answer, but I can't even accept it an efficient answer since it doesn't work at all.
• You failed to read the question carefully and thus failed to provide a good answer. You make the assumption here that I told you not to make (that the arrays are sorted). So please remove your offensive comment in the question about how I awarded the bounty to a non-efficient answer and this is somehow a "fix".

One of most simple and clear approach for your problem.

``````\$births = [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906];
\$deaths = [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915];

/* for generating 1 million records

for(\$i=1;\$i<=1000000;\$i++) {
\$births[] = rand(1900, 2020);
\$deaths[] = rand(1900, 2020);
}
*/

function highestPopulationYear(Array \$births, Array \$deaths): Int {
\$start_time = microtime(true);
\$population = array_count_values(\$births);
\$deaths = array_count_values(\$deaths);

foreach (\$deaths as \$year => \$death) {
\$population[\$year] = (\$population[\$year] ?? 0) - \$death;
}
ksort(\$population, SORT_NUMERIC);
\$cumulativeSum = \$maxPopulation = \$maxYear = 0;
foreach (\$population as \$year => &\$number) {
\$cumulativeSum += \$number;
if(\$maxPopulation < \$cumulativeSum) {
\$maxPopulation = \$cumulativeSum;
\$maxYear = \$year;
}
}
print " Execution time of function = ".((microtime(true) - \$start_time)*1000)." milliseconds";
return \$maxYear;
}

print highestPopulationYear(\$births, \$deaths);
``````

output:

``````1909
``````

complexity:

``````O(m + log(n))
``````
• for 1 million records execution time is just `29.64 milliseconds`