Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Question

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Question

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Question

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Question

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Question

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Question

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

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).