After almost finishing all the dichotomies, I found these things… (below)

preface

Hi, I’m Lucifer. Today I bring you a special topic called “Dichotomy”. First of all, the outline of this paper is a brain map I drew with MindMap. Later, I will continue to improve and gradually improve other topics.

You can also use vscode blink-mind to open the source file and view some notes in it. The source files can be obtained by replying to the brain map on my public account “Likou Jiajia”, and the brain map will continue to update more content in the future. Vscode plug-in address: marketplace.visualstudio.com/items?itemN…

This series includes the following topics:

• After almost finishing all the links, I found these things…
• Almost finished brushing all the tree buttons, I found these things…
• After almost finishing all the questions, I found these things… (on)
• After almost finishing all the questions, I found these things… (below)
• After almost finishing all the dichotomies, I found these things… (on)

This topic is expected to be carried out in two parts. The last section focused on the basic concepts and a focus. In this video, we’ll continue learning about two dichotomous types and four applications. Have a look at the previous article before reading the advice, the address is above.

If you find the article useful, please like it and leave a comment to forward it so that I will be motivated to continue doing it.

Detailed review

The last part is mainly to introduce you to a few concepts, these concepts are very important for the problem, please be sure to grasp. And then we have the center of the dichotomy, the half, and this center requires you to do any dichotomy in your head.

The essence of dichotomy as mentioned at the beginning is that dichotomy is an algorithm that makes the unknown world impossible to multiply. The dichotomy we can give up half of the solution anyway, so we can cut the solution space in half anyway. The difficulty is the two points mentioned above: what conditions and what parts to leave out.

Next, let’s move on to the next chapter. The next note mainly covers two types and four applications.

And the two main types of these are: my solution space for this problem and how to use code to figure out what the values are. The four main applications are: how to construct solution Spaces (more often, ordered sequences) and some variations.

These two parts are very practical content. I want to remind you that as you understand these two parts, you must keep in mind one central half.

Two types of

Problem definition

The definition of the problem here is narrow. Once you understand the problem, you can generalize the specific problem to fit more complex problems. We’ll talk about promotion later.

Given an ordered array of numbers, nums, and given you a numeric target. Ask if target exists in NUMS. If it exists, its index in NUMS is returned. If none exists, -1 is returned.

This is the simplest form of binary lookup. Of course, binary search also has a lot of deformation, this is binary search prone to error, difficult to master the reason.

Common variants are:

• If there are multiple elements that meet the criteria, return the leftmost index that meets the criteria.
• If there are multiple elements that meet the condition, return the rightmost index that meets the condition.
• Arrays are not uniformly ordered. Such as ascending to descending, or descending to ascending.
• Turn a one-dimensional array into a two-dimensional array.
• .

Next, let’s take a look at each one.

The premise

• The array is ordered (if it is unordered, we can also consider sorting, but be careful about the complexity of sorting)

This ordered array may have been given directly by the problem, or you may have constructed it yourself. For example, if you want to find the number of inversions of an array, you can divide an ordered sequence of your own.

The term

It is necessary to introduce some conventions and terminology to help describe the problem later.

Terms used in binary lookup:

• Target – The value to look for
• Index — Current position
• L and R — left and right Pointers
• Mid – The midpoint of the left and right pointer, the index used to determine whether we should look left or right.

It is important to note that everything is dynamic except target, which is fixed. Where L and R refer to the upper and lower bounds of the solution space, mid is the middle value of the upper and lower bounds, and index is the traversal pointer used to control the traversal process.

Find a number

We have already defined the problem. Next, we need to analyze and solve the defined problem.

To better understand what’s next, let’s tackle the simplest type – looking for a specific value.

Algorithm description:

• We start with the middle element of the array. If the middle element is exactly the element we are looking for, the search process ends.
• If the target element is greater than the middle element, then any value in the array that is less than the middle element can be excluded (since the array is ordered, then all values on the left side of the array can be excluded), and the solution space can be shrunk to [mid+1, r].
• If the target element is smaller than the middle element, then any value larger than the middle element in the array can be excluded (since the array is ordered, then all values on the right side of the array can be excluded), and the solution space can be shrunk to [L, mid-1].
• If the solution space is empty at a certain step, it cannot be found.

