数据结构与算法

Code Template for Matrix.

Code Template for Graph Algorithms.

Property

Define the binary array A with A.size() == N > 0. A contains only 0s and 1s.

For example, these are all binary arrays.
[0,0,0],[1,1]
[0,1,1,0],[1,0,0,1]
[0,1,1,1],[1,1,1,1,0,0,0]

Given the function BSearch:

1
2
3
4
5
6
7
8
9
10
11
12

int BSearch(int a, int b, const std::vector<int>& A) {
  assert(a <= b);
  while(a < b) {
    auto mid = a + (b - a) / 2;
    if(A[mid] == 1) {
      a = mid + 1;
    } else {
      b = mid;
    }
  }
  return a;
}

Running BSearch(0, A.size(), A) on all As in the example, we have:

• A = [0,0,0], return 0.
• A = [1,1], return 2.
• A = [0,1,1,0], return 3.
• A = [1,0,0,1], return 1.
• A = [0,1,1,1], return 4.
• A = [1,1,1,1,0,0,0], return 4.

Let us denote the index returned by BSearch as r. we could observe that:

PROPERTY: If r > 0 && r < N then A[r] == 0, A[r - 1] == 1. If r == 0, then A[r] == 0. If r == N, then A[r - 1] == 1.

We then try to prove PROPERTY.

Lemma1: $a + \displaystyle\lfloor{\frac{b - a}{2}}\rfloor = \displaystyle\lfloor{\frac{a + b}{2}}\rfloor$

Prove:

• If $a + b$ is even, then $b - a$ is even. $a + \displaystyle\lfloor{\frac{b - a}{2}}\rfloor = a + \frac{b - a}{2} = \frac{a + b}{2} = \lfloor{\frac{a + b}{2}}\rfloor$

• If $a + b$ is odd, then $b - a$ is odd. $a + \displaystyle\lfloor{\frac{b - a}{2}}\rfloor = a + \frac{b - a - 1}{2} = \frac{a + b - 1}{2} = \lfloor{\frac{a + b}{2}}\rfloor$

With Lemma1, we know that line 4 auto mid = a + (b - a) / 2; is equivalent to auto mid = (a + b) / 2 (when a + b does not overflow).

Lemma2: If $a < b$, then $a \leq \displaystyle{\lfloor{\frac{a + b}{2}}\rfloor} < b$

Prove:

With Lemma1 and Lemma2, we know that in line 4 auto mid = a + (b - a) / 2;, we have mid < b && mid >= a.

Lemma3: we must have a == b in line 11 return a;.

Prove:

In line 6 a = mid + 1;, let us denote the a on the left-hand side as newA, then we have newA = mid + 1. With Lemma2: mid < b, we could derive newA = mid + 1 <= b.

In line 8 b = mid;, let us denote the b on the left-hand side as newB, then we have newB = mid. With Lemma2 mid >= a, then a <= newB.

• newA <= b indicates that we will have a <= b in line 3 when we fall into the branch in lines 5 - 7.
• a <= newB indicates that we will have a <= b in line 3 when we fall into the branch in lines 7 - 9.

There is no other branch we could fall in. We must have a <= b in line 3. The loop will only exit when !(a < b) && (a <= b), which is a == b. Hence, we must have a == b in line 11 return a;.

With Lemma 1 - 3, we could prove PROPERTY.

Consider the following two situations of the program BSearch in line 4 auto mid = a + (b - a) / 2;.

Assume that a = k, b = k + 1, then in line 4 we have mid = k + (k + 1 - k) / 2, which is mid = k.

Situation1:

If A[mid] == A[k] == 1, we fall in the branch line 6 a = mid + 1;. Then newA = k + 1. In the next iteration, we will exit the loop with a == b == k + 1 in line 3 while(a < b). In line 11 we have a == b == k + 1.

If k + 1 < A.size(), then we have b != A.size(), which indicates that b must be assigned some value in line 8 b = mid. This assignment must have A[b] == 0 because we are in the branch of lines 7 - 9. With b == k + 1, we must have A[k + 1] == 0.

Hence, in line 11, we must have

• A[a] == A[b] == A[k + 1] == 0 if k + 1 < A.size().
• A[a - 1] == A[b - 1] == A[k] == 1.

Situation2

If A[mid] == A[k] == 0, we fall in the branch line 8 b = mid;. Then newB = k. In the next iteration, we will exit the loop with a == b == k. In line 11 we have a == b == k.

If k - 1 >= 0, then a == k != 0. Let us say a was assigned with some value x in line 6 a = mid + 1. This assigned value x must have a = x + 1 and A[x] == 1 if we fall into the branch of lines 5 - 7. Therefore, we have A[x] = A[a - 1] == A[k - 1] == 1.

Hence, in line 11, we must have

• A[a] == A[b] == A[k] == 0.
• A[a - 1] == A[b - 1] == A[k - 1] == 1, if k - 1 >= 0.

No other situation will transit to a == b in line 3 while(a < b). Therefore PROPERTY is proved.

Template Problems

Find the Partition Point

Given an array A and a unary predicate UnaryPred. A is said to be PARTITIONED, if there exists some PARTITION POINT im, im < A.size() && im >= 0, such that

• for all the elements a in the range A[0, im), UnaryPred(a) == 1.
• for all the elements a in the range A[im, A.size()) , UnaryPred(a) == 0.

FIND PARTITION POINT
Given an partitioned array A, find the PARTITION POINT im

This problem could be solved easily using BSearch in the previous section. We could apply Pred to each element of A to have a binary array BinaryA. Then we apply the BSearch to A, it must return im:

• If im == 0, with PROPERTY, we know the result must be 0 because there is no 1 in the array.
• If im == 1, with PROPERTY, we know the result must be A.size() because there is no 0 in the array.
• Otherwise, with PROPERTY, we know the result must be im because im is the only index such that A[im] == 0 && A[im - 1] == 1.

Notice that it is unnecessary to apply Pred to all elements of A. We could only apply Pred to those mids that we care.

Consider the following program. It slightly modifies BSearch from the previous section. In line 5, we change A[mid] == 1 into pred(mid), where pred is a unary predicate that returns either 0 or 1.

1
2
3
4
5
6
7
8
9
10
11
12

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

Then we could find im by PartitionPoint.

1
2
3

auto im = PartitionPoint(0, A.size(), [&A](int idx){
  return UnaryPred(A[idx]);
});

The PROPERTY could be revised as:

