bowang0911/leetcode huggingface dataset:
Factor Combinations

Numbers can be regarded as the product of their factors.

*   For example, `8 = 2 x 2 x 2 = 2 x 4`.

Given an integer `n`, return _all possible combinations of its factors_. You may return the answer in **any order**.

**Note** that the factors should be in the range `[2, n - 1]`.

**Example 1:**

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

**Example 2:**

**Input:** n = 12
**Output:** \[\[2,6\],\[3,4\],\[2,2,3\]\]

**Example 3:**

**Input:** n = 37
**Output:** \[\]

**Constraints:**

*   `1 <= n <= 107`
Verify Preorder Sequence in Binary Search Tree

Given an array of **unique** integers `preorder`, return `true` _if it is the correct preorder traversal sequence of a binary search tree_.

**Example 1:**

**Input:** preorder = \[5,2,1,3,6\]
**Output:** true

**Example 2:**

**Input:** preorder = \[5,2,6,1,3\]
**Output:** false

**Constraints:**

*   `1 <= preorder.length <= 104`
*   `1 <= preorder[i] <= 104`
*   All the elements of `preorder` are **unique**.

**Follow up:** Could you do it using only constant space complexity?
Paint House

There is a row of `n` houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an `n x 3` cost matrix `costs`.

*   For example, `costs[0][0]` is the cost of painting house `0` with the color red; `costs[1][2]` is the cost of painting house 1 with color green, and so on...

Return _the minimum cost to paint all houses_.

**Example 1:**

**Input:** costs = \[\[17,2,17\],\[16,16,5\],\[14,3,19\]\]
**Output:** 10
**Explanation:** Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

**Example 2:**

**Input:** costs = \[\[7,6,2\]\]
**Output:** 2

**Constraints:**

*   `costs.length == n`
*   `costs[i].length == 3`
*   `1 <= n <= 100`
*   `1 <= costs[i][j] <= 20`
Binary Tree Paths

Given the `root` of a binary tree, return _all root-to-leaf paths in **any order**_.

A **leaf** is a node with no children.

**Example 1:**

**Input:** root = \[1,2,3,null,5\]
**Output:** \[ "1->2->5 ", "1->3 "\]

**Example 2:**

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

**Constraints:**

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

Given an integer `num`, repeatedly add all its digits until the result has only one digit, and return it.

**Example 1:**

**Input:** num = 38
**Output:** 2
**Explanation:** The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

**Example 2:**

**Input:** num = 0
**Output:** 0

**Constraints:**

*   `0 <= num <= 231 - 1`

**Follow up:** Could you do it without any loop/recursion in `O(1)` runtime?
3Sum Smaller

Given an array of `n` integers `nums` and an integer `target`, find the number of index triplets `i`, `j`, `k` with `0 <= i < j < k < n` that satisfy the condition `nums[i] + nums[j] + nums[k] < target`.

**Example 1:**

**Input:** nums = \[-2,0,1,3\], target = 2
**Output:** 2
**Explanation:** Because there are two triplets which sums are less than 2:
\[-2,0,1\]
\[-2,0,3\]

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `n == nums.length`
*   `0 <= n <= 3500`
*   `-100 <= nums[i] <= 100`
*   `-100 <= target <= 100`
Single Number III

Given an integer array `nums`, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in **any order**.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

**Example 1:**

**Input:** nums = \[1,2,1,3,2,5\]
**Output:** \[3,5\]
**Explanation: ** \[5, 3\] is also a valid answer.

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `2 <= nums.length <= 3 * 104`
*   `-231 <= nums[i] <= 231 - 1`
*   Each integer in `nums` will appear twice, only two integers will appear once.
Graph Valid Tree

You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer n and a list of `edges` where `edges[i] = [ai, bi]` indicates that there is an undirected edge between nodes `ai` and `bi` in the graph.

Return `true` _if the edges of the given graph make up a valid tree, and_ `false` _otherwise_.