Let me give you a concrete example to help you get a sense of substitution. Assume that nums is [1,3,4,6,7,8,10,13,14] and target is 4·.

• We started with 7 in the middle of the array
• 7 is greater than 4, and since all the numbers to the right of 7 are greater than 7, it can’t be the answer. We abbreviate the range to the left of 7.

• The solution space becomes [1,3,4,6], and the middle element is 3.
• 3 is less than 4, and since all the numbers to the left of 3 are less than 3, it can’t be the answer. We abbreviate the range to the right of 3.

• The solution space becomes [4,6], and the middle element is 4, which is exactly what we are looking for. Return its index 2.

Complexity analysis

Because this search algorithm reduces the search scope by half every time, it is a typical binary search.

• Average time complexity: O(logN)O(logN)O(logN)
• Worst time complexity: O(logN)O(logN)O(logN)
• Spatial complexity
  • Iterations: O (1) O (1) O (1)
  • Recursion: O(logN)O(logN)O(logN) (no-tail call elimination)

The following complexity is similar and will not be repeated.

Thinking framework

How do you translate the above algorithm into executable code that is easy to understand?

Don’t underestimate an algorithm like this. Even such a simple, unpretentious binary search, different people write out the difference is also very big. If you don’t have a frame of mind to guide you, you may write very different code at different times. In this way, the chances of making mistakes are greatly increased. Here’s a thought frame and code template I use a lot.

I’m going to define my solution space as [left, right], and notice that it’s closed, and then I’m going to use this point

You can define other forms of the solution space, but the code will change accordingly, so you can try other solution Spaces if you’re interested.

• Since the solution space is defined as [left, right], when left <= right, the solution space is not empty, so we need to continue searching. That is, the termination search condition should be left <= right.

An example makes it easier to understand. For example, for the interval [4,4], it contains an element 4, so the solution space is not empty and we need to continue searching (just think that 4 is the target we are looking for, if we do not continue searching, we will miss the correct answer). When the solution space is [left, right), the solution space is also empty for [4,4], because there is no digit · in such an interval.

• In the circulatory body, we continuously calculate mid and compare NUMS [mid] to the target value.
  • If nums[mid] is equal to the target value, return mid ahead of time.
  • If nums[mid] is less than the target value, the target value is to the right of mid. In this case, the solution space can be reduced to [mid + 1, right] (mid and the digits left of mid are excluded).
  • If nums[mid] is greater than the target value, the target value is to the left of mid. In this case, the solution space can be reduced to [left, mid-1] (mid and digits to the right of mid are excluded).
• If the loop is not found, it indicates that the loop is not found. If -1 is returned, it indicates that the loop is not found.

The code template

Java

public int binarySearch(int[] nums, int target) {
    [l, r] [l, r]
    int left = 0;
    int right = nums.length - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        if (nums[mid] < target)
			      [mid+1, right]
            left = mid + 1;
        if (nums[mid] > target)
            // The solution space becomes [left, mid-1]
            right = mid - 1;
    }
    return -1;
}
Copy the code

Python

def binarySearch(nums, target) :
    # Interval where left and right are closed [l, r]
    l, r = 0.len(nums) - 1
    while l <= r:
        mid = (left + right) >> 1
        if nums[mid] == target: return mid
        [mid+1, right]
        if nums[mid] < target: l = mid + 1
        The solution space becomes [left, mid-1]
        if nums[mid] > target: r = mid - 1
    return -1

Copy the code

JavaScript

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] == target) return mid;
    if (nums[mid] < target)
      [mid+1, right]
      left = mid + 1;
    if (nums[mid] > target)
      // The solution space becomes [left, mid-1]
      right = mid - 1;
  }
  return -1;
}
Copy the code

C++

