Don't be ashamed of N^2

Easy problems on LeetCode are usually easy for a simple reason: you can solve them in polynomial time, most of the time in N^2, without worrying about the constraints since they are small. At the same time, there are probably better than N^2 solutions, but my advise is, if you can solve in N^2, and the N is super small, like 100, don't be ashamed of N^2. There is a great saying: "never let the great be the enemy of the good, and never let the good be the enemy of done". Get it done. Problem is here, and code is down below. Cheers, ACC.

Maximum Population Year - LeetCode

1854. Maximum Population Year

Easy

You are given a 2D integer array logs where each logs[i] = [birthi, deathi] indicates the birth and death years of the ith person.

The population of some year x is the number of people alive during that year. The ith person is counted in year x's population if x is in the inclusive range [birthi, deathi - 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 <= birthi < deathi <= 2050

public int MaximumPopulation(int[][] logs)
{
    int maxPopulation = 0;
    int earliestYear = 3000;

    for (int i = 0; i < logs.Length; i++)
    {
        int count1 = 1;
        int count2 = 0;
        for (int j = 0; j < logs.Length; j++)
        {
            if (j != i)
            {
                if (logs[j][0] <= logs[i][0] && logs[j][1] > logs[i][0])
                {
                    count1++;
                }
                if (logs[j][0] <= logs[i][1] && logs[j][1] > logs[i][1])
                {
                    count2++;
                }
            }
        }

        if (count1 == maxPopulation)
        {
            if (logs[i][0] <= earliestYear) earliestYear = logs[i][0];
        }
        if (count1 > maxPopulation)
        {
            earliestYear = logs[i][0];
            maxPopulation = count1;
        }
        if (count2 == maxPopulation)
        {
            if (logs[i][1] <= earliestYear) earliestYear = logs[i][1];
        }
        if (count2 > maxPopulation)
        {
            earliestYear = logs[i][1];
            maxPopulation = count2;
        }
    }

    return earliestYear;
}