Data Structure: Array - swchen1234/Algorithm GitHub Wiki

Technique to solve varys, often involved other data structure or algorithm, such as hash table, dynamic programming. Common techniques include following,

*** Tips from EPI ***

• Array problem often have simple solution using O(n) space, but there are subtler solution that use the array itself to reduce space complexity to O(1).
• Filling an array is slow => write value from the back.
• Integer represented in array => process from the back.
• It is very easy to make off-by-1, past-by-one mistake.
• Some time just allocate array of size n + 1 to simplify the indexing.

//Allocating and Instantiation an array and vector:
vector<int> A = {1, 2, 3}
array<int, 3> A = {1, 2, 3}

//Allocating and Instantiation an 2D array and vector:
vector<vector<int>> A = {{1,2},{3,4}, {5,6}}
array<array<int, 2>, 3> A = {{1,2},{3,4}, {5,6}}

Kadane Algorithm（dynamic programming)

    def maxSubArray(self, nums: List[int]) -> int:
        res = float('-inf')
        curr = 0 #表示以当前元素为结束的字串的最大和
        for num in nums:
            curr = max(curr + num, num)
            res = max(res, curr)
        return res

53. Maximum Subarray
560. Subarray Sum Equals Kone pass, 同时将cum存入hash中
918. Maximum Sum Circular Subarray化为max(max_subarray_sum， total - min_subarray_sum) => Kadane's algo)
152. Maximum Product Subarray完全同918
3356. Zero Array Transformation II遍历每个val, 若不足以被覆盖，则增加query， 结合diff[query_l] += 1, diff[query_r + 1] -= 1的方法，可以优化至O(n+m) 1769. Minimum Number of Operations to Move All Balls to Each Box从左至右遍历，res[i] += leftSteps, 若遇到1,leftCount+1, leftSteps += leftCount;同理从右至左遍历
3410. Maximize Subarray Sum After Removing All Occurrences of One ElementKadane Algo变种：用pre[num]记录删除num及其之前的左区间所能达到的最小值， pre[0]表示左边区间最小值，minVal = min(pre[0], pre[num]), 则以num+1为右端点所能达到的最大值为cum - minVal\

68. Text Justificationcase 1: 遍历word, 当currLen + wordCnt + len(word) > maxWidth时，word之前的单词成行，空格, extraSpace = divmod(spaceTotalLen, wordCnt）得到；case2: 一个单词组成一行；case 3:最后行
273. Integer to English Words设div=10^9, 每次处理三个数,{1.百味以上+Hundred， 2.20以上，3. 20以内}, div //=1000
251. Flatten 2D Vector共同调用advance_to_next()函数：若j==len(vec[i]）,则将指针移至下一行
755. Pour Water无论往左往右，水只会落在最后次下降的位置，while A[i-1]<=A[i]{往左,同时若A[i-1]<A[i],则更新write 指针}, 向右同理操作\

799. Champagne Tower

Use water[i][j] to represent the water should be poured over glass at ith-row, jth-glass. 从上至下遍历，若杯子水量q>1,则(q - 1)/2 的水流至下层的左右两杯子

957. Prison Cells After N Days

Use a hash map to store the exisiting status to its first appearance day, once reappeared, then there is a cycle.

900. RLE Iterator

54. Spiral Matrix Four position boundary are used, top, down, left, right. First iterator outside circle, then second outside circle and so on. until top < down || left > right. 794. Valid Tic-Tac-Toe State根据X和O的个数以及输赢状况结合出多种invalid case
2043. Simple Bank System看似很简单，但有陷阱：transfer时，如果withdraw成功而deposit失败，那么需要将withdraw的放回；为了方便执行，最好的办法是在每次withdraw/deposit执行之前先确保valid,再开始交易\

1041. Robot Bounded In Circledi表示dirs的指针，按照指令执行，当最终返回（0，0）或者方向不指向北，则可能成环\

121. Best Time to Buy and Sell Stocktrack minPrice, 每次更新res
Best Time to Buy and Sell Stock IIJust add the increments.
299. Bulls and Cows用h[c]记录guess和secret目前为止出现过字母的平衡，h[c]<0代表secret出现的更多，h[c]>0代表guess出现的更多，若完全match不影响h[]
334. Increasing Triplet Subsequence

Maintain two varialbe which always maintain the lowest and second lowest element seen so far. if an element is smaller than the lowest, just update it without change the second lowest element. Because when we decide if there is a qualified answer or not, we only compare it with the second lowest. The lowest is updated only to update the second lowest. 方法同300. Longest Increasing Subsequence

One thing to keep in mind is every time we compare <= instead of <, because we don't we want to have an element exact same as the first one to update the second element, and similar for the exact same second element.

763. Partition Labels用last[c]记录每个字母最右出现的位置，遍历字符串，若i > end, 则添加至答案，否则衍生end.
926. Flip String to Monotone Increasing把数组分为左右两部分，希望左边都是0， 右边都是1，则flips = left ones + right zeros， 一开始cutoff在数组最左边,逐个移动cutoff， 根据为1还是0, 决定flip的变化\

1351. Count Negative Numbers in a Sorted Matrix从右上开始向左找到第一个>0的指数j， 在往下
2938. Separate Black and White Balls遍历一次，记录当前指针i左边有多少黑球，若读到白球，则需要与左边所有黑球交换，res += blackBalls\

Rotate Array Four Approaches: 1) Burte Force, rotation k times. 2) Use Extra Array 3) Cyclic Rotation where each element is placed at right position exactly once. 4) Three times reverse.

Rotate Image First rotate up to down, then rotate along diagonal.

Game of Life Notice there are four starting and ending status combination, to avoid confusing the new status with old status. We encode the changing status to other number and change it back after we visit all nodes.