int binarySearch(vector<int>& nums, int target){
  if(nums.size() = =0)
    return - 1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    int mid = left + ((right - left) >> 1);
    if(nums[mid] == target){ return mid; }
    [mid+1, right]
    else if(nums[mid] < target)
	left = mid + 1;
    // The solution space becomes [left, mid-1]
    else
	right = mid - 1;
  }
  return - 1;
}
Copy the code

Look for the left-most insertion position

So we talked about finding values that satisfy this condition. If it can’t find it, it returns -1. What if instead of returning -1, we return where we should insert, so that the list is still in order?

For example, an array nums: [1,3,4] whose target is 2. We should insert it (note not really insert) at the position of index 1, [1,2,3,4]. So finding the leftmost insertion position should return 1, and finding a position that satisfies the condition should return -1.

In addition, if there are multiple values that satisfy the condition, we return the leftmost value. For example, an array nums: [1,2,2,2,3,4], target is 2, and the position we should insert is 1.

Thinking framework

Specific algorithm:

• I’m going to define my solution space as [left, right], and notice that it’s closed, and then I’m going to use this point.

You can define other forms of the solution space, but the code will change accordingly, so you can try other solution Spaces if you’re interested.

• Since we define the solution space as [left, right], the solution space is not empty when left <= right. That is to say, our termination search condition is left <= right.

• If A[mid] >= x, it indicates that A spare tire has been found. We set r = mid-1 to exclude mid from the solution space and continue to see if there is A better spare tire.

• If A[mid] < x, mid is not the answer at all. If l = mid + 1, mid is excluded from the solution space.

• And then finally l of the solution space is the best spare, and the spare turns positive.

The code template

Python

def bisect_left(nums, x) :
    # built-in API
    bisect.bisect_left(nums, x)
    # handwritten
    l, r = 0.len(A) - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] >= x: r = mid - 1
        else: l = mid + 1
    return l
Copy the code

Look for the right-most insertion position

Thinking framework

Specific algorithm:

• I’m going to define my solution space as [left, right], and notice that it’s closed, and then I’m going to use this point.

You can define other forms of the solution space, but the code will change accordingly, so you can try other solution Spaces if you’re interested.

• Since we define the solution space as [left, right], the solution space is not empty when left <= right. That is to say, our termination search condition is left <= right.

• If A[mid] > x indicates that A spare tire is found, we set r = mid-1 to exclude mid from the solution space and continue to see if there is A better spare tire.

• If A[mid] <= x, mid is not the answer at all. If l = mid + 1, mid is excluded from the solution space.

• And then finally l of the solution space is the best spare, and the spare turns positive.

The code template

Python

def bisect_right(nums, x) :
    # built-in API
    bisect.bisect_right(nums, x)
    # handwritten
    l, r = 0.len(A) - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] <= x: l = mid + 1
        else: r = mid - 1
    return l
Copy the code

So those are the two basic forms of dichotomy. In actual code, INSTEAD of finding a value template that meets the criteria, I insert the template directly to the left or right. Why is that? Because the latter includes the former, and the former can not achieve the function. If nums[I] is equal to target, return -i. If nums[I] is equal to target, return -i. If nums[I] is equal to target, return -i. That’s why I divide dichotomies into two types, not three or even four.

In addition, left-most insertion and right-most insertion can be used together to find the number of numbers equal to target in an ordered sequence, which is sometimes a good idea. Code representation:

nums = [1.2.2.2.3.4]
i = bisect.bisect_left(nums, 2) # get 1
j = bisect.bisect_right(nums, 2) # get 4
# j-i is the number of 2's in nums
Copy the code

Bisect. Bisect. Bisect. Bisect.

summary

For binary problems, the solution space should be defined first, and then half of the solutions should be discarded according to certain conditions (usually compared with the median value). You can start by looking for dichotomies of values that satisfy this condition, and then learn the leftmost and rightmost dichotomies. At the same time, you only need to know the left and right dichotomy, because the latter is more powerful than the former.

For the left-most and right-most dichotomies, a simple two-sentence summary:

1. The left-most dichotomy continuously shrinks the right boundary and eventually returns to the left boundary

2. The right-most binary continuously shrinks the left boundary and returns the right boundary

The four applications

