bowang0911/leetcode huggingface dataset:
Gas Station

There are `n` gas stations along a circular route, where the amount of gas at the `ith` station is `gas[i]`.

You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `ith` station to its next `(i + 1)th` station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays `gas` and `cost`, return _the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return_ `-1`. If there exists a solution, it is **guaranteed** to be **unique**

**Example 1:**

**Input:** gas = \[1,2,3,4,5\], cost = \[3,4,5,1,2\]
**Output:** 3
**Explanation:**
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

**Example 2:**

**Input:** gas = \[2,3,4\], cost = \[3,4,3\]
**Output:** -1
**Explanation:**
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

**Constraints:**

*   `n == gas.length == cost.length`
*   `1 <= n <= 105`
*   `0 <= gas[i], cost[i] <= 104`
Candy

There are `n` children standing in a line. Each child is assigned a rating value given in the integer array `ratings`.

You are giving candies to these children subjected to the following requirements:

*   Each child must have at least one candy.
*   Children with a higher rating get more candies than their neighbors.

Return _the minimum number of candies you need to have to distribute the candies to the children_.

**Example 1:**

**Input:** ratings = \[1,0,2\]
**Output:** 5
**Explanation:** You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

**Example 2:**

**Input:** ratings = \[1,2,2\]
**Output:** 4
**Explanation:** You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

**Constraints:**

*   `n == ratings.length`
*   `1 <= n <= 2 * 104`
*   `0 <= ratings[i] <= 2 * 104`
Single Number

Given a **non-empty** array of integers `nums`, every element appears _twice_ except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

**Input:** nums = \[2,2,1\]
**Output:** 1

**Example 2:**

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

**Example 3:**

**Input:** nums = \[1\]
**Output:** 1

**Constraints:**

*   `1 <= nums.length <= 3 * 104`
*   `-3 * 104 <= nums[i] <= 3 * 104`
*   Each element in the array appears twice except for one element which appears only once.
Single Number II

Given an integer array `nums` where every element appears **three times** except for one, which appears **exactly once**. _Find the single element and return it_.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

**Input:** nums = \[2,2,3,2\]
**Output:** 3

**Example 2:**

**Input:** nums = \[0,1,0,1,0,1,99\]
**Output:** 99

**Constraints:**

*   `1 <= nums.length <= 3 * 104`
*   `-231 <= nums[i] <= 231 - 1`
*   Each element in `nums` appears exactly **three times** except for one element which appears **once**.
Copy List with Random Pointer

A linked list of length `n` is given such that each node contains an additional random pointer, which could point to any node in the list, or `null`.

