bowang0911/leetcode huggingface dataset:
Wiggle Subsequence

A **wiggle sequence** is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

*   For example, `[1, 7, 4, 9, 2, 5]` is a **wiggle sequence** because the differences `(6, -3, 5, -7, 3)` alternate between positive and negative.
*   In contrast, `[1, 4, 7, 2, 5]` and `[1, 7, 4, 5, 5]` are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A **subsequence** is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array `nums`, return _the length of the longest **wiggle subsequence** of_ `nums`.

**Example 1:**

**Input:** nums = \[1,7,4,9,2,5\]
**Output:** 6
**Explanation:** The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

**Example 2:**

**Input:** nums = \[1,17,5,10,13,15,10,5,16,8\]
**Output:** 7
**Explanation:** There are several subsequences that achieve this length.
One is \[1, 17, 10, 13, 10, 16, 8\] with differences (16, -7, 3, -3, 6, -8).

**Example 3:**

**Input:** nums = \[1,2,3,4,5,6,7,8,9\]
**Output:** 2

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `0 <= nums[i] <= 1000`

**Follow up:** Could you solve this in `O(n)` time?
Combination Sum IV

Given an array of **distinct** integers `nums` and a target integer `target`, return _the number of possible combinations that add up to_ `target`.

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

**Example 1:**

**Input:** nums = \[1,2,3\], target = 4
**Output:** 7
**Explanation:**
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

**Example 2:**

**Input:** nums = \[9\], target = 3
**Output:** 0

**Constraints:**

*   `1 <= nums.length <= 200`
*   `1 <= nums[i] <= 1000`
*   All the elements of `nums` are **unique**.
*   `1 <= target <= 1000`