**Example 1:**

**Input:** n = 5, edges = \[\[0,1\],\[0,2\],\[0,3\],\[1,4\]\]
**Output:** true

**Example 2:**

**Input:** n = 5, edges = \[\[0,1\],\[1,2\],\[2,3\],\[1,3\],\[1,4\]\]
**Output:** false

**Constraints:**

*   `1 <= n <= 2000`
*   `0 <= edges.length <= 5000`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   There are no self-loops or repeated edges.
Ugly Number

An **ugly number** is a positive integer whose prime factors are limited to `2`, `3`, and `5`.

Given an integer `n`, return `true` _if_ `n` _is an **ugly number**_.

**Example 1:**

**Input:** n = 6
**Output:** true
**Explanation:** 6 = 2 \* 3

**Example 2:**

**Input:** n = 1
**Output:** true
**Explanation:** 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

**Example 3:**

**Input:** n = 14
**Output:** false
**Explanation:** 14 is not ugly since it includes the prime factor 7.

**Constraints:**

*   `-231 <= n <= 231 - 1`
Ugly Number II

An **ugly number** is a positive integer whose prime factors are limited to `2`, `3`, and `5`.

Given an integer `n`, return _the_ `nth` _**ugly number**_.

**Example 1:**

**Input:** n = 10
**Output:** 12
**Explanation:** \[1, 2, 3, 4, 5, 6, 8, 9, 10, 12\] is the sequence of the first 10 ugly numbers.

**Example 2:**

**Input:** n = 1
**Output:** 1
**Explanation:** 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

**Constraints:**

*   `1 <= n <= 1690`
Paint House II

There are a row of `n` houses, each house can be painted with one of the `k` colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an `n x k` cost matrix costs.

*   For example, `costs[0][0]` is the cost of painting house `0` with color `0`; `costs[1][2]` is the cost of painting house `1` with color `2`, and so on...

Return _the minimum cost to paint all houses_.

**Example 1:**

**Input:** costs = \[\[1,5,3\],\[2,9,4\]\]
**Output:** 5
**Explanation:**
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

**Example 2:**

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

**Constraints:**

*   `costs.length == n`
*   `costs[i].length == k`
*   `1 <= n <= 100`
*   `2 <= k <= 20`
*   `1 <= costs[i][j] <= 20`

**Follow up:** Could you solve it in `O(nk)` runtime?
Palindrome Permutation

Given a string `s`, return `true` _if a permutation of the string could form a_ _**palindrome**_ _and_ `false` _otherwise_.

**Example 1:**

**Input:** s =  "code "
**Output:** false

**Example 2:**

**Input:** s =  "aab "
**Output:** true

**Example 3:**

**Input:** s =  "carerac "
**Output:** true

**Constraints:**

*   `1 <= s.length <= 5000`
*   `s` consists of only lowercase English letters.
Palindrome Permutation II

Given a string s, return _all the palindromic permutations (without duplicates) of it_.

You may return the answer in **any order**. If `s` has no palindromic permutation, return an empty list.

**Example 1:**

**Input:** s = "aabb"
**Output:** \["abba","baab"\]

**Example 2:**

**Input:** s = "abc"
**Output:** \[\]

**Constraints:**

*   `1 <= s.length <= 16`
*   `s` consists of only lowercase English letters.
Missing Number

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return _the only number in the range that is missing from the array._

**Example 1:**

**Input:** nums = \[3,0,1\]
**Output:** 2
**Explanation:** n = 3 since there are 3 numbers, so all numbers are in the range \[0,3\]. 2 is the missing number in the range since it does not appear in nums.

**Example 2:**

**Input:** nums = \[0,1\]
**Output:** 2
**Explanation:** n = 2 since there are 2 numbers, so all numbers are in the range \[0,2\]. 2 is the missing number in the range since it does not appear in nums.

**Example 3:**

