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:

• 0209. Minimum Size Subarray Sum

• 0315. Count of Smaller Numbers After Self

  • 0327. Count of Range Sum

  • 0493. Reverse Pairs

• 0307. Range Sum Query - Mutable

  • 0303. Range Sum Query - Immutable

  • 0308. Range Sum Query 2D - Mutable

  • 0304. Range Sum Query 2D - Immutable

• 0325. Maximum Size Subarray Sum Equals k

  • 0523. Continuous Subarray Sum: more of a math trick.

  • 0525. Contiguous Array

• 0437. Path Sum III

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

  • 0057. Insert Interval
  • 0352. Data Stream as Disjoint Intervals
  • 0715. Range Module
  • 0759. Employee Free Time
  • 0986. Interval List Intersections
• 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:

• 0238. Product of Array Except Self
• 0581. Shortest Unsorted Continuous Subarray