PROPERTY:
If r > 0 && r < N then P(r) == 0, P(r - 1) == 1. If r == 0, then P(r) == 0. If r == N, then P(r - 1) == 1.

Lower/Upper Bound, Binary Search

LOWER BOUND
Given a sorted array A and a number n, find the index of the first element in A such that it is greater than or equal to n.

Consider applying the following function to every element of the array:

1
2
3

int GreaterOrEqualThan(int a, int n) {
  return a < n;
} 

Then the sorted array will be partitioned by GreaterOrEqualThan. The partition point is the first element that has GreaterOrEqualThan != 1, which means that it is great or equal to n. We could use the function PartitionPoint in problem PARTITION POINT to find it out.

1
2
3

auto im = PartitionPoint(0, A.size(), [&A, n](int idx){
  return A[idx] < n;
});

UPPER BOUND
Given a sorted array A and a number n, find the index of the first element in A such that it is greater than n.

This problem is similar to LOWER BOUND. We just change our unary predicate into A[idx] <= n to make im the first element that has !(A[im] <= n) ==> A[im] > n.

1
2
3

auto im = PartitionPoint(0, A.size(), [&A, n](int idx){
  return A[idx] <= n;
});

BINARY SEARCH
Given a sorted array A and a number n, return true if there exists an element equals to a. Otherwise, return false.

Do LOWER BOUND with a on A. Test if the index i returned by LOWER BOUND has A[i] == a.

1
2
3
4
5

auto im = PartitionPoint(0, A.size(), [&A, n](int idx){
  return A[idx] < n;
});

return im < A.size() && A[im] == a;

Find the Kth Element

KTH ELEMENT
Given an array A with elements in range [a, b).
Define the function G, such that G(n) is the number of elements in A that are less than or equal to n.
Find the kth element of A, where k starts from 1.

There are greater than or equal to n elements in A that are less than or equal to the nth element.

For example, consider the array [1, 2, 3, 3, 4].

• The 1st element is 1. There are 1 element that is less than or equal to 1. That is 1 itself.
• The 2nd element is 2. There are 2 elements less than or equal to 1. They are 1 and 2 itself.
• The 3rd element is 3. There are 4 elements less than or equal to 3. They are 1, 2, 3 itself, and the other 3.
• The 4th element is 3. There are 4 elements less than or equal to 3. They are 1, 2, the other 3, and 3 itself.
• The 5th element is 4. There are 5 elements less than or equal to 4. They are 1, 2, 3, the other 3 and 4 itself.

Besides, the nth element is the first element that has greater than or equal to n element(s) that are less than or equal to it.

For example, consider the array [1, 2, 3, 3, 4].

• The 1st element is 1. 1 is the first element that has greater than or equal to 1 element that is less than or equal to it.
• The 2nd element is 2. 2 is the first element that has greater than or equal to 2 elements that are less than or equal to it.
• The 3rd element is 3. 3 is the first element that has greater than or equal to 3 elements that are less than or equal to it.
• The 4th element is 3. 3 is the first element that has greater than or equal to 4 elements that are less than or equal to it.
• The 5th element is 4. 4 is the first element that has greater than or equal to 5 elements that are less than or equal to it.

Notice that the function G (the number of elements in A that are less than or equal to n) is a non-decreasing function of n.

Define the unary predicate P(n) to be G(n) < k. The range [a, b) is partitioned by P(n) because of the monotonicity of G. The partition point im is the first element with !(G(im) < k), i.e., the first element that has greater than or equal to k element(s) that are less than or equal to it. Therefore, the partition point im is the kth element in A.

Find Peak

FIND PEAK IN MOUNTAIN ARRAY
A MOUNTAIN ARRAY is an array A with following constraints:

• A.size() >= 3
• There exists some peak at index i with 0 < i < A.size() - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
    Given a MOUNTAIN ARRAY, find the index of the PEAK.

All the elements in the range A[0, i + 1) have arr[j] - arr[j - 1] > 0(except for the first element).
All the elements in the range A[i + 1, A.size()) have arr[j] - arr[j - 1] < 0

Define the predicate P(j): j == 0 || (arr[j] - arr[j - 1] > 0). The index array I = [0, 1, 2, ..., A.size() - 1] is partitioned by P. The partition point im is the first element such that arr[j] - arr[j - 1] <= 0. Because there is no such j that has arr[j] - arr[j - 1] == 0, the partition point is i + 1. Thus we have i = im - 1.

1
2
3

return PartitionPoint(first, last, [&A](int idx){
  return idx == 0 || A[idx] - A[idx - 1] > 0;
});

FIND ANY PEAK
Given an integer array A, find the index to any of the peaks. A peak element is an element that is strictly greater than its neighbors. An element is always considered to be strictly greater than a neighbor that is outside the array.
Constraint:

• nums[i] != nums[i + 1]

Define the predicate P(j): j == 0 || (arr[j] - arr[j - 1] > 0).
We must have P(0) = 1.
If we have P(A.size() - 1) = 1 for the last element, then the last element is one of the peaks.
If we have P(A.size() - 1) = 0 for the last element, then there must be a peak in the range A[0, A.size() - 1).

• Assume that the results of applying P to all elements in the range A[0, A.size() - 1) are all 1, then A[A.size() - 2] must be a peak.
• Assume that the results of applying P to all elements in the range A[0, A.size() - 1) are all 0, then A[0] must be a peak.
• Assume that the results of applying P to all elements in the range A[0, A.size() - 1) contain both 0 and 1, then there must be a peak in the range A[0, A.size() - 1).

Therefore, even if the index range I = [0, 1, 2, ..., A.size() - 1] is not partitioned by P. Denote the result of running FIND PARTITION POINT as r. With PROPERTY, we know that r - 1 must be a peak.

PROPERTY
If r > 0 && r < N then P(r) == 0, P(r - 1) == 1. If r == 0, then P(r) == 0. If r == N, then P(r - 1) == 1.

• If r > 0 && r < N then A[r] == 0, A[r - 1] == 1: This indicates that P(r) == 0 and P(r - 1) == 1. We could derive A[r] - A[r - 1] <= 0 and A[r - 1] - A[r - 2] > 0. Because of the constraint nums[i] != nums[i + 1], we must have A[r] - A[r - 1] < 0 and A[r - 1] - A[r - 2] > 0. A[r - 1] is strictly greater than its neighbors.
• If r == 0, then A[r] == 0: We must have P(0) == 1, then r != 0
• If r == N, then P(r - 1) == 1: A[N - 1] is greater than its right neighbor because we have “an element is always considered to be strictly greater than a neighbor that is outside the array.” A[N - 1] is greater than its left neight because P(N - 1) == 1. Therefore, if r == N, then N - 1 is a peak element.

