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;
}

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more