[Python] Subarray Problems Template. Thinking process to O(N).
First thing first, my O(n) solution:\n\n\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n    \n\t# Template: boundaries for calculating range later
First thing first, my O(n) solution:\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n    \n\t# Template: boundaries for calculating range later\n\tleft_bound = [-1] * n\n\tright_bound = [n] * n\n\n   # Template: get boundaries\n\tdic = {}\n\tfor i in range(n):\n\t\tch = s[i]\n\t\tif ch in dic:\n\t\t\tleft_bound[i] = dic[ch]\n\t\tdic[ch] = i\n\n\tdic = {}\n\tfor i in reversed(range(n)):\n\t\tch = s[i]\n\t\tif ch in dic:\n\t\t\tright_bound[i] = dic[ch]\n\t\tdic[ch] = i\n\n\tres = 0\n\tfor i in range(n):\n\t\t# Template: use boundaries to get contributions for each element in array\n\t\tres += (i - left_bound[i]) * (right_bound[i] - i)\n\n\treturn res\n```\n\nIt seems that Amazon likes to ask these type of problems with following properties:\n\n1. It allows to find an easy brute force solution with O(N^2 * N^c), similiar to DFS or backtracking. Using this, the recruiter can test interviewer how well the interviewer can simulate instructions using programming languages.\n2. It can be improved by using intermedia techniques to reduce it to O(N^2), similar to dynamic programming or Rolling Hash. Using this, the recruiter can test the interviewer how well the interviewer can improve performance by engineering or apply existing algorithms tools.\n3. Then it can be further improved by finding inner patterns, so it can be reduced to O(N), similar to greedy or Kadane\'s Algorithm. Using this, the recruiter can tell whether the interviewer has great problem-solving abilities or intuition for finding inner patterns. But this can be achieved by remembering some famous techniques, like prefix sum.\n\nFor example:\n\n1. Medium: https://leetcode.com/problems/sum-of-subarray-minimums\n2. Hard: https://leetcode.com/problems/sum-of-subarray-ranges\n2. Hard: https://leetcode.com/problems/sum-of-total-strength-of-wizards\n3. Hard: https://leetcode.com/problems/largest-rectangle-in-histogram\n4. Hard: https://leetcode.com/problems/sliding-window-maximum/\n\nUnlike greedy, there are some clear patterns for these problems. \n\n1. Using mono stack / queue for finding max / min problems\n2. Using left and right boundaries for accumulative total problems, like this problem.\n3. Using both above techniques in one problem\n\n### 1. Brute Force O(N^3) with 31 / 76\n\nThis solution is basically a template subarray traversing with Problem 1748, so this is an Easy solution\n\nhttps://leetcode.com/problems/sum-of-unique-elements/\n\nBrute Force is basically simulation. Do whatever the instructions ask to do. More like using programming language to implement something, but less enigeering part, so that we can reduce cost with sophisticated design. Recursive may reduce the difficulty of solving it but not improving the performance. That is to say, an Easy Problem is a problem to build a tool that can be roughly used though it might not be well designed, like a cave house, or a stick as a hunting weapon.\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n\tres = 0\n\tfor i in range(n):\n\t\tfor j in range(i, n):\n\t\t\tcount = Counter(s[i:j+1])\n\t\t\tuniq = 0\n\t\t\tfor c in count:\n\t\t\t\tif count[c] == 1:\n\t\t\t\t\tuniq += 1\n\t\t\tres += uniq\n\treturn res\n```\n\nAnother easy example: https://leetcode.com/problems/subarray-sum-equals-k/\n\nFollowing brute force solution passes 61 / 92 test cases.\n\n```\ndef subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tres = 0\n\tfor i in range(n):\n\t\tfor j in range(i, n):\n\t\t\tcurr_sum = sum(nums[i:j + 1])\n\t\t\tif curr_sum == k:\n\t\t\t\tres += 1\n\n\treturn res\n```\n\nSimple does what instructions ask to do.\n\n### 2. Dynamic Programming O(N^2) with 46 / 76\n\nInstead of repeatly counting subarray elements, we can move counter and uniq count up one loop level.\n\nAnd dynamically update uniq count state, so like we are using greedy for each i. Or we are using DP for remembering a state (treat `uniq` as `dp[0]`) while move forward. In this way, the second loop becomes O(1)\n\nWhy can we use DP? Because we can use remembered results from previous calculation. That is `array[:i]` has a property that `array[i]` can use. Instead of go over every instance in range `[:i]`, we only need to O(1) time to check remembered information.\n\nFor example, `max(array[:i + 1]) == max(max(arr[:i]) , arr[i])`, the new problem can be solved by using subproblem results. To me, the Rolling Hash is the epitome of this idea.\n\nIn this problem, for each index-i subarray, and for each j, we consider it as a subproblem `unique_count_until(j)` and use this subproblem results to get `unique_count_until(j + 1)` with a little help from `Counter()`.\n\nTo solve a larger problem, we only consider current element `array[i]` and never look back one by one, we save the subproblem result and remember other things to use in the later as long as we get them in O(n) time and use them in O(1) time.\n\nNow, compare with brute force, we have some enigeering efforts, which means we reduce computational and commercial cost.\n\nMultiplication and logrithms are invented to reduce computations. By trying to calculate using brute force, we may find that we are doing repetitive works, so we induct and abstract, and design a method to save time and efforts. This process is kind of robust since we can use brute force as if we are doing an experiment, find repetitions in each iteration and ask ourselves what if we know the subproblem solution.\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n\tres = 0\n\tfor i in range(n):\n\t\tcount = Counter()\n\t\tuniq = 0\n\t\tfor j in range(i, n):\n\t\t\tchar = s[j]\n\t\t\tif count[char] == 0:\n\t\t\t\tuniq += 1\n\t\t\telif count[char] == 1:\n\t\t\t\tuniq -= 1\n\t\t\tcount[char] += 1\n\t\t\tres += uniq\n\treturn res\n```\n\nAnother easy example: https://leetcode.com/problems/subarray-sum-equals-k/\n\nWhat can we use what we have solved in this problem? Simple, `sum(i + 1) = arr[i + 1] + sum(i)`, perfect example of dynamic programming and with one dimension array which can be further reduce to one state.\n\nThe following dp one state solution passes 72 / 92 cases.\n\n```\ndef subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tres = 0\n\tfor i in range(n):\n\t\tcurr_sum = 0\n\t\tfor j in range(i, n):\n\t\t\tcurr_sum += nums[j]\n\t\t\tif curr_sum == k:\n\t\t\t\tres += 1\n\n\treturn res\n```\n\nIf we use an array for dp:\n\n```\ndef subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tres = 0\n\tfor i in range(n):\n\t\tdp = [0] * (n + 1)\n\t\tfor j in range(i, n):\n\t\t\tdp[j] = dp[j - 1] + nums[j]\n\t\t\tif sums[j] == k:\n\t\t\t\tres += 1\n\n\treturn res\n```\n\nSimilar to above, but make it more prefix sum like.\n\n```\ndef subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tres = 0\n\tfor i in range(n):\n\t\tpsum = [0]\n\t\tfor j in range(i, n):\n\t\t\tpsum.append(psum[-1] + nums[j])\n\t\t\tif psum[-1] == k:\n\t\t\t\tres += 1\n\n\treturn res\n```\n\n### 3. Greedy O(N) with 76 / 76\n\nDP is a robust technique, yet greedy is not always obvious. Like in backtracking / DP, we try every possible children nodes and prune (remembering) some children nodes to reduce complexity. In greedy, we prune all children nodes by realizing some inner patterns.\n\nWhy can we use greedy for this problem? Because we can preprocess the array with one pass to get some properties `get_next_great_number(i)` ( https://leetcode.com/problems/next-greater-element-i ) of this array. Like we can build a DFA for string patterns in KMP ( https://leetcode.com/problems/longest-happy-prefix ). Later we can use these features for each element with one pass computation.\n\nIt might not be clear for this problem, let\'s see for the Prefix Sum problem. https://leetcode.com/problems/subarray-sum-equals-k/\n\n```\ndef subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tpsum = [0]\n\tfor num in nums:\n\t\tpsum.append(psum[-1] + num)\n\n\tdic = defaultdict(int)\n\tdic[0] = 1\n\n\tres = 0\n\tfor i in range(1, n + 1):\n\t\tcurr_sum = psum[i]\n\t\tres +=  dic[curr_sum - k]\n\t\tdic[curr_sum] += 1\n\n\treturn res\n```\n\nAs we can see, how smooth we can transfer from dp to greedy. The dp array can be precomputed within O(n), instead of O(n^2), that is to say, in O(n^2) solution we recompute the O(n) results. In some way, greedy is using dp on dp.\n\nOf course we can build prefix on the fly instead of preprocessing.\n\n```\n def subarraySum(self, nums: List[int], k: int) -> int:\n\tn = len(nums)\n\n\tdic = defaultdict(int)\n\tdic[0] = 1\n\n\tres = 0\n\tpsum = 0\n\tfor i in range(1, n + 1):\n\t\tpsum += nums[i - 1]\n\t\tres += dic[psum - k]\n\t\tdic[psum] += 1\n\n\treturn res\n```\n\nIf we look back, we can always transfer greedy to dp. But not every dp can be solved using greedy. Since you maynot always find the right properties to precompute, the only thing you can do is that you can repeatly ask yourself: HOW CAN I USE THE ALREADY COMPUTED RESULTS? I assume find this inner pattern is hard. Many named algorithms are greedy algorithms, making these greedy solutions as scientific discoveries . \n\n1. Kadane\'s Algorithm: It also solves a subarray problem. https://leetcode.com/problems/maximum-subarray\n2. Rabin Karp / KMP: It also solves a subarray problem. https://leetcode.com/problems/implement-strstr\n2. Dijkstra\'s Algorithm. https://leetcode.com/problems/network-delay-time/\n3. Kruskal\'s and Prim\'s Algorithm. https://leetcode.com/problems/min-cost-to-connect-all-points\n4. Kahn\'s Algorithm. https://leetcode.com/problems/course-schedule-ii/\n\nLet\'s we come back to our problem, it might not be straightforward to transfer from dp to greedy. But we can see we actually count the same subarray again and again, for `ABCDEF` and `BCDEF`, we actually do the same stuff repeatly. The question is how we can reduce this repetition. A more logical way is to design a better dp solution, but compute property on the fly is harder than preprocessing. The following solution is using preprocessing.\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n\n\tleft_bound = [-1] * n\n\tright_bound = [n] * n\n\n\tdic = {}\n\tfor i in range(n):\n\t\tch = s[i]\n\t\tif ch in dic:\n\t\t\tleft_bound[i] = dic[ch]\n\t\tdic[ch] = i\n\n\tdic = {}\n\tfor i in reversed(range(n)):\n\t\tch = s[i]\n\t\tif ch in dic:\n\t\t\tright_bound[i] = dic[ch]\n\t\tdic[ch] = i\n\n\tres = 0\n\tfor i in range(n):\n\t\tres += (i - left_bound[i]) * (right_bound[i] - i)\n\n\treturn res\n```\n\nTo come up a one pass solution, we need to find a on-the-fly dp solution. The following solution is harder to understand than the above one. It requires sophsicated dp updating and using prev dp results.\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n\tn = len(s)\n\tdic = defaultdict(lambda: [-1, -1])\n\n\tres = 0\n\tnew_uniq = 0\n\tfor i in range(n):\n\t\tsec_last, last = dic[s[i]]\n\t\tdic[s[i]] = [last, i]\n\n\t\tnew_uniq += (i - last) - (last - sec_last)\n\t\tres += new_uniq\n\n\treturn res\n```\n\nUsing this single problem with easy to understand description, the recuiter can test candidates with different levels of programming skills and combine multiple easy problems into one. How to design these problems?\n\n1. find an array problem, especially those calculate max / min / count properties\n2. make it an subarray problem, so that brute force can be used\n3. since it calculate max / min / count, for each subarray starting with i, the previous calculation is normally useful. So that we can use dp or remembering a few states.\n4. hopefully this problem can be solved using greedy, especially for those max / min or having boundaries, `(i - left) * (right - i)` will be the total.\n\nI don\'t know a robust technique to tell what kind of subarray problem can be solved O(N) or greedy in general. But at this moment, finding a greedy solution is like solving a Zelda dungeon. The reward is the journey itself.\n
[]