Line Sweep Algorithm

Line Sweep Algorithm

·

2 min read

Let see how to solve the leetcode problem Maximum Population Year.

The problem is given a list of birth year and death year, calculate the year with the maximum population. This is perfect problem for demostrate how line seep algorithm works, let see how.

The idea is to process all the cases with sorted order and calculate current state along the way.

In this problem, the cases are years. So we will first create an array with the index to express the years and values to express the population of the year. Then we will iterate the list of logs, if there is a birth, then plus 1, if there is a death, then minus 1. In this way, we will be end up with an array containing all the information about birth and death. The final step is to calculate the prefix sum of this array, then the values of the array will become the actual population of the year.

Take a simple list [[0, 3], [1, 3], [2, 3]] as an example, the process works like below.

[[0, 3], [1, 3], [2, 3]]

=> 

index: 0, 1, 2, 3
value: 1, 1, 1, -3

=> prefix sum

index: 0, 1, 2, 3
value: 1, 2, 3, 0

So the year 2 has the maximum population 3.

Now we know how the algorithm works, let solve this problem in code.

function maximumPopulation(logs: number[][]): number {
    const min = 1950;
    const max = 2050;

    const years = Array.from({ length: max - min + 1 }, () => 0);

    for (const [birth, death] of logs) {
        years[birth - min] += 1;
        years[death - min] -= 1;
    }

    let mpy = 0;
    let mp = years[0];
    for (let i = 1; i < years.length; i++) {
        years[i] += years[i - 1];
        if (years[i] > mp) {
            mp = years[i];
            mpy = i;
        }
    }

    return mpy + min;
};