Array

Sum

• 303. Range Sum Query - Immutable: prefix sum

• No. 304: Range Sum Query 2D Immutable: integral image

• No. 416: Partition Equal Subset Sum: sum, dp(backpack) (use bit to reduce space );

  • Extention:

    http://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/

• No. 698: Partition to K Equal Sum Subsets: dfs

Product

• 238. Product of Array Except Self: Two times calculation O(n)

Majority

• 169. Majority Element: Moore Voting Algorithm

• No. 373 Find K Pairs with Smallest Sums: Moore Voting Algorithm https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations one counter

• No. 229 Majority Element II: Moore Voting Algorithm: two counter

Max Consecutive

• No. 485: Max Consecutive Ones

• No. 487: Max Consecutive Ones II https://eugenejw.github.io/2017/08/leetcode-487 (also applicable to 1004)

• No. 1004: Max Consecutive Ones III

  • O(1) space: moving window

  • time: queue

• No. 1446: Consecutive Characters (485)

• No. 1869: Longer Contiguous Segments of Ones than Zeros (485)

• No. 1784: Check if Binary String Has at Most One Segment of Ones (485)

• No. 1550: Three Consecutive Odds (485)

• No. 128: Longest Consecutive Sequence: Hashing

• No. 829: Consecutive Numbers Sum: calculation O(sqrt(N))

Amplitude

• No. 1509: Minimum Difference Between Largest and Smallest Value in Three Moves:

  • sort O(nlogn)

  • O(n). save (k+1) min and (k+1) max

  • extend to k moves. min-heap and max-heap. O(nlogk) time https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/discuss/1729942/Python3-(very)-simple-heapq-O(n-log-k)-99-memory

• Google Find the min amplitude after removing K consecutive elements in an array. https://leetcode.com/discuss/interview-question/1523646/google-find-the-min-amplitude-after-removing-k-consecutive-elements-in-an-array

  • window-left min and max, window-right min and max. O(n) time. O(n) space.

Kth

• No. 215 Kth Largest Element in an Array: Sort; Heap; Quick Select

• No. 230 Kth Smallest Element in a BST: tranverse; can add one element to the node

• No. 378 Kth Smallest Element in a Sorted Matrix: binary search; median of median + saddleback search https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

• No. 668 Kth Smallest Number in Multiplication Table: this is a sorted matrix

• No. 373 Find K Pairs with Smallest Sums: Heap: pointer

Stock:

• 121. Best Time to Buy and Sell Stock: (one whole transaction) Kadane's Algorithm(similar to maximum subarray, using difference between neighbors)

• No. 122: Best Time to Buy and Sell Stock II: (multiple times transactions) simple

• No. 123: Best Time to Buy and Sell Stock III:

  • (2 times -> k times) DP : f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions.

  • Thinking: max k subarray sum

  • some states: states[][0]: one buy; states[][1]: one buy, one sell; states[][2]: two buys, one sell; states[][3]: two buy, two sell sol

• No. 188: Best Time to Buy and Sell Stock IV:

  • sol Using DP solution with O(kn) time O(k) space

  • sol Using O(n + klgn) time using Max Heap and Stack keep the highest k ones.(not the best)

• No. 309: Best Time to Buy and Sell Stock with Cooldown

  • DP: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/?currentPage=1&orderBy=hot&query=

• No. 714: Best Time to Buy and Sell Stock with Transaction Fee: Dynamic programming with 2 variables: hold and sell. O(n) time & O(1) space

Trapping Water/Rain

• 11. Container With Most Water Two-pointer

• 42. Trapping Rain Water: Two-pointer

Other:

• No. 189 Rotate Array: Copy; O(1)-tmp memory; Reverse two set and Reverse all

• No. 632: Smallest Range: K merge sort

• No. 697: Degree of an Array: Hashmap

• 605. Can Place Flowers: add front and end, edit in array

• 3354. Make Array Elements Equal to Zero: simulation, prefix sum