Question

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Question

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Question

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Question

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Question

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Solution

To find an efficient solution for this type of problem, we need to use DP.

However, let us consider an extreme case fisrt. We are allow to make at most k transactions. If k is large enough to enable us to grab every profit, we do not have to do DP but just traverse the array once. The threshold of this k is n/2. Because a stock can rise at most n/2 times (two rises on two adjacent days can be merged into one). This is the idea of quickSolve().

For DP, the essence of DP is to solve small sub-problems first, and derive the results from these small sub-problem to larger problems. This max profit problem has two dimensions: 1. the number of days; 2. the max number of transactions allowed. So we creaste a 2D DP cache. And because deriving results from fewer days to more days is easier than changing max number of transactions, we make k+1 (more convenient than k) the first dimension and n the second dimension. Always use a variable that is easier to derive as the second dimension in 2D DP.

dp[i][j] represents the max profit of prices[:j] (inclusive) with at most i transactions. Thus, there are only two options for dp[i][j]: sell the stock on jth day or not. If sell, we need to iterate all possible cases to find the max profit. If not, dp[i][j] should be equal to dp[i][j-1].

So, we can get the following formulas for these two situations:

1. dp[i][j] = dp[i][j-1].
2. t is the date the last transaction was brought. dp[i][j] = for t: 0->j-1, max(dp[i-1][t-1]+prices[j]-prices[t]) .

This solution still has a O((n^2)*k) time complexity. The bottleneck is the second formula. However, we can further optimize it. It is equivalent to for t: 0->j-1, max(dp[i-1][t-1]-prices[t])+prices[j]. Thus, we can find the max of the second formula while iterating 0 to j-1 once.

Finally, the time complexity is optimized to O(nk).

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

// return the max profit without limiting the number of transactions
private int quickSolve(int[] prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        // short-term trading
        maxProfit += Math.max(0, prices[i] - prices[i - 1]);
    }
    return maxProfit;
}

// Time Complexity O(nk)
public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    // if k allows us to get every profit
    if (k >= n / 2) {
        return quickSolve(prices);
    }
    // dp[i][j] is the max profit of prices[:j] (inclusive) with at most i transactions
    int[][] dp = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        // dp[i-1][t-1]-prices[t]
        int maxTemp = -prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], maxTemp + prices[j]);
            maxTemp = Math.max(maxTemp, dp[i - 1][j - 1] - prices[j]);
        }
    }
    return dp[k][n - 1];
}

Question

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Question

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Question

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

You must find a solution with a memory complexity better than O(n^2).

Question

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Modular arithmetic

$a\equiv b\space(\text{mod}\space n)$ means a mod n = b mod n. The parentheses mean that $(\text{mod}\space n)$ applies to the entire equation, not just to the right-hand side.

Reflexivity, Symmetry and Transitivity:

• $a\equiv a\space(\text{mod}\space n)$
• $a\equiv b\space(\text{mod}\space n) \Leftrightarrow b\equiv a\space(\text{mod}\space n)$
• If $a\equiv b\space(\text{mod}\space n)$ and $b\equiv c\space(\text{mod}\space n)$, then $a\equiv c\space(\text{mod}\space n)$

If $a_1\equiv b_1\space(\text{mod}\space n)$ and $a_2\equiv b_2\space(\text{mod}\space n)$, or if $a\equiv b\space(\text{mod}\space n)$, then:

• $a+k\equiv b+k\space(\text{mod}\space n)$, for any integer $k$
• $ka\equiv kb\space(\text{mod}\space n)$, for any integer $k$
• $a_1+a_2\equiv b_1+b_2\space(\text{mod}\space n)$
• $a_1-a_2\equiv b_1-b_2\space(\text{mod}\space n)$
• $a_1a_2\equiv b_1b_2\space(\text{mod}\space n)$
• $a^k\equiv b^k\space(\text{mod}\space n)$, for any non-negative integer $k$
• $p(a)\equiv p(b)\space(\text{mod}\space n)$, for any polynomial $p(x)$ with integer coefficients

Compatibility with translation, scaling, addition, subtraction, multiplication, exponentiation and polynomial evaluation.

Read exponential expressions

2^16: two to the power of sixteen. 3^4: three to the power of four. x^2: x squared. x^3: x cubed.