The basic knowledge is laid almost. Next, let’s move on to dry goods techniques.

Next up:

• Ability detection and counting dichotomy are similar in nature, both are generalizations of ordinary dichotomy.
• Prefix and dichotomy and insertion sort dichotomy are essentially building ordered sequences.

So let’s get started.

Ability test dichotomy

Dichotomy of capability detection is generally: define the function possible, the parameter is mid, and the return value is Boolean. The outer layer adjusts the “solution space” based on the return value.

Sample code (using the left-most binary example) :

def ability_test_bs(nums) :
  def possible(mid) :
    pass
  l, r = 0.len(A) - 1
  while l <= r:
      mid = (l + r) // 2
      # Only here is different from the left half
      if possible(mid): l = mid + 1
      else: r = mid - 1
  return l
Copy the code

In contrast to the most basic dichotomy types, the ability dichotomy simply adjusts the if statement inside a while to a function. Therefore, the dichotomy of ability test can be divided into two basic types: leftmost and rightmost.

Basically anyone can use this pattern. With a clear understanding of the framework of the problem, let’s finally look at what problems can be solved by the ability test dichotomy. Here through three questions to take you to feel, there are many similar questions, you experience after class.

875. Ke Ke who Loves bananas (medium)

Title address

Leetcode-cn.com/problems/ko…

Topic describes

Ke Ke likes bananas. There were N piles of bananas and piles I had piles of bananas. The guard has left and will be back in H hours. Coco can determine the rate at which she eats the banana, K (roots per hour). Every hour, she will choose a bunch of bananas and eat K of them. If there are less than K bananas in the pile, she will eat all the bananas in the pile and will not eat any more bananas for an hour. Ke liked to eat slowly, but still wanted to eat all the bananas before the guards came back. Returns the minimum speed at which she can eat all bananas in H (K is an integer). Example 1: inputs: haemi = [3,6,7,11], H = 8 Example 2: inputs: haemi = [30,11,23,4,20], H = 5 Example 3: inputs: Haemoglobin = [30,11,23,4,20], H = 6 haemoglobin: 1 <= haem. length <= 10^4 haem. length <= H <= 10^9 1 <= haem. [I] <= 10^9Copy the code

Front knowledge

• Binary search

The company

• byte

Train of thought

And they say let’s figure out the minimum speed at which we can eat all the bananas in H hours.

The intuitive thing to do is to enumerate all the possible speeds, find all the speed at which you can eat the banana, and then choose the lowest speed. Because you want to return the minimum speed, it is better to choose the minus-to-large enumeration because you can exit early. The solution has a high time complexity of O(N∗M)O(N * M)O(N∗M) O(N∗M), where N is the piles length and M is the largest number in the piles (i.e., the maximum solution space).

Observing that the solution space to be detected is an ordered sequence, it should be thought possible to solve it using dichotomy rather than linear enumeration. The key thing that can be solved with dichotomy is exactly the same as the dichotomy problem that we simplified earlier, but the key thing is that if velocity K can’t eat all the bananas, then all solutions less than or equal to k can be eliminated.

The key to binary solution lies in:

• Specify the solution space. For this problem, the solution space is [1, Max (Piles)].
• How to shrink the solution space. The point is that if speed K can’t eat all the bananas, then all solutions less than or equal to k can be eliminated.

To sum up, we can use the leftmost dichotomy, that is, constantly shrinking the right boundary.

The maximum number of bananas in a banana pile is 10 to the ninth.

Key point resolution

• Binary search template

code

Code support: Python, JavaScript

Python Code:

class Solution:
    def solve(self, piles, k) :
        def possible(mid) :
            t = 0
            for pile in piles:
                t += (pile + mid - 1) // mid
            return t <= k

        l, r = 1.max(piles)

        while l <= r:
            mid = (l + r) // 2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

Copy the code

JavaScript Code:

function canEatAllBananas(piles, H, mid) {
  let h = 0;
  for (let pile of piles) {
    h += Math.ceil(pile / mid);
  }

  return h <= H;
}
/ * * *@param {number[]} piles
 * @param {number} H
 * @return {number}* /
