An Interesting Optimisation | JAVA Explanation
Introduction:\nBefore we discuss the optimisation, let\'s make sure we\'re on the same page regarding the classic two-pointer approach.\nWe can solve this quest
### Introduction:\nBefore we discuss the optimisation, let\'s make sure we\'re on the same page regarding the classic two-pointer approach.\nWe can solve this question by simply expanding a right pointer while keeping track of the sum until we reach a value we\'ve seen before. Then, we increment our left pointer until the duplicate no longer exists. Finally, we can just update our maximum sum! I\'ve included the code for this approach below as well.\n\n### Optimising our code:\nNow, as you may have noticed, we continuously expand our left pointer until we reach that duplicate. Doesn\'t it feel like we could be saving some time here? I mean, if we already knew the <ins>last indexes of all values</ins>, we could just jump our left pointer straight there. Awesome, now we\'re getting somewhere.\n\n> Interview tip: To optimise your code, look for inefficiencies or repetitive work in your current approach and see if you can negate them. \n\nHang on, but what about our sums? The benefit of the regular two-pointer approach was that we get to adjust our sum while our left pointer is increasing. Well, what if we already knew the sums at any given range? Turns out we can do this using a prefix sum array.\n\n> Interview tip: If you find yourself thinking "man, it would be great if I had x", then try to enforce that behaviour in your algorithm.\n\n### Prefix Sums:\nThe idea behind prefix sums is that if we want the sum between the range `[left, right]`, we can obtain it by evaluating: \n**`sum[left, right] = sum[0, right] - sum[0, left - 1]`**. In other words, this is a *range sum query*.\n\nObserve this in the below illustration:\n![image](https://assets.leetcode.com/users/images/73b91f6a-15db-4ea3-9717-29b8d959f82f_1654996154.9269967.png)\n\nIn other words, the sum from any range from 0 to `i` where `i` is any index in the array, is called the <ins>prefix sum</ins>. If we store the prefix sum at each index, we can obtain any given sum range! If we combine this idea with the idea to keep track of "last indexes", we have ourselves an optimised approach.\n\nAnd there we have it! Just by spending a bit more extra space, we managed to improve our linear solution quite a bit! Now we\'re ready to start coding.\n___\n### Code:\n**Two-pointer Solution:**\n> Time complexity: `O(n)`\n> Space complexity: `O(m)` where `m` is the number of unique elements.\n```java\npublic int maximumUniqueSubarray(int[] nums) {        \n\tint maxScore = 0, currScore = 0;\n\tSet<Integer> set = new HashSet<>();\n\n\tfor (int l=0, r=0; r<nums.length; r++) {\n\t\twhile (!set.add(nums[r])) {\n\t\t\tcurrScore -= nums[l];\n\t\t\tset.remove(nums[l++]);\n\t\t}\n\t\tcurrScore += nums[r];\n\t\tmaxScore = Math.max(maxScore, currScore);\n\t}\n\n\treturn maxScore;\n}\n```\n**Prefix Sum Solution:**\n> Time complexity: `O(n)`\n> Space complexity: `O(n)`\n```java\npublic int maximumUniqueSubarray(int[] nums) {\n\tMap<Integer, Integer> lastIndex = new HashMap<>();\n\tint[] prefixSum = new int[nums.length + 1];\n\n\tint maxScore = 0;\n\tfor (int l=0, r=0; r<nums.length; r++) {\n\t\tprefixSum[r+1] = prefixSum[r] + nums[r];\n\t\tif (lastIndex.containsKey(nums[r])) \n\t\t\tl = Math.max(l, lastIndex.get(nums[r]) + 1);\n\t\tmaxScore = Math.max(maxScore, prefixSum[r+1] - prefixSum[l]);\n\t\tlastIndex.put(nums[r], r);\n\t}\n\n\treturn maxScore;\n}\n```\nNote: Both approaches can be improved using arrays instead of a set or map! I left the sets and maps in there to make the intention clear for this guide.
['Two Pointers', 'Prefix Sum', 'Java']