JAVA || O(n) solution With Explanation || Range Addition
Let\'s understand with an example\nSuppose we are given the log [1950, 1961]\nThis means birth year is 1950 and death year is 1961\nTherefore, years from 1950 t
Let\'s understand with an example\nSuppose we are given the log [1950, 1961]\nThis means birth year is 1950 and death year is 1961\nTherefore, years from 1950 to 1960 will be incremented by 1.\n\nWe can do it by iterating from 1950 to 1960 but that will increase time complexity if we have to do it for every query in logs array.\n\nTo do this in O(1), we increment year[1950] by 1 and decrement year[1961] by 1.\nWe can reapeat this for every query in logs array.\n\nWhat will this do ?\n\nFor the case [1950, 1961], let\'s look at how the array will look like\n\n![image](https://assets.leetcode.com/users/images/a4172564-0a38-486a-9b09-4b0481ff89bb_1620540596.718192.png)\n\n\nBut this is not the desired result ?\n\nTo get the answer,\nAfter iterating through all the queries, take prefix sum of the array(year)\nThis is how the array will look like\n\n![image](https://assets.leetcode.com/users/images/f6c1f3d6-b05a-4838-9f8d-8f5828914cea_1620540708.6256618.png)\n\nYou can see that the Prefix Sum row will give the desired result as we have incremented the values of array from index 1950 to 1960.\n\nLet\'s try for the test case, logs = [[1950,1961],[1960,1965],[1963,1970]] for a better understanding\n\n![image](https://assets.leetcode.com/users/images/a582b7a5-a7c1-4bc8-a35d-553d1f796a62_1620540523.8904378.png)\n\nLooking at the Prefix Sum, we can clearly see that the maximum value is 2 and its first occurence is at 1960. Hence, 1960 is the answer.\n\n```\nclass Solution {\n    public int maximumPopulation(int[][] logs) {\n        \n        int[] year = new int[2051];\n        \n\t\t// O(n) -> n is log.length\n\t\t\n        for(int[] log : logs){\n            \n            year[log[0]] += 1;\n            year[log[1]] -= 1;\n        }\n        \n        int maxNum = year[1950], maxYear = 1950;\n        \n\t\t// O(100) -> 2050 - 1950 = 100\n\n        for(int i = 1951; i < year.length; i++){\n            year[i] += year[i - 1];  // Generating Prefix Sum\n            \n            if(year[i] > maxNum){\n                maxNum = year[i];\n                maxYear = i;\n            }\n        }\n        \n        return maxYear;\n    }\n}\n```\nTotal time complexity will be O(n + 100) -> O(n)\nIn a general case we can write it as O(n + Range of Year)\n\nYou can also improve the space complexity by taking array of size 101 and not of 2051 because we only consider years from 1950 to 2050.
['Java']