**Follow up:** What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
Kth Smallest Element in a Sorted Matrix

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(n2)`.

**Example 1:**

**Input:** matrix = \[\[1,5,9\],\[10,11,13\],\[12,13,15\]\], k = 8
**Output:** 13
**Explanation:** The elements in the matrix are \[1,5,9,10,11,12,13,**13**,15\], and the 8th smallest number is 13

**Example 2:**

**Input:** matrix = \[\[-5\]\], k = 1
**Output:** -5

**Constraints:**

*   `n == matrix.length == matrix[i].length`
*   `1 <= n <= 300`
*   `-109 <= matrix[i][j] <= 109`
*   All the rows and columns of `matrix` are **guaranteed** to be sorted in **non-decreasing order**.
*   `1 <= k <= n2`

**Follow up:**

*   Could you solve the problem with a constant memory (i.e., `O(1)` memory complexity)?
*   Could you solve the problem in `O(n)` time complexity? The solution may be too advanced for an interview but you may find reading [this paper](http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf) fun.
Design Phone Directory

Design a phone directory that initially has `maxNumbers` empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the `PhoneDirectory` class:

*   `PhoneDirectory(int maxNumbers)` Initializes the phone directory with the number of available slots `maxNumbers`.
*   `int get()` Provides a number that is not assigned to anyone. Returns `-1` if no number is available.
*   `bool check(int number)` Returns `true` if the slot `number` is available and `false` otherwise.
*   `void release(int number)` Recycles or releases the slot `number`.

**Example 1:**

**Input**
\[ "PhoneDirectory ",  "get ",  "get ",  "check ",  "get ",  "check ",  "release ",  "check "\]
\[\[3\], \[\], \[\], \[2\], \[\], \[2\], \[2\], \[2\]\]
**Output**
\[null, 0, 1, true, 2, false, null, true\]

**Explanation**
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // It can return any available phone number. Here we assume it returns 0.
phoneDirectory.get();      // Assume it returns 1.
phoneDirectory.check(2);   // The number 2 is available, so return true.
phoneDirectory.get();      // It returns 2, the only number that is left.
phoneDirectory.check(2);   // The number 2 is no longer available, so return false.
phoneDirectory.release(2); // Release number 2 back to the pool.
phoneDirectory.check(2);   // Number 2 is available again, return true.

**Constraints:**

*   `1 <= maxNumbers <= 104`
*   `0 <= number < maxNumbers`
*   At most `2 * 104` calls will be made to `get`, `check`, and `release`.
Insert Delete GetRandom O(1)

Implement the `RandomizedSet` class:

*   `RandomizedSet()` Initializes the `RandomizedSet` object.
*   `bool insert(int val)` Inserts an item `val` into the set if not present. Returns `true` if the item was not present, `false` otherwise.
*   `bool remove(int val)` Removes an item `val` from the set if present. Returns `true` if the item was present, `false` otherwise.
*   `int getRandom()` Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.

You must implement the functions of the class such that each function works in **average** `O(1)` time complexity.

**Example 1:**

**Input**
\[ "RandomizedSet ",  "insert ",  "remove ",  "insert ",  "getRandom ",  "remove ",  "insert ",  "getRandom "\]
\[\[\], \[1\], \[2\], \[2\], \[\], \[1\], \[2\], \[\]\]
**Output**
\[null, true, false, true, 2, true, false, 2\]

**Explanation**
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains \[1,2\].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains \[2\].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

**Constraints:**

*   `-231 <= val <= 231 - 1`
*   At most `2 *` `105` calls will be made to `insert`, `remove`, and `getRandom`.
*   There will be **at least one** element in the data structure when `getRandom` is called.
Insert Delete GetRandom O(1) - Duplicates allowed

`RandomizedCollection` is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element.

Implement the `RandomizedCollection` class:

*   `RandomizedCollection()` Initializes the empty `RandomizedCollection` object.
*   `bool insert(int val)` Inserts an item `val` into the multiset, even if the item is already present. Returns `true` if the item is not present, `false` otherwise.
*   `bool remove(int val)` Removes an item `val` from the multiset if present. Returns `true` if the item is present, `false` otherwise. Note that if `val` has multiple occurrences in the multiset, we only remove one of them.
*   `int getRandom()` Returns a random element from the current multiset of elements. The probability of each element being returned is **linearly related** to the number of the same values the multiset contains.

You must implement the functions of the class such that each function works on **average** `O(1)` time complexity.

**Note:** The test cases are generated such that `getRandom` will only be called if there is **at least one** item in the `RandomizedCollection`.

**Example 1:**

**Input**
\[ "RandomizedCollection ",  "insert ",  "insert ",  "insert ",  "getRandom ",  "remove ",  "getRandom "\]
\[\[\], \[1\], \[1\], \[2\], \[\], \[1\], \[\]\]
**Output**
\[null, true, false, true, 2, true, 1\]

**Explanation**
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);   // return true since the collection does not contain 1.
                                  // Inserts 1 into the collection.
randomizedCollection.insert(1);   // return false since the collection contains 1.
                                  // Inserts another 1 into the collection. Collection now contains \[1,1\].
randomizedCollection.insert(2);   // return true since the collection does not contain 2.
                                  // Inserts 2 into the collection. Collection now contains \[1,1,2\].
randomizedCollection.getRandom(); // getRandom should:
                                  // - return 1 with probability 2/3, or
                                  // - return 2 with probability 1/3.
randomizedCollection.remove(1);   // return true since the collection contains 1.
                                  // Removes 1 from the collection. Collection now contains \[1,2\].
randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

**Constraints:**

*   `-231 <= val <= 231 - 1`
*   At most `2 * 105` calls **in total** will be made to `insert`, `remove`, and `getRandom`.
*   There will be **at least one** element in the data structure when `getRandom` is called.
Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the **same probability** of being chosen.

Implement the `Solution` class:

*   `Solution(ListNode head)` Initializes the object with the head of the singly-linked list `head`.
*   `int getRandom()` Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

**Example 1:**

**Input**
\[ "Solution ",  "getRandom ",  "getRandom ",  "getRandom ",  "getRandom ",  "getRandom "\]
\[\[\[1, 2, 3\]\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, 1, 3, 2, 2, 3\]

**Explanation**
Solution solution = new Solution(\[1, 2, 3\]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

**Constraints:**

*   The number of nodes in the linked list will be in the range `[1, 104]`.
*   `-104 <= Node.val <= 104`
*   At most `104` calls will be made to `getRandom`.

**Follow up:**

*   What if the linked list is extremely large and its length is unknown to you?
*   Could you solve this efficiently without using extra space?
Ransom Note

Given two strings `ransomNote` and `magazine`, return `true` _if_ `ransomNote` _can be constructed by using the letters from_ `magazine` _and_ `false` _otherwise_.

Each letter in `magazine` can only be used once in `ransomNote`.

**Example 1:**

**Input:** ransomNote = "a", magazine = "b"
**Output:** false

**Example 2:**

**Input:** ransomNote = "aa", magazine = "ab"
**Output:** false

**Example 3:**

**Input:** ransomNote = "aa", magazine = "aab"
**Output:** true

**Constraints:**

*   `1 <= ransomNote.length, magazine.length <= 105`
*   `ransomNote` and `magazine` consist of lowercase English letters.
Shuffle an Array

Given an integer array `nums`, design an algorithm to randomly shuffle the array. All permutations of the array should be **equally likely** as a result of the shuffling.

Implement the `Solution` class:

*   `Solution(int[] nums)` Initializes the object with the integer array `nums`.
*   `int[] reset()` Resets the array to its original configuration and returns it.
*   `int[] shuffle()` Returns a random shuffling of the array.

**Example 1:**

**Input**
\[ "Solution ",  "shuffle ",  "reset ",  "shuffle "\]
\[\[\[1, 2, 3\]\], \[\], \[\], \[\]\]
**Output**
\[null, \[3, 1, 2\], \[1, 2, 3\], \[1, 3, 2\]\]

**Explanation**
Solution solution = new Solution(\[1, 2, 3\]);
solution.shuffle();    // Shuffle the array \[1,2,3\] and return its result.
                       // Any permutation of \[1,2,3\] must be equally likely to be returned.
                       // Example: return \[3, 1, 2\]
solution.reset();      // Resets the array back to its original configuration \[1,2,3\]. Return \[1, 2, 3\]
solution.shuffle();    // Returns the random shuffling of array \[1,2,3\]. Example: return \[1, 3, 2\]

**Constraints:**

*   `1 <= nums.length <= 50`
*   `-106 <= nums[i] <= 106`
*   All the elements of `nums` are **unique**.
*   At most `104` calls **in total** will be made to `reset` and `shuffle`.
Mini Parser

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return _the deserialized_ `NestedInteger`.

Each element is either an integer or a list whose elements may also be integers or other lists.

**Example 1:**

**Input:** s =  "324 "
**Output:** 324
**Explanation:** You should return a NestedInteger object which contains a single integer 324.

**Example 2:**

**Input:** s =  "\[123,\[456,\[789\]\]\] "
**Output:** \[123,\[456,\[789\]\]\]
**Explanation:** Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789

**Constraints:**

*   `1 <= s.length <= 5 * 104`
*   `s` consists of digits, square brackets `"[] "`, negative sign `'-'`, and commas `','`.
*   `s` is the serialization of valid `NestedInteger`.
*   All the values in the input are in the range `[-106, 106]`.
Lexicographical Numbers

Given an integer `n`, return all the numbers in the range `[1, n]` sorted in lexicographical order.

You must write an algorithm that runs in `O(n)` time and uses `O(1)` extra space.

**Example 1:**

**Input:** n = 13
**Output:** \[1,10,11,12,13,2,3,4,5,6,7,8,9\]

**Example 2:**

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

**Constraints:**

*   `1 <= n <= 5 * 104`
First Unique Character in a String

Given a string `s`, _find the first non-repeating character in it and return its index_. If it does not exist, return `-1`.

**Example 1:**

**Input:** s = "leetcode"
**Output:** 0

**Example 2:**

**Input:** s = "loveleetcode"
**Output:** 2

**Example 3:**

**Input:** s = "aabb"
**Output:** -1

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of only lowercase English letters.
Longest Absolute File Path

Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:

Here, we have `dir` as the only directory in the root. `dir` contains two subdirectories, `subdir1` and `subdir2`. `subdir1` contains a file `file1.ext` and subdirectory `subsubdir1`. `subdir2` contains a subdirectory `subsubdir2`, which contains a file `file2.ext`.

In text form, it looks like this (with ⟶ representing the tab character):

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext

If we were to write this representation in code, it will look like this: `"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext "`. Note that the `'\n'` and `'\t'` are the new-line and tab characters.

Every file and directory has a unique **absolute path** in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by `'/'s`. Using the above example, the **absolute path** to `file2.ext` is `"dir/subdir2/subsubdir2/file2.ext "`. Each directory name consists of letters, digits, and/or spaces. Each file name is of the form `name.extension`, where `name` and `extension` consist of letters, digits, and/or spaces.

Given a string `input` representing the file system in the explained format, return _the length of the **longest absolute path** to a **file** in the abstracted file system_. If there is no file in the system, return `0`.

**Note** that the testcases are generated such that the file system is valid and no file or directory name has length 0.

**Example 1:**

**Input:** input =  "dir\\n\\tsubdir1\\n\\tsubdir2\\n\\t\\tfile.ext "
**Output:** 20
**Explanation:** We have only one file, and the absolute path is  "dir/subdir2/file.ext " of length 20.

**Example 2:**

**Input:** input =  "dir\\n\\tsubdir1\\n\\t\\tfile1.ext\\n\\t\\tsubsubdir1\\n\\tsubdir2\\n\\t\\tsubsubdir2\\n\\t\\t\\tfile2.ext "
**Output:** 32
**Explanation:** We have two files:
 "dir/subdir1/file1.ext " of length 21
 "dir/subdir2/subsubdir2/file2.ext " of length 32.
We return 32 since it is the longest absolute path to a file.

**Example 3:**

**Input:** input =  "a "
**Output:** 0
**Explanation:** We do not have any files, just a single directory named  "a ".

**Constraints:**

*   `1 <= input.length <= 104`
*   `input` may contain lowercase or uppercase English letters, a new line character `'\n'`, a tab character `'\t'`, a dot `'.'`, a space `' '`, and digits.
*   All file and directory names have **positive** length.
Find the Difference

You are given two strings `s` and `t`.

String `t` is generated by random shuffling string `s` and then add one more letter at a random position.

Return the letter that was added to `t`.

**Example 1:**

**Input:** s =  "abcd ", t =  "abcde "
**Output:**  "e "
**Explanation:** 'e' is the letter that was added.

**Example 2:**

**Input:** s =  " ", t =  "y "
**Output:**  "y "

**Constraints:**

*   `0 <= s.length <= 1000`
*   `t.length == s.length + 1`
*   `s` and `t` consist of lowercase English letters.
Elimination Game

You have a list `arr` of all integers in the range `[1, n]` sorted in a strictly increasing order. Apply the following algorithm on `arr`:

*   Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
*   Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
*   Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer `n`, return _the last number that remains in_ `arr`.

**Example 1:**

**Input:** n = 9
**Output:** 6
**Explanation:**
arr = \[1, 2, 3, 4, 5, 6, 7, 8, 9\]
arr = \[2, 4, 6, 8\]
arr = \[2, 6\]
arr = \[6\]

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 109`
Perfect Rectangle