**Input:** nums = \[9,6,4,2,3,5,7,0,1\]
**Output:** 8
**Explanation:** n = 9 since there are 9 numbers, so all numbers are in the range \[0,9\]. 8 is the missing number in the range since it does not appear in nums.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 104`
*   `0 <= nums[i] <= n`
*   All the numbers of `nums` are **unique**.

**Follow up:** Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?
Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are **sorted lexicographically** by the rules of this new language.

Return _a string of the unique letters in the new alien language sorted in **lexicographically increasing order** by the new language's rules._ If there is no solution, return `" "`_._ If there are multiple solutions, return _**any of them**_.

**Example 1:**

**Input:** words = \[ "wrt ", "wrf ", "er ", "ett ", "rftt "\]
**Output:**  "wertf "

**Example 2:**

**Input:** words = \[ "z ", "x "\]
**Output:**  "zx "

**Example 3:**

**Input:** words = \[ "z ", "x ", "z "\]
**Output:**  " "
**Explanation:** The order is invalid, so return ` " "`.

**Constraints:**

*   `1 <= words.length <= 100`
*   `1 <= words[i].length <= 100`
*   `words[i]` consists of only lowercase English letters.
Closest Binary Search Tree Value

Given the `root` of a binary search tree and a `target` value, return _the value in the BST that is closest to the_ `target`. If there are multiple answers, print the smallest.

**Example 1:**

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

**Example 2:**

**Input:** root = \[1\], target = 4.428571
**Output:** 1

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `0 <= Node.val <= 109`
*   `-109 <= target <= 109`
Encode and Decode Strings

Design an algorithm to encode **a list of strings** to **a string**. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector strs) {
  // ... your code
  return encoded\_string;
}

Machine 2 (receiver) has the function:

vector decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded\_string = encode(strs);

and Machine 2 does:

vector strs2 = decode(encoded\_string);

`strs2` in Machine 2 should be the same as `strs` in Machine 1.

Implement the `encode` and `decode` methods.

You are not allowed to solve the problem using any serialize methods (such as `eval`).

**Example 1:**

**Input:** dummy\_input = \[ "Hello ", "World "\]
**Output:** \[ "Hello ", "World "\]
**Explanation:**
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String\[\] strs = decoder.decode(msg);

**Example 2:**

**Input:** dummy\_input = \[ " "\]
**Output:** \[ " "\]

**Constraints:**

*   `1 <= strs.length <= 200`
*   `0 <= strs[i].length <= 200`
*   `strs[i]` contains any possible characters out of `256` valid ASCII characters.

**Follow up:** Could you write a generalized algorithm to work on any possible set of characters?
Closest Binary Search Tree Value II

Given the `root` of a binary search tree, a `target` value, and an integer `k`, return _the_ `k` _values in the BST that are closest to the_ `target`. You may return the answer in **any order**.

You are **guaranteed** to have only one unique set of `k` values in the BST that are closest to the `target`.

**Example 1:**

**Input:** root = \[4,2,5,1,3\], target = 3.714286, k = 2
**Output:** \[4,3\]

**Example 2:**

**Input:** root = \[1\], target = 0.000000, k = 1
**Output:** \[1\]

**Constraints:**

*   The number of nodes in the tree is `n`.
*   `1 <= k <= n <= 104`.
*   `0 <= Node.val <= 109`
*   `-109 <= target <= 109`

**Follow up:** Assume that the BST is balanced. Could you solve it in less than `O(n)` runtime (where `n = total nodes`)?
Integer to English Words

Convert a non-negative integer `num` to its English words representation.

**Example 1:**

**Input:** num = 123
**Output:**  "One Hundred Twenty Three "

**Example 2:**

**Input:** num = 12345
**Output:**  "Twelve Thousand Three Hundred Forty Five "

**Example 3:**

**Input:** num = 1234567
**Output:**  "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven "

**Constraints:**

*   `0 <= num <= 231 - 1`
H-Index

Given an array of integers `citations` where `citations[i]` is the number of citations a researcher received for their `ith` paper, return _the researcher's h-index_.

According to the [definition of h-index on Wikipedia](https://en.wikipedia.org/wiki/H-index): The h-index is defined as the maximum value of `h` such that the given researcher has published at least `h` papers that have each been cited at least `h` times.

**Example 1:**

**Input:** citations = \[3,0,6,1,5\]
**Output:** 3
**Explanation:** \[3,0,6,1,5\] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

**Example 2:**

**Input:** citations = \[1,3,1\]
**Output:** 1

**Constraints:**

*   `n == citations.length`
*   `1 <= n <= 5000`
*   `0 <= citations[i] <= 1000`
H-Index II

Given an array of integers `citations` where `citations[i]` is the number of citations a researcher received for their `ith` paper and `citations` is sorted in **ascending order**, return _the researcher's h-index_.

According to the [definition of h-index on Wikipedia](https://en.wikipedia.org/wiki/H-index): The h-index is defined as the maximum value of `h` such that the given researcher has published at least `h` papers that have each been cited at least `h` times.

You must write an algorithm that runs in logarithmic time.

**Example 1:**

**Input:** citations = \[0,1,3,5,6\]
**Output:** 3
**Explanation:** \[0,1,3,5,6\] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

**Example 2:**

**Input:** citations = \[1,2,100\]
**Output:** 2

**Constraints:**

*   `n == citations.length`
*   `1 <= n <= 105`
*   `0 <= citations[i] <= 1000`
*   `citations` is sorted in **ascending order**.
Paint Fence

You are painting a fence of `n` posts with `k` different colors. You must paint the posts following these rules:

*   Every post must be painted **exactly one** color.
*   There **cannot** be three or more **consecutive** posts with the same color.

Given the two integers `n` and `k`, return _the **number of ways** you can paint the fence_.

**Example 1:**

**Input:** n = 3, k = 2
**Output:** 6
**Explanation:** All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

**Example 2:**

**Input:** n = 1, k = 1
**Output:** 1

**Example 3:**

**Input:** n = 7, k = 2
**Output:** 42

**Constraints:**

*   `1 <= n <= 50`
*   `1 <= k <= 105`
*   The testcases are generated such that the answer is in the range `[0, 231 - 1]` for the given `n` and `k`.
Find the Celebrity

Suppose you are at a party with `n` people labeled from `0` to `n - 1` and among them, there may exist one celebrity. The definition of a celebrity is that all the other `n - 1` people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: "Hi, A. Do you know B? " to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function `bool knows(a, b)` that tells you whether `a` knows `b`. Implement a function `int findCelebrity(n)`. There will be exactly one celebrity if they are at the party.

Return _the celebrity's label if there is a celebrity at the party_. If there is no celebrity, return `-1`.

**Example 1:**

**Input:** graph = \[\[1,1,0\],\[0,1,0\],\[1,1,1\]\]
**Output:** 1
**Explanation:** There are three persons labeled with 0, 1 and 2. graph\[i\]\[j\] = 1 means person i knows person j, otherwise graph\[i\]\[j\] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

**Example 2:**

**Input:** graph = \[\[1,0,1\],\[1,1,0\],\[0,1,1\]\]
**Output:** -1
**Explanation:** There is no celebrity.

**Constraints:**

*   `n == graph.length == graph[i].length`
*   `2 <= n <= 100`
*   `graph[i][j]` is `0` or `1`.
*   `graph[i][i] == 1`

**Follow up:** If the maximum number of allowed calls to the API `knows` is `3 * n`, could you find a solution without exceeding the maximum number of calls?
First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

**Example 1:**

**Input:** n = 5, bad = 4
**Output:** 4
**Explanation:**
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

**Example 2:**

**Input:** n = 1, bad = 1
**Output:** 1

**Constraints:**

*   `1 <= bad <= n <= 231 - 1`
Perfect Squares

Given an integer `n`, return _the least number of perfect square numbers that sum to_ `n`.

A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`, `4`, `9`, and `16` are perfect squares while `3` and `11` are not.