var minEatingSpeed = function (piles, H) {
  let lo = 1,
    hi = Math.max(... piles);// [l, r], the advantage is that if you can find it, then return l and r are the same, because finally l is equal to r.
  while (lo <= hi) {
    let mid = lo + ((hi - lo) >> 1);
    if (canEatAllBananas(piles, H, mid)) {
      hi = mid - 1;
    } else {
      lo = mid + 1; }}return lo; // Cannot select hi
};
Copy the code

Complexity analysis

• Time complexity: O(Max (N,N∗logM))O(Max (N,N * logM))O(Max (N,N∗logM)), where N is the piles length and M is the maximum number in the piles.
• Space complexity: O(1)O(1)O(1)

Minimum lamp radius (difficult)

Topic describes

You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [3, 4, 5, 6]
Output
0.5
Explanation
If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.
Copy the code

Front knowledge

• The sorting
• dichotomy

dichotomy

Train of thought

This case is similar to likou 475. Heater.

Given an array of nums, let you place 3 lights in the range [min(nums), Max (nums)], each with a radius of R, and let you find the smallest r.

Positions less than min(nums) and greater than Max (nums) are not selected because they are not necessary. For example, if the position pos less than min(NUMs) is selected, the result of pos selection is definitely not better than that of min(NUMs).

The core of this problem is the same mental model, namely:

• Determine the solution space. The solution space here is just r. It is not difficult to see that the lower bound of r is 0 and the upper bound is Max (nums) -min (nums).

You don’t have to be exact, you just don’t miss the correct solution, which we talked about earlier, but I’ll emphasize it again.

• Enumerate all possible x’s between the upper and lower bounds (from small to large, if possible), and check if radius x covers all of them by returning the first x that covers all of them.

Note that we are enumerating in an ordered sequence, so using dichotomy should come to mind. The core point to use for dichotomy is: if x does not work, then any radius less than x must not work.

The next problem is to determine whether a radius x can cover all the houses.

Determining whether it is overwritable is the so-called ability test. The function possible I defined is the ability test.

The NUMs are sorted first, which will be used later. Then simulate placing the lamp from the left. First place a lamp at nums[0] + r, which can cover [0, 2 * r]. Since NUMS is already sorted, this equal can cover all rooms in NUMS with coordinates less than or equal to 2 * r, using binary search. For all rooms to the right of numS we need to continue to place lights in the same way.

Ability testing core code:

def possible(diameter) :
    start = nums[0]
    end = start + diameter
    for i in range(LIGHTS):
        idx = bisect_right(nums, end)
        if idx >= N:
            return True
        start = nums[idx]
        end = start + diameter
    return False
Copy the code

Since we want to find the minimum that satisfies the condition, we can apply the left-most binary template directly.

code

Code support: Python3

Python3 Code:

class Solution:
    def solve(self, nums) :
        nums.sort()
        N = len(nums)
        if N <= 3:
            return 0
        LIGHTS = 3
        # The diameter is used here, so the final return is divided by 2
        def possible(diameter) :
            start = nums[0]
            end = start + diameter
            for i in range(LIGHTS):
                idx = bisect_right(nums, end)
                if idx >= N:
                    return True
                start = nums[idx]
                end = start + diameter
            return False

        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l + r) // 2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l / 2
Copy the code

Complexity analysis

Let n be the length of the array.

• Time complexity: Due to sorting, the time complexity is approximately O(nlogn)O(nlogn)O(nlogn)
• Space complexity: Depends on the space consumption of sorting

778. Swimming in a pool with rising water level (difficulty)

Title address

Leetcode-cn.com/problems/sw…

Topic describes