For rigorous proof from another point of view, see Find Peak Element(s).

Rotated Sorted Array

ROTATE
Given an array A. If we rotate A at some index i, it is the same as swapping the elements in A in such a way that the element A[i] becomes the first element of the new rotated array and i - 1 becomes the last element.
std::rotate

For example, if we rotate A = [0, 1, 2, 3, 4] at index i = 3, we have the rotated array as R = [3, 4, 0, 1, 2].

FIND ROTATION POINT
Given a sorted array A. Define r to be a rotated array of A at an unknown index i. There might be many such is. Find any one of them.

Consider the array A = [1, 2, 3, 4, 4, 4, 5].

• If we rotate it at index 1, A[1] = 2, we have R1 = [2, 3, 4, 4, 4, 5, 1]
• If we rotate it at index 4, A[4] = 4, we have R4 = [4, 4, 5, 1, 2, 3, 4].

A is sorted. Then, after rotation, it must have two sorted parts.

For example, the two sorted parts of R1 are P1 = [2, 3, 4, 4, 5] and P2 = [1].

Furthermore, the first element of the rotated array is less than or equal to all the elements in the first part. It is also greater than or equal to all the elements in the second part. For example, 2 is less than all elements in P1 = [2, 3, 4, 4, 5]. 2 is greater than or equal to all elements in P2 = [1].

Assume that, in the second part, there is no such element equal to the first element of the rotated array. Define the unary predicate P(x) as “x is greater than or equal to the first element of the rotated array.” Then, the rotated array is PARTITIONED by P(i). The PARTITION POINT is the index where the sorted array is rotated.

For example, consider the rotated sorted array P1 = [2, 3, 4, 4, 5, 1]. Apply P(x): x >= 2 on it, we have [1, 1, 1, 1, 1, 0], the rotation point is 1 at index 5.

However, if we rotate it at index 4, A[4] = 4, we have R4 = [4, 4, 5, 1, 2, 3, 4]. Apply P(x): x >= 4 on it, we have [1, 1, 1, 0, 0, 0, 1]. The array is not PARTITIONED by P(x). This indicates that if the first and the last element in the rotated array are the same, we have to strip them out. That is to say, if the first and the last element are the same, remove all the elements equal to the first element in the rotated array. After the removal, the stripped array must be PARTITIONED.

To summarize, given a rotated sorted array R, to find the rotation point,

• If the first and the last elements are the same:
  • Remove all elements that are equal to the first element. - Then perform the PARTITION POINT with predicate P(x) = x >= first element of the stripped array on the stripped array.
• If the first and the last elements are different, perform the PARTITION POINT with predicate P(x) = x >= first element of the rotated array.

Notice that if we run the above algorithm on a sorted array that is not rotated, it will return the end index of the array. For example, if we run the above algorithm on A = [1, 2, 3, 4, 5], it will return 5. This matches the definition of ROTATE as rotating the empty range [5, 5) should have no effect.

Level Top Elements

LEVEL TOP ELEMENTS
Given a positive integer array A. In one operation, you pick the smallest element in A, increase it by 1, then put it back. Return the array after performing the operation k times on it.

For example, given array A = [3, 1, 1], do the operation on it 3 times, we have [3, 2, 1] —> [3, 2, 2] —> [3, 3, 2].

This problem could be solved easily by a heap-based priority queue. First, build the heap on A. Then pop the priority queue, increase the popped element, and put it back. This repeats k times. The time complexity is O(N) for building the heap, O(kLog(N)) for doing the operation. The overall time complexity is O(N + kLog(N)).

However, when k is very large, i.e., k ~ 1e9, this solution is not acceptable.

To get a better solution, let us first consider the following problem:

LEVEL TOP ELEMENTS SUBPROBLEM1
Given a sorted positive integer array A. We want to LEVEL the top i elements. “LEVEL“ means to increase the elements in the subarray A[0, i) and make them the same as A[i]. How many do we need to increase?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

               ┌┐                   ┌┐
               ││                   ││
               ││                   ││
               ││                   ││
level    to 2  ││                   ││
────────────┬┬─┼┼──────────┬┬─┬┬─┬┐ ││
            ││ ││          ││ ││ ││ ││
            ││ ││          ││ ││ ││ ││
         ┌┐ ││ ││          ││ ││ ││ ││
         ││ ││ ││          ││ ││ ││ ││
      ┌┐ ││ ││ ││          ││ ││ ││ ││
      ││ ││ ││ ││          ││ ││ ││ ││
      ││ ││ ││ ││          ││ ││ ││ ││
      ││ ││ ││ ││          ││ ││ ││ ││
      ││ ││ ││ ││          ││ ││ ││ ││
      ││ ││ ││ ││          ││ ││ ││ ││
      └┘ └┘ └┘ └┘          └┘ └┘ └┘ └┘
      0  1  2  3           0  1  2  3

Compute the prefix sum pSum of A. The sum of the elements in the subarray A[0, i) could be derived from the prefix sum. After leveling up the top i elements, the sum of the subarray A[0, i) is i * A[i]. The difference (i * A[i]) - pSum[i] is how many we need to increase.

LEVEL TOP ELEMENTS SUBPROBLEM2
Given a sorted positive integer array A. We could increase at most k. Return the largest index i that we could level to.

Consider the cost we derived from the previous problem. Define C(i) = (i * A[i]) - pSum[i] is how many we need to increase if we want to level the top i elements. C(i) - C(i - 1) = (i * A[i]) - pSum[i] - ((i - 1) * A[i - 1]) + pSum[i - 1] = -(pSum[i] - pSum[i - 1]) + (i * A[i]) - ((i - 1) * A[i - 1]) = -A[i - 1] - ((i - 1) * (A[i - 1])) + (i * A[i]) = -(i * A[i - 1]) + (i * A[i]) = i * (A[i] - A[i - 1]). A is sorted. Thus C(i) is a non-decreasing function of i.

Define the predicate P(i): C(i) <= k on the index array I = [0, 1, ..., A.size() - 1]. Because C(i) is a non-decreasing function of i, I is partitioned by P(i). The partition point im is the first index such that C(im) > k, the first index that we cannot level to. Therefore, the largest index i we could level to is im - 1.