442. Find All Duplicates in an Array Setting the number index by the element to be negative, when meet negative num, we know it has been set already.

73. Set Matrix Zeroes 用hash解， 因为用in place change value会使问题更复杂。 This can solved by setting the first row M[0][j] and first col M[i][0] to zero if M[i][j] == 0, and then change the whole row/col int he second iteration. To distinguish M[0][0] == 0 is caused by first row or first col, we use an extra boolean to indicate if there any zero in the first row.\

498. Diagonal Traverse设置up boolean flag,向上时若j==m-1 =>下一行开始;若i==0 =>下一列开始；
723. Candy Crush将欲消掉的元素mark为负数\

41. First Missing Positive

We iterate each element, if its not at right position, we put it at the correct_idx(correct_idx = nums[i], until we encounter an element already at its right position(correct_idx == nums[correct_idx] - 1). Then we iterate the next element. No element will be moved twice, since if it is already at right position in previous cycle swap, then we just skip it.

287. Find the Duplicate Number 题目要求O(1) space, 且不能修改原数组。This is actually a question looking for the start of the cycle. Famous Algo: Floyd Tortoise and Hare, where a hare and a tortoise pointer is used. when the two meet, move the hare to the beginning and let them move at the same speed until meets again. 相关题：442. Find All Duplicates in an Array \

556. Next Greater Element III This is said to be equivalent to next_permutation(a STL function). I originally use a multiset to maintain the sorted order when visiting from the back. But no extra data structure is needed actually. The reason is that, the point is to find the first descreasing element from back to end, so all the visited elemnents are in increasing order. Once we find the first descreasing element, we swap it with the fist element bigger than it in the elements later than it. and the remaining is garuanteed to be in decreasing order, we just need to reverse it. Done!

5. Longest Palindromic Substring This can be solved 1) DP 2).find longest palindrom around each center(i = 1,... n).

415. Add Strings设i1, i2分别指向num1, num2尾部，用carry逆向相加，添加至res, 最后res翻转\

336. Palindrome Pairs 分为三种情况：1. word==word[::-1] 2. word1=TAC, word2=xxxxxCAT 3.word1=TACxxxxx word2=CAT; case2, case3处理时可能会漏了左右palindrom为空的情况，窍门是当中的那部分palindrom不可以为空，否则就成了case 1

564. Find the Closest Palindrome 三种特殊情况：1.10^n或<10 2.100001 3.99999. 除此之外，找到左半部分left， 分别-1得small, +1得big, 找到left+left[::-1], small+small[:-1]和big+big[::-1]中离target最近的

214. Shortest Palindrome

This is a hard problem, but can be solved in O(n) with KMP algo. The problem can be converted to find the longest palindrome starting from index 0, and add the reverse of the remaining to the front. How to find the longest palindrome? once we find the longest matching prefix of s and suffix of reverse s ending at the last element, then that is a palindrome. It can be solved by construct s + '#' + reverse_s, and use the KMP algo to construct the suffix/prefix matching table. 2663. Lexicographically Smallest Beautiful String从最后字符开始，若+1 后1）仍为前k个字母，2）与前两个字母不同，则符合条件，s[i]+=1， s[i+1:]之后的字符从a开始正序组成，仍采用相同的条件1）2）构成\

859. Buddy Strings三种情况：1.长度不一致 2.s==g：是否有重复字符 3.s!=g时遍历zip(s,g)\

66. Plus One从最后位开始往前直至digits[i] != 9 1257. Smallest Common Region类似于lowest common ancestor, 但是不需要build two paths；先建立graph， 从region1开始向上走直到root，放入ancestorSet中，然后从region2开始向上，直到和ancestorSet有交集
2870. Minimum Number of Operations to Make Array Empty用counter统计好后，对每个字母的count进行判断
238. Product of Array Except Self Each value corresponding to the product of its left accumulative and right accumulative, so one forward and one back ward pass is enough.

14. Longest Common Prefix多种解法，horizontal scan, vertical scan, Divide & Conquer, Binary Search, Trie. \

161. One Edit Distance递增i，j直至s[i] != t[j], 判断剩下的字串是否满足三种情况之一。
179. Largest Number化为str来比较，sorted(tmp, key = cmp_to_key(lt)), lt中，通过s1+s2<s1+s2来比较s1, s2
722. Remove Comments设置in_block变量，遍历每行，仅当temp不为空且not in block时，将temp加入res
468. Validate IP Address根据split(':')和spplit('.')来决定verify IP4还是IP8
640. Solve the Equation左右分别统计x的个数和constant, 再化简；在统计单侧时，系数用string积累，遇到+-x 后再化为整数，若默认系数为0，且使用coef*10+int(c)的方法，会与系数=0无法分辨\

1657. Determine if Two Strings Are Close 1755. Closest Subsequence SumMeet in the middle：切为两半，对于每半找到所以可能的subset sum， 对于first half的每一个subset sum, 在second half的subset sum用二分法查找
2035. Partition Array Into Two Arrays to Minimize Sum Difference1735的延伸，分为左右两半后，分别记录subsetSum = {...}, 对于每个k以及subsetSum[k]中的每个sum, 找到右边subsetSum[n/2-k]中离total/2-左边[k],sum最接近sum)\

767. Reorganize String法一：yong heap存cnt, 每次pop出出现最多的字母，若与之前字母相同，再pop出下一个次高频字母， O(nlgk)。 法二：for letter，cnt in Counter(s): 间隔地放入相同字母,O(n)
2094. Finding 3-Digit Even Numbers遍历百、十、个位数， 判断所组成的Counter([i,j,k])是否<=Counter(nums)\