Given an array `rectangles` where `rectangles[i] = [xi, yi, ai, bi]` represents an axis-aligned rectangle. The bottom-left point of the rectangle is `(xi, yi)` and the top-right point of it is `(ai, bi)`.

Return `true` _if all the rectangles together form an exact cover of a rectangular region_.

**Example 1:**

**Input:** rectangles = \[\[1,1,3,3\],\[3,1,4,2\],\[3,2,4,4\],\[1,3,2,4\],\[2,3,3,4\]\]
**Output:** true
**Explanation:** All 5 rectangles together form an exact cover of a rectangular region.

**Example 2:**

**Input:** rectangles = \[\[1,1,2,3\],\[1,3,2,4\],\[3,1,4,2\],\[3,2,4,4\]\]
**Output:** false
**Explanation:** Because there is a gap between the two rectangular regions.

**Example 3:**

**Input:** rectangles = \[\[1,1,3,3\],\[3,1,4,2\],\[1,3,2,4\],\[2,2,4,4\]\]
**Output:** false
**Explanation:** Because two of the rectangles overlap with each other.

**Constraints:**

*   `1 <= rectangles.length <= 2 * 104`
*   `rectangles[i].length == 4`
*   `-105 <= xi, yi, ai, bi <= 105`
Is Subsequence

