Prefix Sum with Range Updates
\n\n# Code\njava []\nclass Solution {\n    public int maximumPopulation(int[][] logs) {\n        \n        int[] year = new int[2051];\n        \n\t\t// O(n) ->
\n\n# Code\n```java []\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```\n```java []\nclass Solution {\n    public int maximumPopulation(int[][] logs) {\n        Map<Integer, Integer> populationChange = new TreeMap<>();\n\n        // Iterate through logs and record population changes\n        for (int[] log : logs) {\n            populationChange.put(log[0], populationChange.getOrDefault(log[0], 0) + 1);  // +1 for birth year\n            populationChange.put(log[1], populationChange.getOrDefault(log[1], 0) - 1);  // -1 for death year\n        }\n\n        int maxNum = 0, maxYear = 0, currentPopulation = 0;\n\n        // Traverse the TreeMap to calculate cumulative population and find the max\n        for (Map.Entry<Integer, Integer> entry : populationChange.entrySet()) {\n            currentPopulation += entry.getValue();\n            if (currentPopulation > maxNum) {\n                maxNum = currentPopulation;\n                maxYear = entry.getKey();\n            }\n        }\n\n        return maxYear;\n    }\n}\n\n```\n<br/>\n<br/><br/>\n\n---\n\n<br/><br/>\n\n\n### Difference Array or Prefix Sum with Range Updates Technique\n\nThis technique is called the **"Difference Array"** or **"Prefix Sum with Range Updates"**. It is commonly used to efficiently handle range updates and compute cumulative effects over a period.\n\n#### How it works:\nIn problems where we need to track changes over a range (e.g., years), this technique allows marking the beginning and the end of an effect (like population increase or decrease). \n\n#### Steps:\n1. **Range Update**:  \n   - For an event that starts at `yearStart` and ends at `yearEnd`, you:\n     - Increase the value at `yearStart` by a certain amount (e.g., population `+1` for a birth year).\n     - Decrease the value at `yearEnd` by the same amount (e.g., population `-1` for a death year).\n\n2. **Prefix Sum Calculation**:  \n   - After marking the changes, you calculate the prefix sum (cumulative effect) to get the actual values year by year. This accumulates the effect from previous years and applies it progressively.\n\n#### Why Use This Technique?\nInstead of updating every year between `yearStart` and `yearEnd` individually (which would be inefficient), you mark only the boundaries and compute the cumulative sum afterward. This reduces the time complexity of range updates to **O(1)** per event, followed by a **single pass** to calculate the final values.\n\n#### Use Cases:\n- **Population Change Problems** (like the problem shared).\n- **Range Addition Problems** (adding values to a subarray or interval).\n- **Scheduling Problems** (tracking activity over a period of time).\n\n#### In Your Code:\n- We marked the population changes by increasing the population by `+1` for births and decreasing it by `-1` for deaths.\n- Then, we used a prefix sum to accumulate population changes and find the year with the maximum population efficiently.\n\nBy using this technique, we optimized the solution for tracking changes over a range of years.\n
['Counting', 'Prefix Sum', 'Java']