✅ Maximum Erasure Value | Easy Solution using 2-Pointers and Hashset w/ Explanation
\u2714\uFE0F Solution (using 2-Pointers and HashSet)\n\nWe need to check every sub-array having unique elements and find the one having the maximum sum. Obvious
\u2714\uFE0F ***Solution (using 2-Pointers and HashSet)***\n\nWe need to check every sub-array having unique elements and find the one having the maximum sum. Obviously, with the given constraints, we can\'t check every sub-array individually.\n\nWe need to realise that we can **choose the first element and keep extending the array till we find a duplicate**. We can insert all the chosen elements till now into a hashset and check if the element already exists before inserting the next one. We will simultaneously also keep track of the sum of all chosen elements - *`cursum`* and maintain the max sum till now - *`ans`*\n\nWhen our next element ***`nums[r]`* is already present in currently chosen subarray** (hashset), then we must **delete all the elements from the start till the duplicate**. For this, we will need to maintain a left-pointer *`l`* denoting the left-most index of an element in currently chosen subarray. \n\nWe will keep deleting *`nums[l]`* and simultaneously deducting it from *`cur_sum`* and incrementing *`l`* pointer till duplicate is deleted. Finally we add *`nums[r]`* to our hashset and `cur_sum`. We repeat till we reach the end.\n\n**C++**\n```\nint maximumUniqueSubarray(vector<int>& nums) {        \n\tint n = size(nums), cur_sum = 0, ans = 0, l = 0, r = 0;\n\tunordered_set<int> s;\n\twhile(r < n) {\n\t\twhile(s.find(nums[r]) != end(s))          // delete from current sub-array till there\'s a duplicate of nums[r]\n\t\t\tcur_sum -= nums[l], s.erase(nums[l++]);\n\t\tcur_sum += nums[r], s.insert(nums[r++]);  // pick nums[r] and update cur_sum\n\t\tans = max(ans, cur_sum);                  // finally update ans to hold the maximum of all subarray sums till now\n\t}\n\treturn ans;\n}\n```\n\n---\n\n**Python**\n```\ndef maximumUniqueSubarray(self, nums: List[int]) -> int:\n\tsub_arr, l, cur_sum, ans  = set(), 0, 0, 0\n\tfor r in range(len(nums)):\n\t\twhile nums[r] in sub_arr:     # deleting duplciate of nums[r], if already exists \n\t\t\tsub_arr.remove(nums[l])\n\t\t\tcur_sum -= nums[l]\n\t\t\tl += 1\n\t\tsub_arr.add(nums[r])          # pick nums[r]\n\t\tcur_sum += nums[r]            # update current sub-array sum\n\t\tans = max(ans, cur_sum)       # update ans to hold max of all sub-array sums till now\n\treturn ans\n```\n\n***Time Complexity :*** **`O(N)`**, where *`N`* is the number of elements in *`nums`*\n***Space Complexity :*** **`O(N)`**\n\n---\n\n\u2714\uFE0F ***Solution - II (using 2-Pointers and Frequency array)***\n\nIt\'s given that all the element in `nums` are in the range `[1, 10000]`. We can use a frequency-array with indices `[1,10000]` to denote if an element is already chosen. \n\nThis method gave significant improvement in the runtime speed & memory of C++ (from ~360ms to <100ms). The improvement was negligible in case of python\n\n**C++**\n```\nint maximumUniqueSubarray(vector<int>& nums) {        \n\tint n = size(nums), cur_sum = 0, ans = 0, l = 0, r = 0;\n    bool freq[10001]{false};\n\twhile(r < n) {\n\t\twhile(freq[nums[r]])\n\t\t\tcur_sum -= nums[l], freq[nums[l++]] = false;\n\t\tcur_sum += nums[r], freq[nums[r++]] = true;  \n\t\tans = max(ans, cur_sum);    \n\t}\n\treturn ans;\n}\n```\n\n---\n\n**Python**\n```\ndef maximumUniqueSubarray(self, nums: List[int]) -> int:\n\tfreq, l, cur_sum, ans  = [False]*10001, 0, 0, 0\n\tfor r in range(len(nums)):\n\t\twhile freq[nums[r]]:\n\t\t\tfreq[nums[l]] = False\n\t\t\tcur_sum -= nums[l]\n\t\t\tl += 1\n\t\tfreq[nums[r]] = True\n\t\tcur_sum += nums[r]\n\t\tans = max(ans, cur_sum)\n\treturn ans\n```\n\n***Time Complexity :*** **`O(N)`**, where *`N`* is the number of elements in *`nums`*\n***Space Complexity :*** **`O(1)`**, although we are using array of size 10000, it doesn\'t depend on the size of input and hence the extra space used is constant - `O(1)`\n\n---\n\n*Best Runtime -*\n\n<table><tr><td><img src =https://assets.leetcode.com/users/images/e7193d6c-9e7e-4da3-a891-abb85294f4c7_1622191896.538263.png /></td></tr></table>\n\n\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C', 'Python']