Given two strings `s` and `t`, return `true` _if_ `s` _is a **subsequence** of_ `t`_, or_ `false` _otherwise_.

A **subsequence** of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., `"ace "` is a subsequence of `"abcde "` while `"aec "` is not).

**Example 1:**

**Input:** s = "abc", t = "ahbgdc"
**Output:** true

**Example 2:**

**Input:** s = "axc", t = "ahbgdc"
**Output:** false

**Constraints:**

*   `0 <= s.length <= 100`
*   `0 <= t.length <= 104`
*   `s` and `t` consist only of lowercase English letters.

**Follow up:** Suppose there are lots of incoming `s`, say `s1, s2, ..., sk` where `k >= 109`, and you want to check one by one to see if `t` has its subsequence. In this scenario, how would you change your code?
UTF-8 Validation

Given an integer array `data` representing the data, return whether it is a valid **UTF-8** encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in **UTF8** can be from **1 to 4 bytes** long, subjected to the following rules:

1.  For a **1-byte** character, the first bit is a `0`, followed by its Unicode code.
2.  For an **n-bytes** character, the first `n` bits are all one's, the `n + 1` bit is `0`, followed by `n - 1` bytes with the most significant `2` bits being `10`.

This is how the UTF-8 encoding would work:

     Number of Bytes   |        UTF-8 Octet Sequence
                       |              (binary)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

