bowang0911/leetcode huggingface dataset:
Design Skiplist

Design a **Skiplist** without using any built-in libraries.

A **skiplist** is a data structure that takes `O(log(n))` time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.

For example, we have a Skiplist containing `[30,40,50,60,70,90]` and we want to add `80` and `45` into it. The Skiplist works this way:

  
Artyom Kalinin \[CC BY-SA 3.0\], via [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Skip_list_add_element-en.gif "Artyom Kalinin [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons")

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than `O(n)`. It can be proven that the average time complexity for each operation is `O(log(n))` and space complexity is `O(n)`.

See more about Skiplist: [https://en.wikipedia.org/wiki/Skip\_list](https://en.wikipedia.org/wiki/Skip_list)

Implement the `Skiplist` class:

*   `Skiplist()` Initializes the object of the skiplist.
*   `bool search(int target)` Returns `true` if the integer `target` exists in the Skiplist or `false` otherwise.
*   `void add(int num)` Inserts the value `num` into the SkipList.
*   `bool erase(int num)` Removes the value `num` from the Skiplist and returns `true`. If `num` does not exist in the Skiplist, do nothing and return `false`. If there exist multiple `num` values, removing any one of them is fine.

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

**Example 1:**

**Input**
\[ "Skiplist ",  "add ",  "add ",  "add ",  "search ",  "add ",  "search ",  "erase ",  "erase ",  "search "\]
\[\[\], \[1\], \[2\], \[3\], \[0\], \[4\], \[1\], \[0\], \[1\], \[1\]\]
**Output**
\[null, null, null, null, false, null, true, false, true, false\]

**Explanation**
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // return False
skiplist.add(4);
skiplist.search(1); // return True
skiplist.erase(0);  // return False, 0 is not in skiplist.
skiplist.erase(1);  // return True
skiplist.search(1); // return False, 1 has already been erased.

**Constraints:**

*   `0 <= num, target <= 2 * 104`
*   At most `5 * 104` calls will be made to `search`, `add`, and `erase`.
Unique Number of Occurrences

Given an array of integers `arr`, return `true` _if the number of occurrences of each value in the array is **unique** or_ `false` _otherwise_.

**Example 1:**

**Input:** arr = \[1,2,2,1,1,3\]
**Output:** true
**Explanation:** The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

**Example 2:**

**Input:** arr = \[1,2\]
**Output:** false

**Example 3:**

**Input:** arr = \[-3,0,1,-3,1,1,1,-3,10,0\]
**Output:** true

**Constraints:**

*   `1 <= arr.length <= 1000`
*   `-1000 <= arr[i] <= 1000`
Get Equal Substrings Within Budget

You are given two strings `s` and `t` of the same length and an integer `maxCost`.

You want to change `s` to `t`. Changing the `ith` character of `s` to `ith` character of `t` costs `|s[i] - t[i]|` (i.e., the absolute difference between the ASCII values of the characters).

Return _the maximum length of a substring of_ `s` _that can be changed to be the same as the corresponding substring of_ `t` _with a cost less than or equal to_ `maxCost`. If there is no substring from `s` that can be changed to its corresponding substring from `t`, return `0`.

**Example 1:**

**Input:** s =  "abcd ", t =  "bcdf ", maxCost = 3
**Output:** 3
**Explanation:**  "abc " of s can change to  "bcd ".
That costs 3, so the maximum length is 3.

**Example 2:**

**Input:** s =  "abcd ", t =  "cdef ", maxCost = 3
**Output:** 1
**Explanation:** Each character in s costs 2 to change to character in t,  so the maximum length is 1.

**Example 3:**

**Input:** s =  "abcd ", t =  "acde ", maxCost = 0
**Output:** 1
**Explanation:** You cannot make any change, so the maximum length is 1.

**Constraints:**

*   `1 <= s.length <= 105`
*   `t.length == s.length`
*   `0 <= maxCost <= 106`
*   `s` and `t` consist of only lowercase English letters.
Remove All Adjacent Duplicates in String II

You are given a string `s` and an integer `k`, a `k` **duplicate removal** consists of choosing `k` adjacent and equal letters from `s` and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make `k` **duplicate removals** on `s` until we no longer can.

Return _the final string after all such duplicate removals have been made_. It is guaranteed that the answer is **unique**.

**Example 1:**

**Input:** s =  "abcd ", k = 2
**Output:**  "abcd "
**Explanation:** There's nothing to delete.

**Example 2:**

**Input:** s =  "deeedbbcccbdaa ", k = 3
**Output:**  "aa "
**Explanation:** 
First delete  "eee " and  "ccc ", get  "ddbbbdaa "
Then delete  "bbb ", get  "dddaa "
Finally delete  "ddd ", get  "aa "

**Example 3:**

**Input:** s =  "pbbcggttciiippooaais ", k = 2
**Output:**  "ps "

**Constraints:**

*   `1 <= s.length <= 105`
*   `2 <= k <= 104`
*   `s` only contains lowercase English letters.
Minimum Moves to Reach Target with Rotations

In an `n*n` grid, there is a snake that spans 2 cells and starts moving from the top left corner at `(0, 0)` and `(0, 1)`. The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at `(n-1, n-2)` and `(n-1, n-1)`.

In one move the snake can:

*   Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
*   Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
*   Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from `(r, c)` and `(r, c+1)` to `(r, c)` and `(r+1, c)`.  
    
*   Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from `(r, c)` and `(r+1, c)` to `(r, c)` and `(r, c+1)`.  
    

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return `-1`.

**Example 1:**

**Input:** grid = \[\[0,0,0,0,0,1\],
               \[1,1,0,0,1,0\],
               \[0,0,0,0,1,1\],
               \[0,0,1,0,1,0\],
               \[0,1,1,0,0,0\],
               \[0,1,1,0,0,0\]\]
**Output:** 11
**Explanation:**
One possible solution is \[right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down\].

**Example 2:**

**Input:** grid = \[\[0,0,1,1,1,1\],
               \[0,0,0,0,1,1\],
               \[1,1,0,0,0,1\],
               \[1,1,1,0,0,1\],
               \[1,1,1,0,0,1\],
               \[1,1,1,0,0,0\]\]
**Output:** 9

**Constraints:**

*   `2 <= n <= 100`
*   `0 <= grid[i][j] <= 1`
*   It is guaranteed that the snake starts at empty cells.
Intersection of Three Sorted Arrays

Given three integer arrays `arr1`, `arr2` and `arr3` **sorted** in **strictly increasing** order, return a sorted array of **only** the integers that appeared in **all** three arrays.

**Example 1:**

**Input:** arr1 = \[1,2,3,4,5\], arr2 = \[1,2,5,7,9\], arr3 = \[1,3,4,5,8\]
**Output:** \[1,5\]
**Explanation:** Only 1 and 5 appeared in the three arrays.

**Example 2:**

**Input:** arr1 = \[197,418,523,876,1356\], arr2 = \[501,880,1593,1710,1870\], arr3 = \[521,682,1337,1395,1764\]
**Output:** \[\]

**Constraints:**

*   `1 <= arr1.length, arr2.length, arr3.length <= 1000`
*   `1 <= arr1[i], arr2[i], arr3[i] <= 2000`
Two Sum BSTs

Given the roots of two binary search trees, `root1` and `root2`, return `true` if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer `target`.

**Example 1:**

**Input:** root1 = \[2,1,4\], root2 = \[1,0,3\], target = 5
**Output:** true
**Explanation:** 2 and 3 sum up to 5.

**Example 2:**

**Input:** root1 = \[0,-10,10\], root2 = \[5,1,7,0,2\], target = 18
**Output:** false

**Constraints:**

*   The number of nodes in each tree is in the range `[1, 5000]`.
*   `-109 <= Node.val, target <= 109`
Stepping Numbers

A **stepping number** is an integer such that all of its adjacent digits have an absolute difference of exactly `1`.

*   For example, `321` is a **stepping number** while `421` is not.

Given two integers `low` and `high`, return _a sorted list of all the **stepping numbers** in the inclusive range_ `[low, high]`.

**Example 1:**

**Input:** low = 0, high = 21
**Output:** \[0,1,2,3,4,5,6,7,8,9,10,12,21\]

**Example 2:**

**Input:** low = 10, high = 15
**Output:** \[10,12\]

**Constraints:**

*   `0 <= low <= high <= 2 * 109`
Valid Palindrome III

Given a string `s` and an integer `k`, return `true` if `s` is a `k`**\-palindrome**.

A string is `k`**\-palindrome** if it can be transformed into a palindrome by removing at most `k` characters from it.

**Example 1:**

**Input:** s =  "abcdeca ", k = 2
**Output:** true
**Explanation:** Remove 'b' and 'e' characters.

**Example 2:**

**Input:** s =  "abbababa ", k = 1
**Output:** true

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of only lowercase English letters.
*   `1 <= k <= s.length`
Minimum Cost to Move Chips to The Same Position

We have `n` chips, where the position of the `ith` chip is `position[i]`.

We need to move all the chips to **the same position**. In one step, we can change the position of the `ith` chip from `position[i]` to:

*   `position[i] + 2` or `position[i] - 2` with `cost = 0`.
*   `position[i] + 1` or `position[i] - 1` with `cost = 1`.

Return _the minimum cost_ needed to move all the chips to the same position.

**Example 1:**

**Input:** position = \[1,2,3\]
**Output:** 1
**Explanation:** First step: Move the chip at position 3 to position 1 with cost = 0.
Second step: Move the chip at position 2 to position 1 with cost = 1.
Total cost is 1.

**Example 2:**

**Input:** position = \[2,2,2,3,3\]
**Output:** 2
**Explanation:** We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

**Example 3:**

**Input:** position = \[1,1000000000\]
**Output:** 1

**Constraints:**

*   `1 <= position.length <= 100`
*   `1 <= position[i] <= 10^9`
Longest Arithmetic Subsequence of Given Difference

Given an integer array `arr` and an integer `difference`, return the length of the longest subsequence in `arr` which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals `difference`.

A **subsequence** is a sequence that can be derived from `arr` by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** arr = \[1,2,3,4\], difference = 1
**Output:** 4
**Explanation:** The longest arithmetic subsequence is \[1,2,3,4\].

**Example 2:**

**Input:** arr = \[1,3,5,7\], difference = 1
**Output:** 1
**Explanation:** The longest arithmetic subsequence is any single element.

**Example 3:**

**Input:** arr = \[1,5,7,8,5,3,4,2,1\], difference = -2
**Output:** 4
**Explanation:** The longest arithmetic subsequence is \[7,5,3,1\].

**Constraints:**

*   `1 <= arr.length <= 105`
*   `-104 <= arr[i], difference <= 104`

The node of a binary tree is a leaf if and only if it has no children. The depth of the node of a binary tree is the number of nodes along the path from the root node down to the node itself.
Path with Maximum Gold

In a gold mine `grid` of size `m x n`, each cell in this mine has an integer representing the amount of gold in that cell, `0` if it is empty.

Return the maximum amount of gold you can collect under the conditions:

*   Every time you are located in a cell you will collect all the gold in that cell.
*   From your position, you can walk one step to the left, right, up, or down.
*   You can't visit the same cell more than once.
*   Never visit a cell with `0` gold.
*   You can start and stop collecting gold from **any** position in the grid that has some gold.

**Example 1:**

**Input:** grid = \[\[0,6,0\],\[5,8,7\],\[0,9,0\]\]
**Output:** 24
**Explanation:**
\[\[0,6,0\],
 \[5,8,7\],
 \[0,9,0\]\]
Path to get the maximum gold, 9 -> 8 -> 7.

**Example 2:**

**Input:** grid = \[\[1,0,7\],\[2,0,6\],\[3,4,5\],\[0,3,0\],\[9,0,20\]\]
**Output:** 28
**Explanation:**
\[\[1,0,7\],
 \[2,0,6\],
 \[3,4,5\],
 \[0,3,0\],
 \[9,0,20\]\]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 15`
*   `0 <= grid[i][j] <= 100`
*   There are at most **25** cells containing gold.
Count Vowels Permutation

Given an integer `n`, your task is to count how many strings of length `n` can be formed under the following rules:

*   Each character is a lower case vowel (`'a'`, `'e'`, `'i'`, `'o'`, `'u'`)
*   Each vowel `'a'` may only be followed by an `'e'`.
*   Each vowel `'e'` may only be followed by an `'a'` or an `'i'`.
*   Each vowel `'i'` **may not** be followed by another `'i'`.
*   Each vowel `'o'` may only be followed by an `'i'` or a `'u'`.
*   Each vowel `'u'` may only be followed by an `'a'.`

Since the answer may be too large, return it modulo `10^9 + 7.`

**Example 1:**

**Input:** n = 1
**Output:** 5
**Explanation:** All possible strings are:  "a ",  "e ",  "i " ,  "o " and  "u ".

**Example 2:**

**Input:** n = 2
**Output:** 10
**Explanation:** All possible strings are:  "ae ",  "ea ",  "ei ",  "ia ",  "ie ",  "io ",  "iu ",  "oi ",  "ou " and  "ua ".

**Example 3:**

**Input:** n = 5
**Output:** 68

**Constraints:**

*   `1 <= n <= 2 * 10^4`
Split a String in Balanced Strings

**Balanced** strings are those that have an equal quantity of `'L'` and `'R'` characters.

Given a **balanced** string `s`, split it into some number of substrings such that:

*   Each substring is balanced.

Return _the **maximum** number of balanced strings you can obtain._

**Example 1:**

**Input:** s =  "RLRRLLRLRL "
**Output:** 4
**Explanation:** s can be split into  "RL ",  "RRLL ",  "RL ",  "RL ", each substring contains same number of 'L' and 'R'.

**Example 2:**

**Input:** s =  "RLRRRLLRLL "
**Output:** 2
**Explanation:** s can be split into  "RL ",  "RRRLLRLL ", each substring contains same number of 'L' and 'R'.
Note that s cannot be split into  "RL ",  "RR ",  "RL ",  "LR ",  "LL ", because the 2nd and 5th substrings are not balanced.

**Example 3:**

**Input:** s =  "LLLLRRRR "
**Output:** 1
**Explanation:** s can be split into  "LLLLRRRR ".

**Constraints:**

*   `2 <= s.length <= 1000`
*   `s[i]` is either `'L'` or `'R'`.
*   `s` is a **balanced** string.
Queens That Can Attack the King

On a **0-indexed** `8 x 8` chessboard, there can be multiple black queens ad one white king.

You are given a 2D integer array `queens` where `queens[i] = [xQueeni, yQueeni]` represents the position of the `ith` black queen on the chessboard. You are also given an integer array `king` of length `2` where `king = [xKing, yKing]` represents the position of the white king.

Return _the coordinates of the black queens that can directly attack the king_. You may return the answer in **any order**.

**Example 1:**

**Input:** queens = \[\[0,1\],\[1,0\],\[4,0\],\[0,4\],\[3,3\],\[2,4\]\], king = \[0,0\]
**Output:** \[\[0,1\],\[1,0\],\[3,3\]\]
**Explanation:** The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

**Example 2:**

**Input:** queens = \[\[0,0\],\[1,1\],\[2,2\],\[3,4\],\[3,5\],\[4,4\],\[4,5\]\], king = \[3,3\]
**Output:** \[\[2,2\],\[3,4\],\[4,4\]\]
**Explanation:** The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

**Constraints:**

*   `1 <= queens.length < 64`
*   `queens[i].length == king.length == 2`
*   `0 <= xQueeni, yQueeni, xKing, yKing < 8`
*   All the given positions are **unique**.
Dice Roll Simulation

A die simulator generates a random number from `1` to `6` for each roll. You introduced a constraint to the generator such that it cannot roll the number `i` more than `rollMax[i]` (**1-indexed**) consecutive times.

Given an array of integers `rollMax` and an integer `n`, return _the number of distinct sequences that can be obtained with exact_ `n` _rolls_. Since the answer may be too large, return it **modulo** `109 + 7`.

Two sequences are considered different if at least one element differs from each other.

**Example 1:**

**Input:** n = 2, rollMax = \[1,1,2,2,2,3\]
**Output:** 34
**Explanation:** There will be 2 rolls of die, if there are no constraints on the die, there are 6 \* 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

**Example 2:**

**Input:** n = 2, rollMax = \[1,1,1,1,1,1\]
**Output:** 30

**Example 3:**

**Input:** n = 3, rollMax = \[1,1,1,2,2,3\]
**Output:** 181

**Constraints:**

*   `1 <= n <= 5000`
*   `rollMax.length == 6`
*   `1 <= rollMax[i] <= 15`
Maximum Equal Frequency

Given an array `nums` of positive integers, return the longest possible length of an array prefix of `nums`, such that it is possible to remove **exactly one** element from this prefix so that every number that has appeared in it will have the same number of occurrences.

If after removing one element there are no remaining elements, it's still considered that every appeared number has the same number of ocurrences (0).

**Example 1:**

**Input:** nums = \[2,2,1,1,5,3,3,5\]
**Output:** 7
**Explanation:** For the subarray \[2,2,1,1,5,3,3\] of length 7, if we remove nums\[4\] = 5, we will get \[2,2,1,1,3,3\], so that each number will appear exactly twice.

**Example 2:**

**Input:** nums = \[1,1,1,2,2,2,3,3,3,4,4,4,5\]
**Output:** 13

**Constraints:**

*   `2 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Airplane Seat Assignment Probability

`n` passengers board an airplane with exactly `n` seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of the passengers will:

*   Take their own seat if it is still available, and
*   Pick other seats randomly when they find their seat occupied

Return _the probability that the_ `nth` _person gets his own seat_.

**Example 1:**

**Input:** n = 1
**Output:** 1.00000
**Explanation:** The first person can only get the first seat.

**Example 2:**

**Input:** n = 2
**Output:** 0.50000
**Explanation:** The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

**Constraints:**

*   `1 <= n <= 105`
Missing Number In Arithmetic Progression

In some array `arr`, the values were in arithmetic progression: the values `arr[i + 1] - arr[i]` are all equal for every `0 <= i < arr.length - 1`.

A value from `arr` was removed that **was not the first or last value in the array**.

Given `arr`, return _the removed value_.

**Example 1:**

**Input:** arr = \[5,7,11,13\]
**Output:** 9
**Explanation:** The previous array was \[5,7,**9**,11,13\].

**Example 2:**

**Input:** arr = \[15,13,12\]
**Output:** 14
**Explanation:** The previous array was \[15,**14**,13,12\].

**Constraints:**

*   `3 <= arr.length <= 1000`
*   `0 <= arr[i] <= 105`
*   The given array is **guaranteed** to be a valid array.
Meeting Scheduler

Given the availability time slots arrays `slots1` and `slots2` of two people and a meeting duration `duration`, return the **earliest time slot** that works for both of them and is of duration `duration`.

If there is no common time slot that satisfies the requirements, return an **empty array**.

The format of a time slot is an array of two elements `[start, end]` representing an inclusive time range from `start` to `end`.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots `[start1, end1]` and `[start2, end2]` of the same person, either `start1 > end2` or `start2 > end1`.

**Example 1:**

**Input:** slots1 = \[\[10,50\],\[60,120\],\[140,210\]\], slots2 = \[\[0,15\],\[60,70\]\], duration = 8
**Output:** \[60,68\]

**Example 2:**

**Input:** slots1 = \[\[10,50\],\[60,120\],\[140,210\]\], slots2 = \[\[0,15\],\[60,70\]\], duration = 12
**Output:** \[\]

**Constraints:**

*   `1 <= slots1.length, slots2.length <= 104`
*   `slots1[i].length, slots2[i].length == 2`
*   `slots1[i][0] < slots1[i][1]`
*   `slots2[i][0] < slots2[i][1]`
*   `0 <= slots1[i][j], slots2[i][j] <= 109`
*   `1 <= duration <= 106`
Toss Strange Coins

You have some coins. The `i`\-th coin has a probability `prob[i]` of facing heads when tossed.

Return the probability that the number of coins facing heads equals `target` if you toss every coin exactly once.

**Example 1:**

**Input:** prob = \[0.4\], target = 1
**Output:** 0.40000

**Example 2:**

**Input:** prob = \[0.5,0.5,0.5,0.5,0.5\], target = 0
**Output:** 0.03125

**Constraints:**

*   `1 <= prob.length <= 1000`
*   `0 <= prob[i] <= 1`
*   `0 <= target` `<= prob.length`
*   Answers will be accepted as correct if they are within `10^-5` of the correct answer.
Divide Chocolate

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array `sweetness`.

You want to share the chocolate with your `k` friends so you start cutting the chocolate bar into `k + 1` pieces using `k` cuts, each piece consists of some **consecutive** chunks.

Being generous, you will eat the piece with the **minimum total sweetness** and give the other pieces to your friends.

Find the **maximum total sweetness** of the piece you can get by cutting the chocolate bar optimally.

**Example 1:**

**Input:** sweetness = \[1,2,3,4,5,6,7,8,9\], k = 5
**Output:** 6
**Explanation:** You can divide the chocolate to \[1,2,3\], \[4,5\], \[6\], \[7\], \[8\], \[9\]

**Example 2:**

**Input:** sweetness = \[5,6,7,8,9,1,2,3,4\], k = 8
**Output:** 1
**Explanation:** There is only one way to cut the bar into 9 pieces.

**Example 3:**

**Input:** sweetness = \[1,2,2,1,2,2,1,2,2\], k = 2
**Output:** 5
**Explanation:** You can divide the chocolate to \[1,2,2\], \[1,2,2\], \[1,2,2\]

**Constraints:**

*   `0 <= k < sweetness.length <= 104`
*   `1 <= sweetness[i] <= 105`
Check If It Is a Straight Line

You are given an array `coordinates`, `coordinates[i] = [x, y]`, where `[x, y]` represents the coordinate of a point. Check if these points make a straight line in the XY plane.

**Example 1:**

**Input:** coordinates = \[\[1,2\],\[2,3\],\[3,4\],\[4,5\],\[5,6\],\[6,7\]\]
**Output:** true

**Example 2:**

**Input:** coordinates = \[\[1,1\],\[2,2\],\[3,4\],\[4,5\],\[5,6\],\[7,7\]\]
**Output:** false

**Constraints:**

*   `2 <= coordinates.length <= 1000`
*   `coordinates[i].length == 2`
*   `-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4`
*   `coordinates` contains no duplicate point.