Now, consider the problem LEVEL TOP ELEMENTS again. With LEVEL TOP ELEMENTS SUBPROBLEM2, we could first derive the largest index i that we could level to with k operations. Then, with LEVEL TOP ELEMENTS SUBPROBLEM1, we could compute how many operations (C(i) = (i * A[i]) - pSum[i]) we need to level to the index i. After subtracting k by C(i), we have r = k - C(i), which is the remaining number of operations after leveling up to the index i. We distribute these r operations evenly on subarray A[0, i + 1) (the right boundary is i + 1 because after leveling to i, A[i] is equal to all elements in A[0, i)):

• First, we perform r / (i + 1) operations on each subarray element of A[0, i + 1).
• Then, we distribute the remaining r mod (i + 1) operations on the first r mod (i + 1) elements.
  After the above operations:
• There are (i + 1 - (r mod (i + 1)) elements with value A[i] + r / (i + 1).
• Thera are r mod (i + 1) elements with value A[i] + r / (i + 1) + 1.

The time complexity the method above is O(N):

• Compute the prefix sum array: O(N)
• Each call of C(i): O(1)
• Finding partition point needs log(N) calls of C(i), which is log(N).
• Distributing the remaining operations: O(1).

The time complexity does not depend on k. We could solve the problem when k ~ 1e9.

Selected Problems

Find the Kth Element

We have discussed this problem in KTH ELEMENT in the Template Problems section. The idea is to find a function G(x) that returns the number of elements that are less than or equal to x. Then define the predicate P(x): G(x) < k. The range of x is partitioned by P(x). We could apply FIND PARTITION POINT on the range. The partition point is the kth element.

Leetcode 878. Nth Magical Number

Leetcode 878. Nth Magical Number
Given three integers n, a, and b. Return the nth number that is divisble by either a or b.

Consider the following subproblems:

Nth Magical Number SUBPROBLEM1
Given two integers x and a. Return the number of integers that are both

• Less than or equal to x .
• Divisble by a

There are x / a integers that are both less than or equal to x and divisible by a.

Nth Magical Number SUBPROBLEM2
Given three integers x, a, and b. Return the number of integers that are:

• Less than or equal to x .
• Divisble by either a or b

There are A = x / a integers that are both less than or equal to x and divisible by a.
There are B = x / b integers that are both less than or equal to x and divisible by b.
There are C = x / lcm(a, b) integers that are less than or equal to x and divisible by both a and b. lcm(a, b) = a * b / gcd(a, b) is the least common multiplier of a and b.

By the inclusion–exclusion principle, the number of integers divisible by either a or b is A + B - C.

Now, we have the G function in the problem KTH ELEMENT, where G(x) = x / a + x / b - x / lcm(a, b). To get the nth element, we define the predicate as G(i) < n. Find the partition point on some large range (for example [1, 1e14)). The partition point is the n element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

static constexpr int64_t M = 1e9 + 7;

template<typename Pred>
int64_t PartitionPoint(int64_t first, int64_t last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int64_t NumberOfMagicalNumberLessEqualN(int64_t a, int64_t b, int64_t N) {
  return N / a + N / b - N / std::lcm(a, b);
}


class Solution {
public:
    int64_t nthMagicalNumber(int64_t n, int64_t a, int64_t b) {
      auto r = PartitionPoint(1, 1e14, [n, a, b](auto num){
        return NumberOfMagicalNumberLessEqualN(a, b, num) < n;
      });
      return r % M;
    }
};

Leetcode 1201. Ugly Number III

Leetcode 1201. Ugly Number III
Return the nth number that is divisble by either a, b or c.

This problem is similar to the previous problem Leetcode 878. Nth Magical Number. We have to derive how many numbers are divisible by either a, b or c. Again, using the inclusion–exclusion principle, we could derive the G function as

1
2
3
4
5

G(x) = n / a + n / b + n / c
       - n / lcm(a, b)
       - n / lcm(b, c)
       - n / lcm(a, c)
       + n / lcm(a, std::lcm(b, c));

Then define the predicate as P(x): G(x) < n and find the partition point on some large range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int64_t NumberOfIntegersDivisibleLessEqualN(int64_t n, int64_t a, int64_t b, int64_t c) {
  return n / a + n / b + n / c
       - n / std::lcm(a, b)
       - n / std::lcm(b, c)
       - n / std::lcm(a, c)
       + n / std::lcm(a, std::lcm(b, c));
}

class Solution {
public:
  int nthUglyNumber(int n, int a, int b, int c) {
    return PartitionPoint(1, 2 * 1e9 + 1, [n, a, b, c](int64_t num){
      return NumberOfIntegersDivisibleLessEqualN(num, a, b, c) < n;
    });
  }
};

Leetcode 719. Find K-th Smallest Pair Distance

Leetcode 719. Find K-th Smallest Pair Distance
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
Constraints:

• n == nums.length
• 2 <= n <= 1e4
• 0 <= nums[i] <= 1e6
• 1 <= k <= n * (n - 1) / 2

All we need to do is to find the G(x) function in the KTH ELEMENT problem. For this problem, G(x) is “the number of pairs with distances smaller than or equal to x.”

We first sort the array A. For the element with index i, search for the UPPER BOUND of x + A[i]. Denote the index of this UPPER BOUND as j. The distance between A[i] and the elements in the subarray A[i, j) is less than or equal to A[j] - A[i], which is x + A[i] - A[i] == x. Then there are j - i pairs whose distances are less than or equal to x.

Do this for each i in [0, A.size()) and accumulate the corresponding j - i. The sum is the number of pairs whose distances are less than or equal x.

After finding the G function, do the routine in the KTH ELEMENT problem to find the kth element.

Time Complexity:

• The search range ranges from the minimum to the maximum pair distance. Given that 0 <= nums[i] <= 1e6, this range is 1e6 at worst.
• Each call of G(x) iterates the whole array with a binary search on the array. This could be O(nLog(n)) at worst.
• Therefore, the time complexity is O(nLog(n)Log(R)), where R, the difference between the distance of the minimum and the maximum pair, is 1e6 at worst.
• Given n ~ 1e4, O(nLog(n)Log(R)) is at worst 1e4 * log(1e4) * log(1e6) ~ 2e6.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int NumberOfPairsWithDistLessEqualD(const std::vector<int>& nums, int dist) {
  auto res = 0;
  for(int i = 0; i < nums.size(); ++i) {
    const auto N = nums[i];
    auto first = nums.begin() + i + 1;
    auto last = nums.end();
    auto it = std::upper_bound(first, last, dist + N);
    res += it - first;
  }
  return res;
}

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
      std::sort(nums.begin(), nums.end()); 
      auto minDist = 0;
      auto maxDist = nums.back() - nums.front();
      return PartitionPoint(minDist, maxDist + 1, [&nums, k](int dist){
        return NumberOfPairsWithDistLessEqualD(nums, dist) < k;
      });
    }
};