Construct a [**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list. The deep copy should consist of exactly `n` **brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the `next` and `random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. **None of the pointers in the new list should point to nodes in the original list**.

For example, if there are two nodes `X` and `Y` in the original list, where `X.random --> Y`, then for the corresponding two nodes `x` and `y` in the copied list, `x.random --> y`.

Return _the head of the copied linked list_.

The linked list is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where:

*   `val`: an integer representing `Node.val`
*   `random_index`: the index of the node (range from `0` to `n-1`) that the `random` pointer points to, or `null` if it does not point to any node.

Your code will **only** be given the `head` of the original linked list.

**Example 1:**

**Input:** head = \[\[7,null\],\[13,0\],\[11,4\],\[10,2\],\[1,0\]\]
**Output:** \[\[7,null\],\[13,0\],\[11,4\],\[10,2\],\[1,0\]\]

**Example 2:**

**Input:** head = \[\[1,1\],\[2,1\]\]
**Output:** \[\[1,1\],\[2,1\]\]

**Example 3:**

**Input:** head = \[\[3,null\],\[3,0\],\[3,null\]\]
**Output:** \[\[3,null\],\[3,0\],\[3,null\]\]

**Constraints:**

*   `0 <= n <= 1000`
*   `-104 <= Node.val <= 104`
*   `Node.random` is `null` or is pointing to some node in the linked list.
Word Break

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

**Input:** s =  "leetcode ", wordDict = \[ "leet ", "code "\]
**Output:** true
**Explanation:** Return true because  "leetcode " can be segmented as  "leet code ".

**Example 2:**

**Input:** s =  "applepenapple ", wordDict = \[ "apple ", "pen "\]
**Output:** true
**Explanation:** Return true because  "applepenapple " can be segmented as  "apple pen apple ".
Note that you are allowed to reuse a dictionary word.

**Example 3:**

**Input:** s =  "catsandog ", wordDict = \[ "cats ", "dog ", "sand ", "and ", "cat "\]
**Output:** false

**Constraints:**

*   `1 <= s.length <= 300`
*   `1 <= wordDict.length <= 1000`
*   `1 <= wordDict[i].length <= 20`
*   `s` and `wordDict[i]` consist of only lowercase English letters.
*   All the strings of `wordDict` are **unique**.
Word Break II

Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

**Input:** s =  "catsanddog ", wordDict = \[ "cat ", "cats ", "and ", "sand ", "dog "\]
**Output:** \[ "cats and dog ", "cat sand dog "\]

**Example 2:**

**Input:** s =  "pineapplepenapple ", wordDict = \[ "apple ", "pen ", "applepen ", "pine ", "pineapple "\]
**Output:** \[ "pine apple pen apple ", "pineapple pen apple ", "pine applepen apple "\]
**Explanation:** Note that you are allowed to reuse a dictionary word.

**Example 3:**

**Input:** s =  "catsandog ", wordDict = \[ "cats ", "dog ", "sand ", "and ", "cat "\]
**Output:** \[\]

**Constraints:**

*   `1 <= s.length <= 20`
*   `1 <= wordDict.length <= 1000`
*   `1 <= wordDict[i].length <= 10`
*   `s` and `wordDict[i]` consist of only lowercase English letters.
*   All the strings of `wordDict` are **unique**.
*   Input is generated in a way that the length of the answer doesn't exceed 105.
Linked List Cycle

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.

Return `true` _if there is a cycle in the linked list_. Otherwise, return `false`.

**Example 1:**

**Input:** head = \[3,2,0,-4\], pos = 1
**Output:** true
**Explanation:** There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2:**

**Input:** head = \[1,2\], pos = 0
**Output:** true
**Explanation:** There is a cycle in the linked list, where the tail connects to the 0th node.

**Example 3:**

**Input:** head = \[1\], pos = -1
**Output:** false
**Explanation:** There is no cycle in the linked list.

**Constraints:**

*   The number of the nodes in the list is in the range `[0, 104]`.
*   `-105 <= Node.val <= 105`
*   `pos` is `-1` or a **valid index** in the linked-list.

**Follow up:** Can you solve it using `O(1)` (i.e. constant) memory?
Linked List Cycle II

Given the `head` of a linked list, return _the node where the cycle begins. If there is no cycle, return_ `null`.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to (**0-indexed**). It is `-1` if there is no cycle. **Note that** `pos` **is not passed as a parameter**.

**Do not modify** the linked list.

**Example 1:**

**Input:** head = \[3,2,0,-4\], pos = 1
**Output:** tail connects to node index 1
**Explanation:** There is a cycle in the linked list, where tail connects to the second node.

**Example 2:**

**Input:** head = \[1,2\], pos = 0
**Output:** tail connects to node index 0
**Explanation:** There is a cycle in the linked list, where tail connects to the first node.

**Example 3:**

**Input:** head = \[1\], pos = -1
**Output:** no cycle
**Explanation:** There is no cycle in the linked list.

**Constraints:**

*   The number of the nodes in the list is in the range `[0, 104]`.
*   `-105 <= Node.val <= 105`
*   `pos` is `-1` or a **valid index** in the linked-list.

**Follow up:** Can you solve it using `O(1)` (i.e. constant) memory?
Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 -> L1 -> ... -> Ln - 1 -> Ln

_Reorder the list to be on the following form:_

L0 -> Ln -> L1 -> Ln - 1 -> L2 -> Ln - 2 -> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

**Example 1:**

**Input:** head = \[1,2,3,4\]
**Output:** \[1,4,2,3\]

**Example 2:**

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

**Constraints:**

*   The number of nodes in the list is in the range `[1, 5 * 104]`.
*   `1 <= Node.val <= 1000`
Binary Tree Preorder Traversal

Given the `root` of a binary tree, return _the preorder traversal of its nodes' values_.

**Example 1:**

**Input:** root = \[1,null,2,3\]
**Output:** \[1,2,3\]

**Example 2:**

**Input:** root = \[\]
**Output:** \[\]

**Example 3:**

**Input:** root = \[1\]
**Output:** \[1\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 100]`.
*   `-100 <= Node.val <= 100`

**Follow up:** Recursive solution is trivial, could you do it iteratively?
Binary Tree Postorder Traversal

Given the `root` of a binary tree, return _the postorder traversal of its nodes' values_.

**Example 1:**

**Input:** root = \[1,null,2,3\]
**Output:** \[3,2,1\]

**Example 2:**

**Input:** root = \[\]
**Output:** \[\]

**Example 3:**

**Input:** root = \[1\]
**Output:** \[1\]

**Constraints:**

*   The number of the nodes in the tree is in the range `[0, 100]`.
*   `-100 <= Node.val <= 100`

**Follow up:** Recursive solution is trivial, could you do it iteratively?
LRU Cache

Design a data structure that follows the constraints of a **[Least Recently Used (LRU) cache](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)**.

Implement the `LRUCache` class:

*   `LRUCache(int capacity)` Initialize the LRU cache with **positive** size `capacity`.
*   `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`.
*   `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, **evict** the least recently used key.

The functions `get` and `put` must each run in `O(1)` average time complexity.

**Example 1:**

**Input**
\[ "LRUCache ",  "put ",  "put ",  "get ",  "put ",  "get ",  "put ",  "get ",  "get ",  "get "\]
\[\[2\], \[1, 1\], \[2, 2\], \[1\], \[3, 3\], \[2\], \[4, 4\], \[1\], \[3\], \[4\]\]
**Output**
\[null, null, null, 1, null, -1, null, -1, 3, 4\]

**Explanation**
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

**Constraints:**

*   `1 <= capacity <= 3000`
*   `0 <= key <= 104`
*   `0 <= value <= 105`
*   At most `2 * 105` calls will be made to `get` and `put`.
Insertion Sort List

Given the `head` of a singly linked list, sort the list using **insertion sort**, and return _the sorted list's head_.

The steps of the **insertion sort** algorithm:

1.  Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2.  At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3.  It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

**Example 1:**

**Input:** head = \[4,2,1,3\]
**Output:** \[1,2,3,4\]

**Example 2:**

**Input:** head = \[-1,5,3,4,0\]
**Output:** \[-1,0,3,4,5\]

**Constraints:**

*   The number of nodes in the list is in the range `[1, 5000]`.
*   `-5000 <= Node.val <= 5000`
Sort List

Given the `head` of a linked list, return _the list after sorting it in **ascending order**_.

**Example 1:**

**Input:** head = \[4,2,1,3\]
**Output:** \[1,2,3,4\]

**Example 2:**

**Input:** head = \[-1,5,3,4,0\]
**Output:** \[-1,0,3,4,5\]

**Example 3:**

**Input:** head = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 5 * 104]`.
*   `-105 <= Node.val <= 105`

**Follow up:** Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?
Max Points on a Line

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the **X-Y** plane, return _the maximum number of points that lie on the same straight line_.

**Example 1:**

**Input:** points = \[\[1,1\],\[2,2\],\[3,3\]\]
**Output:** 3

**Example 2:**

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

**Constraints:**

*   `1 <= points.length <= 300`
*   `points[i].length == 2`
*   `-104 <= xi, yi <= 104`
*   All the `points` are **unique**.
Evaluate Reverse Polish Notation

You are given an array of strings `tokens` that represents an arithmetic expression in a [Reverse Polish Notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation).

Evaluate the expression. Return _an integer that represents the value of the expression_.

**Note** that:

*   The valid operators are `'+'`, `'-'`, `'*'`, and `'/'`.
*   Each operand may be an integer or another expression.
*   The division between two integers always **truncates toward zero**.
*   There will not be any division by zero.
*   The input represents a valid arithmetic expression in a reverse polish notation.
*   The answer and all the intermediate calculations can be represented in a **32-bit** integer.

**Example 1:**

**Input:** tokens = \[ "2 ", "1 ", "+ ", "3 ", "\* "\]
**Output:** 9
**Explanation:** ((2 + 1) \* 3) = 9

**Example 2:**

**Input:** tokens = \[ "4 ", "13 ", "5 ", "/ ", "+ "\]
**Output:** 6
**Explanation:** (4 + (13 / 5)) = 6

**Example 3:**

**Input:** tokens = \[ "10 ", "6 ", "9 ", "3 ", "+ ", "-11 ", "\* ", "/ ", "\* ", "17 ", "+ ", "5 ", "+ "\]
**Output:** 22
**Explanation:** ((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5
= ((10 \* (6 / (12 \* -11))) + 17) + 5
= ((10 \* (6 / -132)) + 17) + 5
= ((10 \* 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

**Constraints:**

*   `1 <= tokens.length <= 104`
*   `tokens[i]` is either an operator: `"+ "`, `"- "`, `"* "`, or `"/ "`, or an integer in the range `[-200, 200]`.
Reverse Words in a String

Given an input string `s`, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s` will be separated by at least one space.

Return _a string of the words in reverse order concatenated by a single space._

**Note** that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

**Example 1:**

**Input:** s =  "the sky is blue "
**Output:**  "blue is sky the "

**Example 2:**

**Input:** s =  "  hello world   "
**Output:**  "world hello "
**Explanation:** Your reversed string should not contain leading or trailing spaces.

**Example 3:**

**Input:** s =  "a good   example "
**Output:**  "example good a "
**Explanation:** You need to reduce multiple spaces between two words to a single space in the reversed string.

**Constraints:**

*   `1 <= s.length <= 104`
*   `s` contains English letters (upper-case and lower-case), digits, and spaces `' '`.
*   There is **at least one** word in `s`.

**Follow-up:** If the string data type is mutable in your language, can you solve it **in-place** with `O(1)` extra space?
Maximum Product Subarray

Given an integer array `nums`, find a subarray that has the largest product, and return _the product_.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = \[2,3,-2,4\]
**Output:** 6
**Explanation:** \[2,3\] has the largest product 6.

**Example 2:**

**Input:** nums = \[-2,0,-1\]
**Output:** 0
**Explanation:** The result cannot be 2, because \[-2,-1\] is not a subarray.

**Constraints:**

*   `1 <= nums.length <= 2 * 104`
*   `-10 <= nums[i] <= 10`
*   The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.
Find Minimum in Rotated Sorted Array

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

*   `[4,5,6,7,0,1,2]` if it was rotated `4` times.
*   `[0,1,2,4,5,6,7]` if it was rotated `7` times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` of **unique** elements, return _the minimum element of this array_.

You must write an algorithm that runs in `O(log n) time.`

**Example 1:**

**Input:** nums = \[3,4,5,1,2\]
**Output:** 1
**Explanation:** The original array was \[1,2,3,4,5\] rotated 3 times.

**Example 2:**

**Input:** nums = \[4,5,6,7,0,1,2\]
**Output:** 0
**Explanation:** The original array was \[0,1,2,4,5,6,7\] and it was rotated 4 times.

**Example 3:**

**Input:** nums = \[11,13,15,17\]
**Output:** 11
**Explanation:** The original array was \[11,13,15,17\] and it was rotated 4 times. 

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 5000`
*   `-5000 <= nums[i] <= 5000`
*   All the integers of `nums` are **unique**.
*   `nums` is sorted and rotated between `1` and `n` times.
Find Minimum in Rotated Sorted Array II

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,4,4,5,6,7]` might become:

*   `[4,5,6,7,0,1,4]` if it was rotated `4` times.
*   `[0,1,4,4,5,6,7]` if it was rotated `7` times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` that may contain **duplicates**, return _the minimum element of this array_.

You must decrease the overall operation steps as much as possible.

**Example 1:**

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

**Example 2:**

**Input:** nums = \[2,2,2,0,1\]
**Output:** 0

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 5000`
*   `-5000 <= nums[i] <= 5000`
*   `nums` is sorted and rotated between `1` and `n` times.

**Follow up:** This problem is similar to [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/), but `nums` may contain **duplicates**. Would this affect the runtime complexity? How and why?
Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the `MinStack` class:

*   `MinStack()` initializes the stack object.
*   `void push(int val)` pushes the element `val` onto the stack.
*   `void pop()` removes the element on the top of the stack.
*   `int top()` gets the top element of the stack.
*   `int getMin()` retrieves the minimum element in the stack.

You must implement a solution with `O(1)` time complexity for each function.

**Example 1:**

**Input**
\[ "MinStack ", "push ", "push ", "push ", "getMin ", "pop ", "top ", "getMin "\]
\[\[\],\[-2\],\[0\],\[-3\],\[\],\[\],\[\],\[\]\]

**Output**
\[null,null,null,null,-3,null,0,-2\]

**Explanation**
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

**Constraints:**

*   `-231 <= val <= 231 - 1`
*   Methods `pop`, `top` and `getMin` operations will always be called on **non-empty** stacks.
*   At most `3 * 104` calls will be made to `push`, `pop`, `top`, and `getMin`.
Binary Tree Upside Down

Given the `root` of a binary tree, turn the tree upside down and return _the new root_.

You can turn a binary tree upside down with the following steps:

1.  The original left child becomes the new root.
2.  The original root becomes the new right child.
3.  The original right child becomes the new left child.

The mentioned steps are done level by level. It is **guaranteed** that every right node has a sibling (a left node with the same parent) and has no children.

**Example 1:**

**Input:** root = \[1,2,3,4,5\]
**Output:** \[4,5,2,null,null,3,1\]

**Example 2:**

**Input:** root = \[\]
**Output:** \[\]

**Example 3:**

**Input:** root = \[1\]
**Output:** \[1\]

**Constraints:**

*   The number of nodes in the tree will be in the range `[0, 10]`.
*   `1 <= Node.val <= 10`
*   Every right node in the tree has a sibling (a left node that shares the same parent).
*   Every right node in the tree has no children.