✅ [C++/Python] Simple Solution w/ Explanation | Sliding Window
If you are doing Daily LeetCoding Challenge for June, I highly recommend you look at the problem given on June 10: 3. Longest Substring Without Repeating Charac
If you are doing Daily LeetCoding Challenge for June, I highly recommend you look at the problem given on June 10: [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/). I have already briefly discussed that problem [in this post](https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/2132954).\nBut if you are visiting this problem for the first time, I still recommend you to see that problem and try to find a similarity with this one \uD83D\uDE42. Here, we need to maximize the subarray sum instead of the length.\n___\n___\n\u274C **Solution I: Brute-Force [TLE]**\n\nStarting with each index, we can check all subarrays till we find a repeating number. We can use a set to store the numbers we\'ve encountered so far to check for repetition.\n\n```python\nclass Solution:\n    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n        max_sum = 0\n        seen = set()\n        for l in range(len(nums)):\n            seen.clear()\n            curr_sum = 0\n            r = l\n            while r < len(nums):\n                if nums[r] in seen:\n                    break\n                curr_sum += nums[r]\n                seen.add(nums[r])\n                r += 1\n            max_sum = max(max_sum, curr_sum)\n        return max_sum\n```\n\n- **Time Complexity:** `O(n\xB2)`\n- **Space Complexity:** `O(1)`\n___\n\u2705 **Solution II (a): Sliding Window + Set [Accepted]**\n\nIf you haven\'t heard the term "sliding window" before, visit [this link](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples).\n\nThe sliding windows approach is a two-pointer approach. Still, I refrained from saying it because I\'m not actually using 2 pointers. The left bound of the window is defined by `l` and the right bound by the index of `num`.\n\n**Algorithm:**\n\n1. Create a sliding window: `[nums[l], nums[l + 1], ..., num].`\n2. For each number in the `nums` array, we check if this `num` is already present in the window. We can use a set to lookup in `O(1)`.\n3. If the number is present in the window, we keep shrinking the window from the left until there\'s no repetition.\n4. We update the set by adding `num` and repeat the above process.\n\n**Example:**\n```text\nnums = [4,2,1,2,6]\n1. Window: [4]; set = {4}; curr_sum = 4; max_sum = 4\n2. Window: [4, 2]; set = {4, 2}; curr_sum = 6; max_sum = 6\n3. Window: [4, 2, 1]; set = {4, 2, 1}; curr_sum = 7; max_sum = 7\n4(a). Window: [2, 1, 2]; set = {2, 1}; curr_sum = 5; max_sum = 7\n4(b). Window: [1, 2]; set = {1, 2}; curr_sum = 3; max_sum = 7\n5. Window: [1, 2, 6]; set = {1, 2, 6}; curr_sum = 9; max_sum = 9\n```\n\n<iframe src="https://leetcode.com/playground/bUc7dtpg/shared" frameBorder="0" width="1080" height="360"></iframe>\n\n- **Time Complexity:** `O(n)`\n- **Space Complexity:** `O(k)`, where k is the number of distinct elements. Here, `k = 10\u2074` (See constraints)\n___\n\u2705 **Solution II (b): Sliding Window + Array [Accepted]**\n\nWe create a sliding window whose left bound is defined by `l` and the right bound by `r`. We try to expand this window towards the right so that no number inside is repeated. In the previous approach to know whether `nums[r]` is already inside this window or not, we used a set. But in this case, we are using an array to know by storing the previous index of each element.\nHow storing the previous index will help?\n\u27A1\uFE0F If the previous index of `nums[r]`, i.e., `prev[nums[r]]  >= l`, it means previous `nums[r]` is towards the right of `l`. In other words, inside the current window.\n\n<iframe src="https://leetcode.com/playground/aspW6KyX/shared" frameBorder="0" width="1080" height="350"></iframe>\n\n- **Time Complexity:** `O(n)`\n- **Space Complexity:** `O(k)`, where k is the number of distinct elements. Here, `k = 10\u2074` (See constraints)\n\n___\n**FAQs:**\n\n1. Why the time complexity for the second approach is `O(n)` instead of `O(n\xB2)`?\n\u27A1\uFE0F Don\'t get confused by looking at the nested loops. Focus on how many elements both the pointers are traversing through. For `r`, it is `n` elements. For `l`, it is `n` in the worst case. So, `O(n) + O(n)` which is effectively `O(n)`.\n___\n___\nIf you like the solution, please **upvote**! \uD83D\uDD3C\nFor any questions, or discussions, comment below. \uD83D\uDC47\uFE0F\n
['Two Pointers', 'Sliding Window', 'Ordered Set', 'Python']