Leetcode 668. Kth Smallest Number in Multiplication Table

668. Kth Smallest Number in Multiplication Table
Given a matrix mat of size m x n where m[i][j] = (i + 1) * (j + 1), return the kth smallest element in the matrix.

The G function for this problem should be G(x): “the number of elements that are less than or equal to x in the matrix.”

All the elements in row i are multiples of i + 1. In the problem Nth Magical Number SUBPROBLEM1, we have already derived the number of elements that are less than x and are multiple of i + 1, which is x / (i + 1).

However, there are at most n elements in row i. Therefore, in row i of the matrix, there are min(n, x / (i + 1)) elements that are less than or equal to x.

Take the mat of size 2 x 4 as an example. Let x = 5

1
2
3
4
5

┌─┬─┬─┬─┐
│1│2│3│4│
├─┼─┼─┼─┤
│2│4│6│8│
└─┴─┴─┴─┘

• In row 0, there are min(4, 5 / (0 + 1)) = 4 elements that are less than or equal to 5.
• In row 1, there are min(4, 5 / (1 + 1)) = 2 elements that are less than or equal to 5.

Then we could iterate each row of the matrix and sum the min(n, x / (i + 1)) together. The sum is G(x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int NumberOfElementsLessEqualN(int row, int col, int n) {
  auto res = 0;
  for(int i = 1; i <= row; ++i) {
    res += std::min(col, n / i);
  }
  return res;
}

class Solution {
public:
  int findKthNumber(int m, int n, int k) {
    return PartitionPoint(1, m * n + 1, [m, n, k](int num){
      return NumberOfElementsLessEqualN(m, n, num) < k;
    });
  }
};

Find Extremum

Leetcode 852. Peak Index in a Mountain Array

Leetcode 852. Peak Index in a Mountain Array
This problem is the same with FIND PEAK IN MOUNTAIN ARRAY.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int FindDividePoint(const std::vector<int>& arr) {
  const int first = 0;
  const int last = arr.size();
  return PartitionPoint(first, last, [&arr](int idx){
    return idx == 0 || arr[idx] - arr[idx - 1] > 0;
  });
}

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
      return FindDividePoint(arr) - 1;
    }
};

Leetcode 1095. Find in Mountain Array

Leetcode 1095. Find in Mountain Array
Given a mountain array A and a number a, find the index of the lower bound of a in A.

This problem is the same with FIND PEAK IN MOUNTAIN ARRAY. After we find the index of PEAK, the array is divided into two sorted parts. The first part is sorted in ascending order. The second part is sorted in descending order. Do LOWER BOUND separately on the two ranges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int FindDividePoint(MountainArray& ma) {
  const auto first = 0;
  const auto last = ma.length();
  return PartitionPoint(first, last, [&ma](int idx){
    return idx == 0 || ma.get(idx) - ma.get(idx - 1) > 0;
  });
}

class Solution {
public:
    int findInMountainArray(int target, MountainArray &ma) {
      auto first2 = FindDividePoint(ma);
      auto idx1 = PartitionPoint(0, first2, [&ma, target](int idx){
        return ma.get(idx) < target;
      });
      
      if(idx1 != first2 && ma.get(idx1) == target) {
        return idx1;
      }
      
      auto idx2 = PartitionPoint(first2, ma.length(), [&ma, target](int idx){
        return ma.get(idx) > target;
      });
      
      if(idx2 != ma.length() && ma.get(idx2) == target) {
        return idx2;
      }
      
      return -1;
    }
};

Leetcode 162. Find Peak Element

Leetcode 162. Find Peak Element
This problem is the same with FIND ANY PEAK.

For more rigorous proof, see Find Peak Element(s).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int FindDividePoint(const std::vector<int>& arr) {
  const int first = 0;
  const int last = arr.size();
  return PartitionPoint(first, last, [&arr](int idx){
    return idx == 0 || arr[idx] - arr[idx - 1] > 0;
  });
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
      return FindDividePoint(nums) - 1;
    }
};

Rotated Sorted Array

We have discussed how to find the rotation point of a rotated sorted array in FIND ROTATION POINT of the Template Problems section. We first check whether the first and the last element of the rotated sorted array are the same. If they are the same, we remove all these elements. After the removal, the first and the last element are not the same in the striped array. We then define the predicate P(x): x <= the first element. The striped rotated sorted array must be partitioned by P(x). The partitioned point is the rotation point, which divides the rotated sorted array into two sorted parts. Notice that if the input array is not rotated, the rotation point will be its end index (A.size()).

Leetcode 153. Find Minimum in Rotated Sorted Array

Leetcode 153. Find Minimum in Rotated Sorted Array
Given a rotated sorted array with unique elements, return the minimum element.

If the array is rotated, the rotation point divides the array into two sorted part. The first element of the second part should be the minimum. That is the rotation point.

If the array is not rotated, the first element is the minimum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