In an N x N grid grid, the value grid[I][j] of each grid represents the height of the platform at position (I,j). It's starting to rain now. When the time is t, the water level at any position in the pool caused by rainwater is T. You can swim from one platform to any nearby platform, but only if the water level covers both platforms at the same time. Assuming you can teleport an infinite distance, by default, it takes no time to swim around the grid. Of course, you have to stay in the grid when you swim. You start from the upper left platform of the grid (0,0). What is the minimum time it takes you to reach the lower right platform of the grid (n-1, n-1)? Example 1: Input: [[0,2],[1,3]] Output: 3 Explanation: When time is 0, your position on the grid is (0, 0). You can't swim in any direction because the four adjacent platforms are all higher than the water level when the current time is 0. Wait until the time reaches 3 before you can swim to the platform (1, 1). Since the water level is 3, no platform in the grid is higher than level 3, so you can swim to any position in the grid. 24,23,22,21,5,1,2,3,4 [[0], [], [12,13,14,15,16],,17,18,19,20 [11], [10,9,8,7,6]] output: 16: 0 12 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6 The final route is marked in bold. 2 <= N <= 50. Grid [I][j] is in the interval [0,... N* n-1].Copy the code

Front knowledge

• DFS
• binary

Train of thought

So let’s clarify our solution space. It is not difficult to conclude that the solution space is [0, Max (grid)], where Max (grid) represents the maximum value in the grid.

So the simple idea is to try it one at a time.

• Try a, no
• Let’s try a plus 1
• .

Testing x to see if it works is a test of ability.

In fact, if x doesn’t work, then anything less than x doesn’t work, and that’s the point. For this reason, we can also use the left-most binary template in the handout.

Pseudo code:

def test(x) :
    pass
while l <= r:
    mid = (l + r) // 2
    if test(mid, 0.0):
        r = mid - 1
    else:
        l = mid + 1
return l

Copy the code

This template will be used in many dichotomies. For example, if you have a typical counting dichotomy, you typically compute how many are less than or equal to x, and then update your solution space based on your answer.

With this in mind, all that remains is to complete the ability test part (the test function). In fact, this is an ordinary two-dimensional grid DFS, we start from (0,0) and search through a two-dimensional grid until we can’t continue or reach (n-1, n-1). If we can reach (n-1, n-1), we return true, otherwise we return False. For those unfamiliar with 2D grid DFS, check out the island topic I wrote earlier

code

class Solution:
    def swimInWater(self, grid: List[List[int]]) - >int:
        l, r = 0.max([max(vec) for vec in grid])
        seen = set(a)def test(mid, x, y) :
            if x > len(grid) - 1 or x < 0 or y > len(grid[0]) - 1 or y < 0:
                return False
            if grid[x][y] > mid:
                return False
            if (x, y) == (len(grid) - 1.len(grid[0]) - 1) :return True
            if (x, y) in seen:
                return False
            seen.add((x, y))
            ans = test(mid, x + 1, y) or test(mid, x - 1,
                                              y) or test(mid, x, y + 1) or test(mid, x, y - 1)
            return ans
        while l <= r:
            mid = (l + r) // 2
            if test(mid, 0.0):
                r = mid - 1
            else:
                l = mid + 1
            seen = set(a)return l

Copy the code

Complexity analysis

• Time complexity: O(NlogM)O(NlogM)O(NlogM) O(NlogM), where M is the maximum size of a grid and N is the total size of a grid.
• Space complexity: O(N)O(N)O(N), where N is the total size of the grid.

The count of binary

Counting binary and the above idea has been basically the same code. Looking directly at the code makes it clear:

def count_bs(nums, k) :
  def count_not_greater(mid) :
    pass
  l, r = 0.len(A) - 1
  while l <= r:
      mid = (l + r) // 2
      # Only here is different from the left half
      if count_not_greater(mid) > k: r = mid - 1
      else: l = mid + 1
  return l
Copy the code

As you can see, possible is changed to count_not_greater and the return value is just a number.

In fact, we can modify the above code slightly to make it more like:

def count_bs(nums, k) :
  def possible(mid, k) :
    # xxx
    return cnt > k
  l, r = 0.len(A) - 1
  while l <= r:
      mid = (l + r) // 2
      if possible(mid, k): r = mid - 1
      else: l = mid + 1
  return l
Copy the code

Is it basically the same?

As the above basic consistent, so here is a direct recommendation of a topic, we use my train of thought to practice, see my skills.

• The KTH smallest distance pair

