Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1854.html

1854. Maximum Population Year

Level

Easy

Description

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i-th person.

The population of some year x is the number of people alive during that year. The i-th person is counted in year x’s population if x is in the inclusive range [birth_i, death_i - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

Example 1:

Input: logs = [[1993,1999],[2000,2010]]

Output: 1993

Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]

Output: 1960

Explanation:

The maximum population is 2, and it had happened in years 1960 and 1970.

The earlier year between them is 1960.

Constraints:

  • 1 <= logs.length <= 100
  • 1950 <= birth_i < death_i <= 2050

Solution

Use a list to store each person’s first and last year. That is, for each log in logs, add log[0] and -(log[1] - 1) to the list. Then store the list according to absolute values in ascending order and according to actual values in descending order. Then loop over the list to count the maximum population and store the corresponding year.

  • class Solution {
    public int maximumPopulation(int[][] logs) {
        List<Integer> birthDeathList = new ArrayList<Integer>();
        for (int[] log : logs) {
            birthDeathList.add(log[0]);
            birthDeathList.add(-(log[1] - 1));
        }
        Collections.sort(birthDeathList, new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                if (Math.abs(num1) != Math.abs(num2))
                    return Math.abs(num1) - Math.abs(num2);
                else
                    return num2 - num1;
            }
        });
        int maxYear = 0;
        int maxAlive = 0;
        int curAlive = 0;
        int size = birthDeathList.size();
        for (int i = 0; i < size; i++) {
            int year = birthDeathList.get(i);
            if (year > 0) {
                curAlive++;
                if (curAlive > maxAlive) {
                    maxYear = year;
                    maxAlive = curAlive;
                }
            } else
                curAlive--;
        }
        return maxYear;
    }
}

############

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] delta = new int[2055];
        for (int[] log : logs) {
            ++delta[log[0]];
            --delta[log[1]];
        }
        int res = 0, mx = 0, cur = 0;
        for (int i = 0; i < delta.length; ++i) {
            cur += delta[i];
            if (cur > mx) {
                mx = cur;
                res = i;
            }
        }
        return res;
    }
}

  • // OJ: https://leetcode.com/problems/maximum-population-year/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int maximumPopulation(vector<vector<int>>& A) {
        sort(begin(A), end(A));
        int ans = 0, mx = 0, N = A.size();
        for (int i = 0; i < N; ++i) {
            int yr = A[i][0], cnt = 0;
            for (int j = 0; j < N; ++j) {
                cnt += A[j][0] <= yr && A[j][1] > yr;
            }
            if (cnt > mx) {
                mx = cnt;
                ans = yr;
            }
        }
        return ans;
    }
};

  • class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        delta = [0] * 2055
        for birth, death in logs:
            delta[birth] += 1
            delta[death] -= 1

        mx = res = cur = 0
        for i, v in enumerate(delta):
            cur += v
            if mx < cur:
                mx = cur
                res = i
        return res

############

# 1854. Maximum Population Year
# https://leetcode.com/problems/maximum-population-year/

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        people = [0] * 2051
        
        for b,d in logs:
            people[b] += 1
            people[d] -= 1

        for i in range(1, 2051):
            people[i] += people[i - 1]
            
        res = 0
        mmax = float('-inf')
        for i,x in enumerate(people):
            if x > mmax:
                res = i
                mmax = x
        
        return res


  • func maximumPopulation(logs [][]int) int {
	delta := make([]int, 101)
	offset := 1950
	for _, log := range logs {
		delta[log[0]-offset]++
		delta[log[1]-offset]--
	}
	res, mx, cur := 0, 0, 0
	for i := 0; i < len(delta); i++ {
		cur += delta[i]
		if cur > mx {
			mx = cur
			res = i
		}
	}
	return res + offset
}

  • /**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function (logs) {
    const offset = 1950;
    const len = 2050 - 1950 + 1;
    let delta = new Array(len).fill(0);
    for (let log of logs) {
        delta[log[0] - offset] += 1;
        delta[log[1] - offset] -= 1;
    }
    let max = 0;
    let total = 0;
    let index = 0;
    for (let i = 0; i < len; i++) {
        total += delta[i];
        if (total > max) {
            max = total;
            index = i;
        }
    }
    return index + offset;
};


  • function maximumPopulation(logs: number[][]): number {
    const d: number[] = new Array(101).fill(0);
    const offset = 1950;
    for (const [birth, death] of logs) {
        d[birth - offset]++;
        d[death - offset]--;
    }
    let j = 0;
    for (let i = 0, s = 0, mx = 0; i < d.length; ++i) {
        s += d[i];
        if (mx < s) {
            mx = s;
            j = i;
        }
    }
    return j + offset;
}

All Problems

All Solutions