`x` denotes a bit in the binary form of a byte that may be either `0` or `1`.

**Note:** The input is an array of integers. Only the **least significant 8 bits** of each integer is used to store the data. This means each integer represents only 1 byte of data.

**Example 1:**

**Input:** data = \[197,130,1\]
**Output:** true
**Explanation:** data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

**Example 2:**

**Input:** data = \[235,140,4\]
**Output:** false
**Explanation:** data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

**Constraints:**

*   `1 <= data.length <= 2 * 104`
*   `0 <= data[i] <= 255`
Decode String

Given an encoded string, return its decoded string.

The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. Note that `k` is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, `k`. For example, there will not be input like `3a` or `2[4]`.

The test cases are generated so that the length of the output will never exceed `105`.

**Example 1:**

**Input:** s =  "3\[a\]2\[bc\] "
**Output:**  "aaabcbc "

**Example 2:**

**Input:** s =  "3\[a2\[c\]\] "
**Output:**  "accaccacc "

**Example 3:**

**Input:** s =  "2\[abc\]3\[cd\]ef "
**Output:**  "abcabccdcdcdef "

**Constraints:**

*   `1 <= s.length <= 30`
*   `s` consists of lowercase English letters, digits, and square brackets `'[]'`.
*   `s` is guaranteed to be **a valid** input.
*   All the integers in `s` are in the range `[1, 300]`.