Prefix and dichotomy

If the array is all positive, then the sum of the prefixes is a strictly increasing array. Similarly, there are monotonic stacks/queues. There are many types of questions, so I won’t give examples to save space. The whole point of coming up with prefixes and dichotomies is to keep people sensitive to ordered sequences.

Insertion sort dichotomy

In addition to the prefix and above, we can also maintain ordered sequences ourselves. Generally, there are two ways:

• Sort the sequence directly.

Code representation:

nums.sort()
bisect.bisect_left(nums, x) # left-most dichotomy
bisect.bisect_right(nums, x) # right half
Copy the code

• The traversal process maintains a new ordered sequence of values that have already been traversed.

For example, in an unordered array [3,2,10,5], we construct an ordered sequence [2,3,10] when iterating over items with index 2 (that is, items with value 10).

Note that I’m describing ordered sequences, not specific data structures like exponential groups, linked lists, etc. In fact, this ordered sequence is in many cases a balanced binary tree. And we’ll see that later on.

Code representation:

d = SortedList()
for a in A:
    d.add(a) Add a to D and keep d in order
Copy the code

D of the code above is the ordered sequence.

So much for the theory, let me give you an example.

327. Number of sums of intervals (difficulty)

Title address

Leetcode-cn.com/problems/co…

Topic describes

Given an integer array nums. The interval and S(I, j) represent the sum of the elements in position from I to j in NUMS, including I and j (I ≤ j). Start with the subscript I (0 <= I <= nums.length) and count the sum of the elements in the subarray. When the sum of the elements falls within the range [lower, upper] (including lower and upper), the subscript j of the current last element of the subarray is recorded, denoted as the valid range and S(I, j). Find the number of valid sums within the range [lower, upper], including lower and upper. Note: The most intuitive algorithm complexity is O(n2), please optimize your algorithm based on this. Example: Input: nums = [-2,5,-1], lower = -2, upper = 2, output: 3 Where -2 and 2 fall between the range [lower = -2, upper = 2], so the effective range and S(0,0), S(0,2) are recorded. When subscript I = 1, subarray [5], [5,-1], elements and 5, 4; There is no effective interval sum satisfying the question. When I = 2, subarray [-1], elements and -1; Record the valid interval and S(2,2). Therefore, there are 3 effective intervals and. 0 <= nums.length <= 10^4Copy the code

Train of thought

It’s easy to understand.

Sum (I,j) = pre[j] -pre [i-1], where pre[I] is the sum of the I items before the array 0 <= I < n.

But the numbers in the problem could be negative, so the sum of prefixes doesn’t have to be monotonic. Right? What is to be done? The answer is to manually maintain the order of prefix sums.

For example, the prefix sum for [-2,5,-1] is [-2,3,2], but we can manually maintain it as [-2,2,3], which is sorted. But this loses the index information, so this trick only works if you don’t have to worry about the index, you don’t have to ask for a specific subsequence, you just have to know that there is such a subsequence, we don’t care which one it is.

For example, if the current prefix sum is cur, the number of prefixes less than or equal to cur-lower indicates the number of intervals ending in the current sum greater than or equal to lower. Similarly, the number of prefixes with sums less than or equal to cur-upper indicates the number of intervals ending in the current sum greater than or equal to upper.

Based on this idea, we can quickly solve these two numbers using binary in lognlognlogn time. Using a balanced binary tree instead of an array reduces the insertion time complexity to O(logn)O(logn)O(logn). Python can be implemented using SortedList, while Java can use TreeMap instead.

code

from sortedcontainers import SortedList
class Solution:
    def countRangeSum(self, A: List[int], lower: int, upper: int) - >int:
        ans, pre, cur = 0[0].0
        for a in A:
            cur += a
            ans += pre.bisect_right(cur - lower) - pre.bisect_left(cur - upper)
            pre.add(cur)
        return ans

Copy the code

Complexity analysis

Let n be the length of the array.

• O(nlogn)O(nlogn)O(nlogn)
• Space complexity: O(nlogn)O(nlogn)O(nlogn)

493. Flip pair (difficulty)

