# Posts tagged as “hard”

Problem:

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation:
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.


Note:

• The number of calls to MyCalendarThree.book per test case will be at most 400.
• In calls to MyCalendarThree.book(start, end)start and end are integers in the range [0, 10^9].

Idea:

Similar to LeetCode 731 My Calendar II Use an ordered / tree map to track the number of event at current time.

For a new book event, increase the number of events at start, decrease the number of events at end.

Scan the timeline to find the maximum number of events.

# Solution 1: Count Boundaries

Time complexity: O(n^2)

Space complexity: O(n)

# Solution 3: Segment Tree

## Python3

Related Problems:

Problem:

In a N x N grid representing a field of cherries, each cell is one of three possible integers.

• 0 means the cell is empty, so you can pass through;
• 1 means the cell contains a cherry, that you can pick up and pass through;
• -1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible by following the rules below:

• Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);
• After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;
• When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);
• If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.

Example 1:

Note:

• grid is an N by N 2D array, with 1 <= N <= 50.
• Each grid[i][j] is an integer in the set {-1, 0, 1}.
• It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.

Idea:

DP

Key observation: (0,0) to (n-1, n-1) to (0, 0) is the same as (n-1,n-1) to (0,0) twice

1. Two people starting from (n-1, n-1) and go to (0, 0).
2. They move one step (left or up) at a time simultaneously. And pick up the cherry within the grid (if there is one).
3. if they ended up at the same grid with a cherry. Only one of them can pick up it.

Solution: DP / Recursion with memoization.

x1, y1, x2 to represent a state y2 can be computed: y2 = x1 + y1 – x2

dp(x1, y1, x2) computes the max cherries if start from {(x1, y1), (x2, y2)} to (0, 0), which is a recursive function.

Since two people move independently, there are 4 subproblems: (left, left), (left, up), (up, left), (left, up). Finally, we have:

dp(x1, y1, x2)= g[y1][x1] + g[y2][x2] + max{dp(x1-1,y1,x2-1), dp(x1,y1-1,x2-1), dp(x1-1,y1,x2), dp(x1,y1-1,x2)}

Time complexity: O(n^3)

Space complexity: O(n^3)

# Solution: DP

Time complexity: O(n^3)

Space complexity: O(n^3)

## Java

Related Problems:

Problem:

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

# Solution 2: Union Find

## Python3

Related Problems:

Problem:

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input:
S = 'bccb'
Output: 6
Explanation:
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.


Example 2:

Input:
Output: 104860361
Explanation:
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.


Note:

• The length of S will be in the range [1, 1000].
• Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.

Idea:

DP

# Solution 1: Recursion with memoization

Time complexity: O(n^2)
Space complexity: O(n^2)

# Solution 2: DP

## Pyhton

Related Problems:

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

# Solution:

Time complexity: O(k * (n1+n2)^2)

Space complexity: O(n1+n2)

## Java

Mission News Theme by Compete Themes.