> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/array.md).

# 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](/leetcode/solutions/0325-maximum-size-subarray-sum-equals-k.md)
    * 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](/leetcode/solutions/0315-count-of-smaller-numbers-after-self.md)
  * [0327. Count of Range Sum](/leetcode/solutions/0327-count-of-range-sum.md)
* Segment Tree. Mostly used in range sum lookup.(Not used in search cases)
  * [0307. Range Sum Query - Mutable](/leetcode/solutions/0307-range-sum-query-mutable.md)

Typicall questions:

* [0209. Minimum Size Subarray Sum](/leetcode/solutions/0209-minimum-size-subarray-sum.md)
* [0315. Count of Smaller Numbers After Self](/leetcode/solutions/0315-count-of-smaller-numbers-after-self.md)
  * [0327. Count of Range Sum](/leetcode/solutions/0327-count-of-range-sum.md)
  * [0493. Reverse Pairs](/leetcode/solutions/0493-reverse-pairs.md)
* [0307. Range Sum Query - Mutable](/leetcode/solutions/0307-range-sum-query-mutable.md)
  * [0303. Range Sum Query - Immutable](/leetcode/solutions/0303-range-sum-query-immutable.md)
  * [0308. Range Sum Query 2D - Mutable](/leetcode/solutions/0308-range-sum-query-2d-mutable.md)
  * [0304. Range Sum Query 2D - Immutable](/leetcode/solutions/0304-range-sum-query-2d-immutable.md)
* [0325. Maximum Size Subarray Sum Equals k](/leetcode/solutions/0325-maximum-size-subarray-sum-equals-k.md)
  * [0523. Continuous Subarray Sum](/leetcode/solutions/0523-continuous-subarray-sum.md): more of a math trick.
  * [0525. Contiguous Array](/leetcode/solutions/0525-contiguous-array.md)
* [0437. Path Sum III](/leetcode/solutions/0437-path-sum-iii.md)

## 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](/leetcode/solutions/0218-the-skyline-problem.md). It almost always requires sorting. Since it's O(NlogN) anyway, always try TreeMap.

Typicall ideas:

* Just sort it and iterate
  * [0056. Merge Intervals](/leetcode/solutions/0056-merge-intervals.md)
* PriorityQueue. When we need to know how many accumulative intervals at some point.
  * [0253. Meeting Rooms II](/leetcode/solutions/0253-meeting-rooms-ii.md)
* 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](/leetcode/solutions/0218-the-skyline-problem.md).
  * Alternatively, why not just use [TreeMap](https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html). Built-in APIs are amazing!
    * [0715. Range Module](/leetcode/solutions/0715-range-module.md)
    * [0732. My Calendar III](/leetcode/solutions/0732-my-calendar-iii.md)

Typical questions:

* [0056. Merge Intervals](/leetcode/solutions/0056-merge-intervals.md)
  * [0057. Insert Interval](/leetcode/solutions/0057-insert-interval.md)
  * [0352. Data Stream as Disjoint Intervals](/leetcode/solutions/0352-data-stream-as-disjoint-intervals.md)
  * [0715. Range Module](/leetcode/solutions/0715-range-module.md)
  * [0759. Employee Free Time](/leetcode/solutions/0759-employee-free-time.md)
  * [0986. Interval List Intersections](/leetcode/solutions/0986-interval-list-intersections.md)
* [0253. Meeting Rooms II](/leetcode/solutions/0253-meeting-rooms-ii.md)
  * [0729. My Calendar I](/leetcode/solutions/0729-my-calendar-i.md)
    * TreeMap is your friend. Calendar problem optimal is O(N).
  * [0731. My Calendar II](/leetcode/solutions/0731-my-calendar-ii.md)
  * [0732. My Calendar III](/leetcode/solutions/0732-my-calendar-iii.md)
* [0218. The Skyline Problem](/leetcode/solutions/0218-the-skyline-problem.md): Key is how to order multiple points, high->low start points, then low->high end points.
* [0436. Find Right Interval](/leetcode/solutions/0436-find-right-interval.md)
* Greedy:
  * [0452. Minimum Number of Arrows to Burst Balloons](/leetcode/solutions/0452-minimum-number-of-arrows-to-burst-balloons.md)
  * [0435. Non-overlapping Intervals](/leetcode/solutions/0435-non-overlapping-intervals.md)
* [0699. Falling Squares](/leetcode/solutions/0699-falling-squares.md): 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

```java
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](/leetcode/solutions/0238-product-of-array-except-self.md)
* [0581. Shortest Unsorted Continuous Subarray](/leetcode/solutions/0581-shortest-unsorted-continuous-subarray.md)