✅ ✅  Python Easiest Solution Beats 99% 🔥🔥🔥
image.png\n\n\n# Intuition\nThe idea here is to use prefix sum to count the number of people alive in a particular year. Each time we encounter a year which is 
image.png\n![image.png](https://assets.leetcode.com/users/images/eb3a1454-0d19-4c00-bda6-ca89fec8ec37_1710571077.9645107.png)\n\n# Intuition\nThe idea here is to use prefix sum to count the number of people alive in a particular year. Each time we encounter a year which is a death year we substract the population by 1 and increament if it is a birth year.\n\nTo do this we need to keep a count of death years. For this I am using a dictionary.\n\nIn first loop we create a dictionary of deaths with count of each death year. We will use this later to give priority to reduction of population first as compared to incrementing it. As if the death and birth are in same year for different person we count them as 1 and not 2.\n\nNext we sort the years and calculate running total of population in a given year. If a year is present in dictionary we simply substract the population by 1 if the count of death years is more than 0.\n\nIf the year is not in deaths than we increment the count.\n\nNow all we need to do is find the year when prefix array had maximum value.\n\n# Complexity\n- Time complexity: nlogn due to sorting\n\n- Space complexity: O(n)\n\n# Find me on LinkedIn\n****[CLICK HERE](https://www.linkedin.com/in/priyanshu-jain-iim/)**\n\n# Find me on GitHub\n****[CLICK HEREEE...](https://github.com/priyanshuJain-32)**\n\n# PLEASE UPVOTE. HELPS MY MOTIVATION.\n\n![Cat for Leetcode.png](https://assets.leetcode.com/users/images/fcf42c7d-0cd2-4b7d-9fc9-27bab361350a_1705630029.4976823.png)\n\n# Code\n```\nclass Solution:\n    def maximumPopulation(self, logs: List[List[int]]) -> int:\n        deaths = defaultdict(int)\n        all_years = []\n        for b,d in logs:\n            deaths[d] += 1\n            all_years.extend([b,d])\n        all_years.sort()\n        \n        n = len(all_years)\n        prefix = [0]*(n+1)\n        for i in range(n):\n            if all_years[i] in deaths:\n                if deaths[all_years[i]]>0:\n                    prefix[i+1] = prefix[i]-1\n                    deaths[all_years[i]]-=1\n                else:\n                    prefix[i+1] = prefix[i]+1\n            else:\n                prefix[i+1] = prefix[i]+1\n        \n        max_pop = -1\n        for pop, year in zip(prefix[1:], all_years):\n            if pop>max_pop:\n                max_pop = pop\n                max_year = year\n\n        return max_year\n```\n
['Prefix Sum', 'Python', 'Python3']