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).
- 0315. Count of Smaller Numbers After Self
- 0327. Count of Range Sum
Segment Tree. Mostly used in range sum lookup.(Not used in search cases)
- 0307. Range Sum Query - Mutable

Typicall questions:

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
- 0056. Merge Intervals
PriorityQueue. When we need to know how many accumulative intervals at some point.
- 0253. Meeting Rooms II
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!
  - 0715. Range Module
  - 0732. My Calendar III

Typical questions:

0056. Merge Intervals
0253. Meeting Rooms II
- 0729. My Calendar I
  - TreeMap is your friend. Calendar problem optimal is O(N).
- 0731. My Calendar II
- 0732. My Calendar III
0218. The Skyline Problem: Key is how to order multiple points, high->low start points, then low->high end points.
0436. Find Right Interval
Greedy:
- 0452. Minimum Number of Arrows to Burst Balloons
- 0435. Non-overlapping Intervals
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

for (int i = 0; i < prices.length; i++) {
    while (i < prices.length - 1 && prices[i] >= prices[i+1]) i++;
    buy = prices[i];

    while (i < prices.length - 1 && prices[i] <= prices[i+1]) i++;
    profit += prices[i] - buy;
}

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:

PreviousString NextStack

Last updated 2 years ago