**Example 1:**

**Input:** n = 12
**Output:** 3
**Explanation:** 12 = 4 + 4 + 4.

**Example 2:**

**Input:** n = 13
**Output:** 2
**Explanation:** 13 = 4 + 9.

**Constraints:**

*   `1 <= n <= 104`
Wiggle Sort

Given an integer array `nums`, reorder it such that `nums[0] <= nums[1] >= nums[2] <= nums[3]...`.

You may assume the input array always has a valid answer.

**Example 1:**

**Input:** nums = \[3,5,2,1,6,4\]
**Output:** \[3,5,1,6,2,4\]
**Explanation:** \[1,6,2,5,3,4\] is also accepted.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 5 * 104`
*   `0 <= nums[i] <= 104`
*   It is guaranteed that there will be an answer for the given input `nums`.

**Follow up:** Could you solve the problem in `O(n)` time complexity?
Zigzag Iterator

Given two vectors of integers `v1` and `v2`, implement an iterator to return their elements alternately.

Implement the `ZigzagIterator` class:

*   `ZigzagIterator(List v1, List v2)` initializes the object with the two vectors `v1` and `v2`.
*   `boolean hasNext()` returns `true` if the iterator still has elements, and `false` otherwise.
*   `int next()` returns the current element of the iterator and moves the iterator to the next element.

**Example 1:**

**Input:** v1 = \[1,2\], v2 = \[3,4,5,6\]
**Output:** \[1,3,2,4,5,6\]
**Explanation:** By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: \[1,3,2,4,5,6\].

**Example 2:**

**Input:** v1 = \[1\], v2 = \[\]
**Output:** \[1\]

**Example 3:**

**Input:** v1 = \[\], v2 = \[1\]
**Output:** \[1\]

**Constraints:**

*   `0 <= v1.length, v2.length <= 1000`
*   `1 <= v1.length + v2.length <= 2000`
*   `-231 <= v1[i], v2[i] <= 231 - 1`

**Follow up:** What if you are given `k` vectors? How well can your code be extended to such cases?

**Clarification for the follow-up question:**

The "Zigzag " order is not clearly defined and is ambiguous for `k > 2` cases. If "Zigzag " does not look right to you, replace "Zigzag " with "Cyclic ".

**Follow-up Example:**

**Input:** v1 = \[1,2,3\], v2 = \[4,5,6,7\], v3 = \[8,9\]
**Output:** \[1,4,8,2,5,9,3,6,7\]
Expression Add Operators

Given a string `num` that contains only digits and an integer `target`, return _**all possibilities** to insert the binary operators_ `'+'`_,_ `'-'`_, and/or_ `'*'` _between the digits of_ `num` _so that the resultant expression evaluates to the_ `target` _value_.

Note that operands in the returned expressions **should not** contain leading zeros.

**Example 1:**

**Input:** num =  "123 ", target = 6
**Output:** \[ "1\*2\*3 ", "1+2+3 "\]
**Explanation:** Both  "1\*2\*3 " and  "1+2+3 " evaluate to 6.

**Example 2:**

**Input:** num =  "232 ", target = 8
**Output:** \[ "2\*3+2 ", "2+3\*2 "\]
**Explanation:** Both  "2\*3+2 " and  "2+3\*2 " evaluate to 8.

**Example 3:**

**Input:** num =  "3456237490 ", target = 9191
**Output:** \[\]
**Explanation:** There are no expressions that can be created from  "3456237490 " to evaluate to 9191.

**Constraints:**

*   `1 <= num.length <= 10`
*   `num` consists of only digits.
*   `-231 <= target <= 231 - 1`
Move Zeroes

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

**Note** that you must do this in-place without making a copy of the array.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-231 <= nums[i] <= 231 - 1`

**Follow up:** Could you minimize the total number of operations done?