Title address

Leetcode-cn.com/problems/re…

Topic describes

Given an array nums, we call (I, j) an important flipped pair if I < j and nums[I] > 2*nums[j]. You need to return the number of important flips in a given array. Example 1: Input: [1,3,2,3,1] Output: 2 Example 2: Input: [2,4,3,5,1] Output: 3 Note: The length of the given array cannot exceed 50000. All numbers in the input array are within the representation range of 32-bit integers.Copy the code

Front knowledge

• binary

The company

• no

Train of thought

We can iterate while maintaining an ordered sequence D, where D is the set of values already iterated. For each position 0 <= I < n, we count the number in D greater than 2 * A[I], which is the flipped pair they ask for. The key here is that the values in D are all values smaller than the current index.

We can of course go through d linearly and figure out what the number is. A better way to do this is to keep d in order while walking, so we can use dichotomy. As in the above problem, using balanced binary trees instead of arrays reduces the insertion time complexity to O(logn)O(logn)O(logn).

The key point

• Insertion sort dichotomy

code

• Language support: Python3

Python3 Code:

from sortedcontainers import SortedList
class Solution:
    def reversePairs(self, A: List[int]) - >int:
        d = SortedList()
        ans = 0
        for a in A:
            ans += len(d) - d.bisect_right(2*a)
            d.add(a)
        return ans

Copy the code

Complexity analysis

Let n be the length of the array.

• O(nlogn)O(nlogn)O(nlogn)
• Space complexity: O(n)O(n)O(n)

summary

The four applications talk about two ways to construct ordered sequences, prefix and insertion sort, and the insertion sort part can actually look at the longest ascending subsequence series I wrote earlier, where the greedy solution is to construct ordered sequences and then dichotomize them. In addition, monotonic stacks/queues are also ordered in theory, which can also be used to make dichotomies, but there are few related topics, so you just need to be sensitive to ordered sequences.

The ability to detect dichotomy is common, but it simply transforms the if part of the ordinary dichotomy into a function. As for counting dichotomy, it is actually a special case of ability detection dichotomy, but it is too common, so it is extracted separately.

In addition, sometimes ordered sequences give you a slightly different form. For example, binary search trees, you know you can do it in lognlognlogn time, and the search process is essentially binary. Does a binary search tree have an ordered sequence? Some! The middle order traversal of a binary search tree happens to be an ordered sequence. So if a number is smaller than the current value, it must be in the left subtree (to the left of the ordered sequence), and if a number is larger than the current value, it must be in the right subtree (to the right of the ordered sequence).

conclusion

This article mainly talked about two dichotomous types: most left and most right, the template has been given to you, you just need to adjust the solution space and judgment conditions according to the topic. But more about the four applications is just to get you to understand the core of dichotomy. On the surface, dichotomy is the search for an ordered sequence. No, it’s just that ordered sequences are easy to dichotomy. So tactically you have to be sensitive to ordered sequences, and strategically you have to make it clear that the essence of dichotomy is splitting in half, and the key is when you split which half.

The key to solving a binary problem is to detect a value that excludes half of the elements in the solution space. For example, as I said over and over again if x doesn’t work, then everything in our solution space that is less than or equal to x doesn’t work.

For simple problems, you’re usually given an ordered sequence where you can find the right place. Change a little bit at most, such as the array is locally ordered, one dimension becomes two dimensions, etc. And for this part you can look at the notes that I wrote on algorithm 91, binary search

Intermediate problems may require you to construct your own ordered sequences.

Difficult questions may be a combination of dichotomy and other topics, such as 778. Swimming in a pool with rising water level (difficult), which is a combination of dichotomy and search (I used DFS).

The above is all the content of this article, you have any views on this, welcome to leave a message to me, I have time will check the answer one by one. I’m Lucifer, Github Over 40K STAR You can also pay attention to my public account “Li Kou Jia Jia” take you to bite the hard bone of the algorithm.

In addition, the ebook of more than 1000 pages that I organized has been downloaded for free for a limited time. You can go to the background of my official account “Likejiajia” to reply and get the ebook.