Array
Range sum(subarray/matrix)
Essentially, this kind of problem can be solved with prefix sum. But search prefix sum takes O(N), how can we accelerate? Use Binary Index Tree(BIT) which guarantee O(logN) for searching an accumulated sum.
So to find the sum of a range, these are typical solutions:
Prefix sum. Works for array: Sum(i, j) = prefixSum[j] - prefixSum[i-1], i is inclusive.
0325. Maximum Size Subarray Sum Equals k
Trick:
map.put(0, -1);, this means Sum(0, i), i.e. prefixSum[i], is what we want.
Binary Index Tree(BIT). When prefixSum1 is known, we need to find another prefixSum2 that meets some constraint, e.g. prefixSum1 - prefixSum = k.
We can also build BST to achieve similar O(logN) search, but worst case is still O(N).
Segment Tree. Mostly used in range sum lookup.(Not used in search cases)
Typicall questions:
0325. Maximum Size Subarray Sum Equals k
0523. Continuous Subarray Sum: more of a math trick.
Interval problems
Interval problem typically cope with a range: a start point, a end point, and optionally some attributes of this interval, like 0218. The Skyline Problem. It almost always requires sorting. Since it's O(NlogN) anyway, always try TreeMap.
Typicall ideas:
Just sort it and iterate
PriorityQueue. When we need to know how many accumulative intervals at some point.
2 sorted arrays: 1 for start points, 1 for end points
1 sorted array to store all points.
You can store them as array of classes, like 0218. The Skyline Problem.
Alternatively, why not just use TreeMap. Built-in APIs are amazing!
Typical questions:
TreeMap is your friend. Calendar problem optimal is O(N).
0218. The Skyline Problem: Key is how to order multiple points, high->low start points, then low->high end points.
0699. Falling Squares: Key is how to update TreeMap.
make use of index
match nums[i] with i
https://leetcode.com/problems/first-missing-positive/description/ https://leetcode.com/problems/missing-number/description/ https://leetcode.com/problems/find-the-duplicate-number/description/ https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/ https://leetcode.com/problems/find-all-duplicates-in-an-array/description/ https://leetcode.com/problems/couples-holding-hands/description/
Peak and Valley
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
sliding to find peak or valley
K sum problem
2 pointers: https://leetcode.com/problems/two-sum https://leetcode.com/problems/two-sum-ii-input-array-is-sorted https://leetcode.com/problems/two-sum-iii-data-structure-design https://leetcode.com/problems/two-sum-iv-input-is-a-bst https://leetcode.com/problems/3sum https://leetcode.com/problems/3sum-closest https://leetcode.com/problems/3sum-smaller https://leetcode.com/problems/valid-triangle-number/description/ https://leetcode.com/problems/4sum https://leetcode.com/problems/4sum-ii
hash map:
https://leetcode.com/problems/two-sum https://leetcode.com/problems/subarray-sum-equals-k/description/ https://leetcode.com/problems/two-sum-iv-input-is-a-bst https://leetcode.com/problems/4sum-ii
Avoid duplicate
1) sort and skip same value, if (nums[i] == nums[i-1]) continue; https://leetcode.com/problems/combination-sum-ii/description/ 2) when it can't be sort, use array or set at this level; https://leetcode.com/problems/increasing-subsequences/description/
Trap water
https://leetcode.com/problems/container-with-most-water/description/ https://leetcode.com/problems/trapping-rain-water/description/ https://leetcode.com/problems/trapping-rain-water-ii
Two pass
1 from left and 1 from right:
Last updated
Was this helpful?