template<typename Pred, typename It>
It PartitionPoint(It first, It last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

template<typename It>
It RotatePoint(It first, It last) {  
  return PartitionPoint(first, last, [first](auto it) {
    return *first <= *it;
  });
}

class Solution {
public:
    int findMin(vector<int>& nums) {
      auto first = nums.begin();
      auto last = nums.end();
      auto pivot = RotatePoint(first, last);
      if(pivot == last) {
        return nums.front();
      } else {
        return *pivot;
      }
    }
};

Leetcode 154. Find Minimum in Rotated Sorted Array II

Leetcode 154. Find Minimum in Rotated Sorted Array II
Given a rotated sorted array, return the minimum element.

This problem is similar to the previous one but with duplicate elements.

If the first element equals the last element, we first strip them out of the array. (Line 40) Then we do FIND ROTATION POINT on the striped array. (Line 45)

The result is the smaller one between the first element and the rotation point(or the first element of the striped array). (Line 42, 47, 49)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

template<typename Pred, typename It>
It PartitionPoint(It first, It last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

template<typename It>
auto Strip(It first, It last) {
  if(*first == *(last - 1)) {
    const auto val = *first;
    while(first < last && *first == val) {
      ++first;
    }
    
    while(first < last && *(last - 1) == val) {
      --last;
    }
  }
  return std::make_pair(first, last);
}

template<typename It>
It RotatePoint(It first, It last) {  
  return PartitionPoint(first, last, [first](auto it) {
    return *first <= *it;
  });
}

class Solution {
public:
    int findMin(vector<int>& nums) {
      auto res = INT_MAX;
      auto [first, last] = Strip(nums.begin(), nums.end());
      if(last - first < nums.size()) {
        res = std::min(res, nums.front());
      }
      if(first < last) {
        auto pivot = RotatePoint(first, last);
        if(pivot == last) {
          res = std::min(res, *first);
        } else {
          res = std::min(res, *pivot);
        }
      }
      return res;
    }
};

Leetcode 33. Search in Rotated Sorted Array

Leetcode 33. Search in Rotated Sorted Array
Given a rotated sorted array with unique elements, return the index of the element equals to a. If there is no such element, return -1.

First, use FIND ROTATION POINT to get the rotation point. The rotated sorted array is divided into two sorted parts by the rotation point.
Then, do two LOWER BOUND on the two sorted parts separately.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

template<typename Pred, typename It>
It PartitionPoint(It first, It last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

template<typename It>
It RotatePoint(It first, It last) {  
  return PartitionPoint(first, last, [first](auto it) {
    return *first <= *it;
  });
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
      auto first = nums.begin();
      auto last = nums.end();
      auto pivot = RotatePoint(first, last);
      auto lIt = std::lower_bound(first, pivot, target);
      if(lIt != pivot && *lIt == target) {
        return lIt - first;
      }
      
      auto rIt = std::lower_bound(pivot, last, target);
      if(rIt != last && *rIt == target) {
        return rIt - first;
      }
      
      return -1;
    }
};

Leetcode 81. Search in Rotated Sorted Array II

Leetcode 81. Search in Rotated Sorted Array II
Given a rotated sorted array, return true if there exists an element equals to a. Otherwise, return false.

Do FIND ROTATION POINT on the rotated sorted array. As there might be duplicated elements. Before striping the array, we need to check if a equals the first element. If a does not equal the first element, we then BINARY SEARCH a on the two parts divided by the rotation point.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

template<typename Pred, typename It>
It PartitionPoint(It first, It last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

template<typename It>
auto Strip(It first, It last) {
  if(*first == *(last - 1)) {
    const auto val = *first;
    while(first < last && *first == val) {
      ++first;
    }
    
    while(first < last && *(last - 1) == val) {
      --last;
    }
  }
  return std::make_pair(first, last);
}

template<typename It>
It RotatePoint(It first, It last) {  
  return PartitionPoint(first, last, [first](auto it) {
    return *first <= *it;
  });
}

class Solution {
public:
    bool search(vector<int>& nums, int target) {
      if(target == nums.front()) {
        return true;
      }
      auto [first, last] = Strip(nums.begin(), nums.end());
      auto rIt = RotatePoint(first, last);
      return std::binary_search(first, rIt, target) 
          || std::binary_search(rIt, last, target);
    }
};

Level Top Elements

Some greedy solution requires you to increase the minimum element or to decrease the maximum element k times. If k is very large (k ~ 1e9), we could implement these greedy solutions by LEVEL TOP ELEMENTS.

• Sort the array.
• Compute the prefix sum of the array.
• Derive the function computing how many operations we need if we LEVEL to the i index.
• Binary search the largest i that we could level to.
• Distribute the remaining operations after leveling to i.

Leetcode 2233. Maximum Product After K Increments

Leetcode 2233. Maximum Product After K Increments
Given an array with non-negative integers. In one operation, you could increase any element by 1. You can do this operation k times. Return the maximum product of the elements in the array after k operations.

Let the elements in the array be $x_0, x_1, x_2, \cdots, x_{n-1}$, the product of the elements is $P = \displaystyle\prod_{i = 0}^{n}{x_{i}}$. Let $x_j$, $0 \leq j < n$ be the element that we will do the operation on. The partial derivative of $P$ w.r.t $x_j$ is $\displaystyle\frac{\partial P}{\partial x_j} = \displaystyle\prod_{i = 0, i \neq j}^{n}{x_{i}}$. To maximize the increase of the operation, we need to maximize $\displaystyle\frac{\partial P}{\partial x_j}$. That is, we need to pick the smallest element as $x_j$, so that $\displaystyle\frac{\partial P}{\partial x_j} = \displaystyle\prod_{i = 0, i \neq j}^{n}{x_{i}}$ is the largest.

Now we come up with a greedy solution for this problem. Do the operation on the smallest element of the array k times. Given k ~ 1e5, we could use a priority queue to implement it with O(kLog(n)) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static constexpr int M = 1e9 + 7;

int64_t Mul(int64_t l, int64_t r) {
  return (l % M * r % M) % M;
}

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
      auto pq = std::priority_queue<int, std::vector<int>, std::greater<int>>(nums.begin(), nums.end());
      for(int i = 0; i < k; ++i) {
        auto n = pq.top();
        pq.pop();
        pq.push(n + 1);
      }
      int64_t res = 1;
      while(!pq.empty()) {
        auto n = pq.top();
        pq.pop();
        res = Mul(res, n);
      }
      return res;
    }
};

However, the priority queue solution is not acceptable when k ~ 1e9. When `k ~ 1e9, we must solve this problem by LEVEL TOP ELEMENTS.

• In lines 20 - 23, the function LevelCost is the function C(i) in LEVEL TOP ELEMENTS.
• In line 28, we sort the input array.
• In lines 29 - 32, we compute the prefix sum of the array.
• In lines 33 - 35, we find the largest index idx that we could level to with k operations.
• In lines 36 - 40, we distribute the remaining operations evenly on the first i + 1 elements.
• In lines 41 - 50, we compute the product of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

static constexpr int M = 1e9 + 7;

int64_t Mul(int64_t lhs, int64_t rhs) {
  return (lhs % M * rhs % M) % M;
}

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int64_t LevelCost(int idx, const std::vector<int>& nums, const std::vector<int64_t>& pSum) {
  const int64_t n = nums[idx];
  return n * (idx + 1) - pSum[idx + 1];
}

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
      std::sort(nums.begin(), nums.end());
      auto pSum = std::vector<int64_t>{0};
      for(int i = 0; i < nums.size(); ++i) {
        pSum.push_back(pSum.back() + nums[i]);
      }
      const auto idx = PartitionPoint(0, nums.size(), [nums, pSum, k](int idx){
        return LevelCost(idx, nums, pSum) <= k;
      }) - 1;
      const int64_t levelCost = LevelCost(idx, nums, pSum);
      const int64_t levelNum1 = nums[idx] + (k - levelCost) / (idx + 1);
      const int64_t levelNum2 = levelNum1 + 1;
      const int64_t levelCount2 = (k - levelCost) % (idx + 1);
      const int64_t levelCount1 = (idx + 1) - levelCount2;
      int64_t res = 1;
      for(int i = idx + 1; i < nums.size(); ++i) {
        res = Mul(res, nums[i]);
      }
      for(int i = 0; i < levelCount2; ++i) {
        res = Mul(res, levelNum2);
      }
      for(int i = 0; i < levelCount1; ++i) {
        res = Mul(res, levelNum1);
      }
      return res % M;
    }
};

Leetcode 2333. Minimum Sum of Squared Difference

Leetcode 2333. Minimum Sum of Squared Difference
You are given a non-negative integer array A. In one operation, you could decrease any element by 1. You can do this operation k times. Return the minimum sum of squared elements in the array after k operations.

Let the elements in the array be $x_0, x_1, x_2, \cdots, x_{n-1}$, the sum of squared elements is $S = \displaystyle\sum_{i = 0}^{n}{x_{i}^2}$. Let $x_j$, $0 \leq j < n$ be the element that we will do the operation on. The partial derivative of $S$ w.r.t $x_j$ is $\displaystyle\frac{\partial P}{\partial x_j} = 2x_j$. To maximize the decrease of the operation, we need to maximize $\displaystyle\frac{\partial P}{\partial x_j}$. That is, we need to pick the largest element as $x_j$, so that $\displaystyle\frac{\partial P}{\partial x_j} = 2x_j$ is the largest.

This is a reversed LEVEL TOP ELEMENT. In this problem, we need to find the smallest index we could level to by decreasing larger elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

         ┌┐
         ││
         ││
         ││
         ││
      ┌┐ ││
      ││ ││
      ││ ││   level to 1
   ┌┬─┼┼─┼┼─────────┬┬─┬┬─┬┐
   ││ ││ ││         ││ ││ ││
┌┐ ││ ││ ││      ┌┐ ││ ││ ││
││ ││ ││ ││      ││ ││ ││ ││
││ ││ ││ ││      ││ ││ ││ ││
││ ││ ││ ││      ││ ││ ││ ││
││ ││ ││ ││      ││ ││ ││ ││
││ ││ ││ ││      ││ ││ ││ ││
└┘ └┘ └┘ └┘      └┘ └┘ └┘ └┘
0  1  2  3       0  1  2  3

Similar to LEVEL TOP ELEMENT, we need to define the C(i) function. Let pSum be the prefix sum of the array A. Then C(i) = (pSum[A.size()] - pSum[i]) - (nums.size() - i) * A[i].

Then we define the predicate P(i): C(i) > k and perform FIND PARTITION POINT on the index range [0, A.size()). The partition point is the first element such that C(i) <= k. Therefore, it is the smallest index that we could level to.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

auto LevelCost(int idx, 
               const std::vector<int64_t>& nums, 
               const std::vector<int64_t>& pSum) {
  return (pSum[nums.size()] - pSum[idx]) - (nums.size() - idx) * nums[idx];
}

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
      auto nums = std::vector<int64_t>(nums1.size(), 0);
      for(int i = 0; i < nums.size(); ++i) {
        nums[i] = std::abs(nums1[i] - nums2[i]);
      }
      
      std::sort(nums.begin(), nums.end());
      auto pSum = std::vector<int64_t>(nums.size() + 1, 0);
      std::partial_sum(nums.begin(), nums.end(), pSum.begin() + 1);
      const auto k = k1 + k2;
      if(pSum.back() <= k) {
        return 0;
      }
      auto idx = PartitionPoint(0, nums.size(), [&pSum, &nums, k](int idx){
        return LevelCost(idx, nums, pSum) > k;
      });
      const auto levelNum = nums[idx];
      const auto levelCount = nums.size() - idx;
      const auto levelCost = LevelCost(idx, nums, pSum);
      const auto remainingKAfterLevel = k - levelCost;
      const auto levelNum1 = levelNum - remainingKAfterLevel / levelCount;
      const auto levelNum2 = levelNum1 - 1;
      const auto levelNum2Count = remainingKAfterLevel % levelCount;
      const auto levelNum1Count = levelCount - levelNum2Count;
      
      auto res = 0ll;
      for(int i = 0; i < idx; ++i) {
        res += nums[i] * nums[i];
      }
      
      res += levelNum1 * levelNum1 * levelNum1Count;
      res += levelNum2 * levelNum2 * levelNum2Count;
      return res;
    }
};

Leetcode 1648. Sell Diminishing-Valued Colored Balls

1648. Sell Diminishing-Valued Colored Balls
Given an array A where A[i] represent the price of the ball with index i. There are infinite number of balls. However, every time when you sell a ball with index i, its price will decrease by 1. The minimum price of a ball is 0. You can sell k balls. Return the maximum value that you could attain after selling k balls.

A greedy strategy is always selling the ball of the largest price. This greedy strategy is similar to the previous problem Leetcode 2333. Minimum Sum of Squared Difference

Find the smallest index i that you could level to. Let us say some ball with price A[j] = a becomes A[j] = b after leveling to index i. Then the total value you could gain from selling this ball is then the arithmetic sequence sum: ((a + b + 1) * (a - b))/ 2. The computation of the total value attained should consider how the remaining operations are distributed on the leveled elements. (Lines 38 - 47)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

static constexpr int M = 1e9 + 7;

int64_t Plus(int64_t l, int64_t r) {
  return (l % M + r % M) % M;
}

template<typename Pred>
int64_t PartitionPoint(int64_t first, int64_t last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

auto LevelCost(int64_t idx, 
               const std::vector<int>& is, 
               const std::vector<int64_t> pSum) {
  return (pSum[is.size()] - pSum[idx]) - (is.size() - idx) * is[idx];
}

class Solution {
public:
    int maxProfit(vector<int>& is, int k) {
      std::sort(is.begin(), is.end());
      auto pSum = std::vector<int64_t>{0};
      for(auto i : is) {
        pSum.push_back(pSum.back() + i);
      }
      
      const int64_t idx = PartitionPoint(0, is.size(), [&is, &pSum, k](int idx){
        return LevelCost(idx, is, pSum) > k;
      });
      const int64_t levelCost = LevelCost(idx, is, pSum);
      const int64_t levelNum1 = is[idx] - (k - levelCost) / (is.size() - idx);
      const int64_t levelCount2 = (k - levelCost) % (is.size() - idx);
      const int64_t levelNum1Value = levelNum1 * levelCount2;
      int64_t res = levelNum1Value;
      for(int i = idx; i < is.size(); ++i) {
        const auto sellCount = is[i] - levelNum1;
        const auto value = ((levelNum1 + 1 + is[i]) * sellCount) / 2;
        res = Plus(res, value);
      }
      return res;
    }
};

Other Problems

Leetcode 69. Sqrt(x)

Leetcode 69. Sqrt(x)
Find floor(sqrt(x))

If x <= 1, then floor(sqrt(x)) == x.
If x > 1, the range [1, x) is partitioned by the predicate P(n): n * n <= x. The partition point im is the first n such that n * n > x, then floor(sqrt(x)) == im.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

template<typename Pred>
int64_t PartitionPoint(int64_t first, int64_t last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

class Solution {
public:
    int mySqrt(int x) {
      if(x <= 1) {
        return x;
      }
      return PartitionPoint(1, x, [x](int64_t num){
        return num * num <= x;
      }) - 1;
    }
};

Leetcode 475. Heaters

475. Heaters
Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Let the minimum radius of heaters to cover all houses be rm. It is obvious that all radius r > rm could cover all houses. All radius r < rm cannot cover all houses. Let the predicate P(r) be P(r): radius r could cover all houses. The range of the radius must be partitioned by P(r). Given the constraint 1 <= houses[i], heaters[i] <= 1e9, the range of the radius r is [0, 1e9 + 1).

To check if radius r could cover all houses, we simply put all positions of the houses into a set s. Then for each position p of the heater, we remove all houses in the range [p - r, p + r]. After iterating all positions of the heaters, if s is empty, then the radius r could cover all houses.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

bool CanCoverAllHouses(const std::vector<int>& houses, 
                       const std::vector<int>& heaters, 
                       int radius) {
  auto hs = std::set<int>(houses.begin(), houses.end());
  for(auto heater : heaters) {
    const auto first = heater - radius;
    const auto last = heater + radius;
    const auto firstIt = hs.lower_bound(first);
    const auto lastIt = hs.upper_bound(last);
    hs.erase(firstIt, lastIt);
  }
  return hs.empty();
}

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
      return PartitionPoint(0, 1e9 + 1, [&houses, &heaters](int radius){
        return !CanCoverAllHouses(houses, heaters, radius);
      });
    }
};

Leetcode 875. Koko Eating Bananas

Leetcode 875. Koko Eating Bananas
See the description of the problem in the link above.

If k == max(piles), Koko could eat all the bananas in piles.size() hours which is the minimum time that Koko could have.
If k > max(piles), Koko still eats all the bananas in piles.size() hours.
If k == 1, Koko eats all the bananas in sum(piles) hours.
As k increases, the time that Koko needs is non-increasing.

Define T(k): the time that Koko eats all bananas with speed k.
Let the predicate P(k) be P(k): T(k) > h. The range of speed [1, max(piles) + 1) is partitioned by P(k). The partition point is the smallest k such that T(k) <= h.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

template<typename Pred>
int PartitionPoint(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

int64_t DivCell(int64_t lhs, int64_t rhs) {
  if(lhs % rhs == 0) {
    return lhs / rhs;
  } else {
    return lhs / rhs + 1;
  }
}

int TotalEatingTime(const vector<int>& piles, int k) {
  auto res = 0;
  for(int i = 0; i < piles.size(); ++i) {
    res += DivCell(piles[i], k);
  }
  return res;
}

int MaxEatingTime(const vector<int>& piles) {
  return *std::max_element(piles.begin(), piles.end());
}

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
      return PartitionPoint(1, MaxEatingTime(piles) + 1, [&piles, h](int k){
        return TotalEatingTime(piles, k) > h;
      });
    }
};

Sliding Window, a popular method in programming problems, surprisingly, shares the same idea with Binary Search. In this post, we will show that Sliding Window is a 2D extension of Binary Search. We will also find that solving Sliding Window problems is nothing more than searching the 01 boundaries in 2D space.

This post is the second post of the【01Boundary】series.

• We first model the two situtations of Sliding Window, Max Window and Min Window, with the state $(i, j)$ and the binary predicate $\text{Pred}(i, j)$.
• Then, we talk about four popular problems (minimum length window, maximum length window, min counting, and max counting) under the model.
• After that, we derive the duality of Max Window and Min Window. Then we prove that we could transform Max Window to Min Window by negating the predicate $\text{Pred}(i, j)$.
• At the end of the introduction, we provide a code template for Min Window.
• In the Selected Problem section, we mainly focus on two types of problems:
  • Max/Min Window Problems
    • Leetcode 76 Minimum Window Substring
    • Leetcode 632 Smallest Range Covering Elements from K Lists
    • … and other 6 problems.
  • Subarray Counting Problems
    • Leetcode 1248 Count Number of Nice Subarrays
    • Leetcode 1918 Kth Smallest Subarray Sum
    • … and other 3 problems.

Keywords for sliding window problems:
longest/shortest subarray/substring, maximum/minimum length subarray/substring, number of such subarray.

Introduce the “small but mighty” algorithm — monotonic stack and its five properties.

• Next Smaller Element
• Previous Not Greater Element
• Minimum in Subarray
• Monotonic Increasing Stack
• Offline RMQ

Discussed the following problems with monotonic stack:

• Find next greater or smaller elements.
• Find subarrays for an element being minimum or maximum.
• Stack-sortable Permutation, 231 Pattern.
• Lexicorgraphically smallest subsequence after removing some elements.

Implement the binary tree traversal with the following functionalities

• Could traverse the tree in preorder, inorder, and postorder.
• Could access all the nodes on the path from the root to the current one.
• Could be suspended and resumed.
• Traverse the tree in O(N) time complexity

Tackle down most of linked list problems easily with basic concepts from functional programming.

LC162 Find one Peak Element in 1D Array

[Codewars] Find All Peak Elements in 1D Array

LC1901 Find one Peak Element in 2D Matrix