bowang0911/leetcode huggingface dataset:
Path Sum III

Given the `root` of a binary tree and an integer `targetSum`, return _the number of paths where the sum of the values along the path equals_ `targetSum`.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

**Example 1:**

**Input:** root = \[10,5,-3,3,2,null,11,3,-2,null,1\], targetSum = 8
**Output:** 3
**Explanation:** The paths that sum to 8 are shown.

**Example 2:**

**Input:** root = \[5,4,8,11,null,13,4,7,2,null,null,5,1\], targetSum = 22
**Output:** 3

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 1000]`.
*   `-109 <= Node.val <= 109`
*   `-1000 <= targetSum <= 1000`
Find All Anagrams in a String

Given two strings `s` and `p`, return _an array of all the start indices of_ `p`_'s anagrams in_ `s`. You may return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

**Example 1:**

**Input:** s =  "cbaebabacd ", p =  "abc "
**Output:** \[0,6\]
**Explanation:**
The substring with start index = 0 is  "cba ", which is an anagram of  "abc ".
The substring with start index = 6 is  "bac ", which is an anagram of  "abc ".

**Example 2:**

**Input:** s =  "abab ", p =  "ab "
**Output:** \[0,1,2\]
**Explanation:**
The substring with start index = 0 is  "ab ", which is an anagram of  "ab ".
The substring with start index = 1 is  "ba ", which is an anagram of  "ab ".
The substring with start index = 2 is  "ab ", which is an anagram of  "ab ".

**Constraints:**

*   `1 <= s.length, p.length <= 3 * 104`
*   `s` and `p` consist of lowercase English letters.
Ternary Expression Parser

Given a string `expression` representing arbitrarily nested ternary expressions, evaluate the expression, and return _the result of it_.

You can always assume that the given expression is valid and only contains digits, `'?'`, `':'`, `'T'`, and `'F'` where `'T'` is true and `'F'` is false. All the numbers in the expression are **one-digit** numbers (i.e., in the range `[0, 9]`).

The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, `'T'` or `'F'`.

**Example 1:**

**Input:** expression =  "T?2:3 "
**Output:**  "2 "
**Explanation:** If true, then result is 2; otherwise result is 3.

**Example 2:**

**Input:** expression =  "F?1:T?4:5 "
**Output:**  "4 "
**Explanation:** The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
 "(F ? 1 : (T ? 4 : 5)) " -->  "(F ? 1 : 4) " -->  "4 "
or  "(F ? 1 : (T ? 4 : 5)) " -->  "(T ? 4 : 5) " -->  "4 "

**Example 3:**

**Input:** expression =  "T?T?F:5:3 "
**Output:**  "F "
**Explanation:** The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
 "(T ? (T ? F : 5) : 3) " -->  "(T ? F : 3) " -->  "F "
 "(T ? (T ? F : 5) : 3) " -->  "(T ? F : 5) " -->  "F "

**Constraints:**

*   `5 <= expression.length <= 104`
*   `expression` consists of digits, `'T'`, `'F'`, `'?'`, and `':'`.
*   It is **guaranteed** that `expression` is a valid ternary expression and that each number is a **one-digit number**.
K-th Smallest in Lexicographical Order

Given two integers `n` and `k`, return _the_ `kth` _lexicographically smallest integer in the range_ `[1, n]`.

**Example 1:**

**Input:** n = 13, k = 2
**Output:** 10
**Explanation:** The lexicographical order is \[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9\], so the second smallest number is 10.

**Example 2:**

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

**Constraints:**

*   `1 <= k <= n <= 109`
Arranging Coins

You have `n` coins and you want to build a staircase with these coins. The staircase consists of `k` rows where the `ith` row has exactly `i` coins. The last row of the staircase **may be** incomplete.

Given the integer `n`, return _the number of **complete rows** of the staircase you will build_.

**Example 1:**

**Input:** n = 5
**Output:** 2
**Explanation:** Because the 3rd row is incomplete, we return 2.

**Example 2:**

**Input:** n = 8
**Output:** 3
**Explanation:** Because the 4th row is incomplete, we return 3.

**Constraints:**

*   `1 <= n <= 231 - 1`
Find All Duplicates in an Array

Given an integer array `nums` of length `n` where all the integers of `nums` are in the range `[1, n]` and each integer appears **once** or **twice**, return _an array of all the integers that appears **twice**_.

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

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 105`
*   `1 <= nums[i] <= n`
*   Each element in `nums` appears **once** or **twice**.
String Compression

Given an array of characters `chars`, compress it using the following algorithm:

Begin with an empty string `s`. For each group of **consecutive repeating characters** in `chars`:

*   If the group's length is `1`, append the character to `s`.
*   Otherwise, append the character followed by the group's length.

The compressed string `s` **should not be returned separately**, but instead, be stored **in the input character array `chars`**. Note that group lengths that are `10` or longer will be split into multiple characters in `chars`.

After you are done **modifying the input array,** return _the new length of the array_.

You must write an algorithm that uses only constant extra space.

**Example 1:**

**Input:** chars = \[ "a ", "a ", "b ", "b ", "c ", "c ", "c "\]
**Output:** Return 6, and the first 6 characters of the input array should be: \[ "a ", "2 ", "b ", "2 ", "c ", "3 "\]
**Explanation:** The groups are  "aa ",  "bb ", and  "ccc ". This compresses to  "a2b2c3 ".

**Example 2:**

**Input:** chars = \[ "a "\]
**Output:** Return 1, and the first character of the input array should be: \[ "a "\]
**Explanation:** The only group is  "a ", which remains uncompressed since it's a single character.

**Example 3:**

**Input:** chars = \[ "a ", "b ", "b ", "b ", "b ", "b ", "b ", "b ", "b ", "b ", "b ", "b ", "b "\]
**Output:** Return 4, and the first 4 characters of the input array should be: \[ "a ", "b ", "1 ", "2 "\].
**Explanation:** The groups are  "a " and  "bbbbbbbbbbbb ". This compresses to  "ab12 ".

**Constraints:**

*   `1 <= chars.length <= 2000`
*   `chars[i]` is a lowercase English letter, uppercase English letter, digit, or symbol.
Sequence Reconstruction

You are given an integer array `nums` of length `n` where `nums` is a permutation of the integers in the range `[1, n]`. You are also given a 2D integer array `sequences` where `sequences[i]` is a subsequence of `nums`.

Check if `nums` is the shortest possible and the only **supersequence**. The shortest **supersequence** is a sequence **with the shortest length** and has all `sequences[i]` as subsequences. There could be multiple valid **supersequences** for the given array `sequences`.

*   For example, for `sequences = [[1,2],[1,3]]`, there are two shortest **supersequences**, `[1,2,3]` and `[1,3,2]`.
*   While for `sequences = [[1,2],[1,3],[1,2,3]]`, the only shortest **supersequence** possible is `[1,2,3]`. `[1,2,3,4]` is a possible supersequence but not the shortest.

Return `true` _if_ `nums` _is the only shortest **supersequence** for_ `sequences`_, or_ `false` _otherwise_.

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

**Example 1:**

**Input:** nums = \[1,2,3\], sequences = \[\[1,2\],\[1,3\]\]
**Output:** false
**Explanation:** There are two possible supersequences: \[1,2,3\] and \[1,3,2\].
The sequence \[1,2\] is a subsequence of both: \[**1**,**2**,3\] and \[**1**,3,**2**\].
The sequence \[1,3\] is a subsequence of both: \[**1**,2,**3**\] and \[**1**,**3**,2\].
Since nums is not the only shortest supersequence, we return false.

**Example 2:**

**Input:** nums = \[1,2,3\], sequences = \[\[1,2\]\]
**Output:** false
**Explanation:** The shortest possible supersequence is \[1,2\].
The sequence \[1,2\] is a subsequence of it: \[**1**,**2**\].
Since nums is not the shortest supersequence, we return false.

**Example 3:**

**Input:** nums = \[1,2,3\], sequences = \[\[1,2\],\[1,3\],\[2,3\]\]
**Output:** true
**Explanation:** The shortest possible supersequence is \[1,2,3\].
The sequence \[1,2\] is a subsequence of it: \[**1**,**2**,3\].
The sequence \[1,3\] is a subsequence of it: \[**1**,2,**3**\].
The sequence \[2,3\] is a subsequence of it: \[1,**2**,**3**\].
Since nums is the only shortest supersequence, we return true.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 104`
*   `nums` is a permutation of all the integers in the range `[1, n]`.
*   `1 <= sequences.length <= 104`
*   `1 <= sequences[i].length <= 104`
*   `1 <= sum(sequences[i].length) <= 105`
*   `1 <= sequences[i][j] <= n`
*   All the arrays of `sequences` are **unique**.
*   `sequences[i]` is a subsequence of `nums`.
Add Two Numbers II

You are given two **non-empty** linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example 1:**

**Input:** l1 = \[7,2,4,3\], l2 = \[5,6,4\]
**Output:** \[7,8,0,7\]

**Example 2:**

**Input:** l1 = \[2,4,3\], l2 = \[5,6,4\]
**Output:** \[8,0,7\]

**Example 3:**

**Input:** l1 = \[0\], l2 = \[0\]
**Output:** \[0\]

**Constraints:**

*   The number of nodes in each linked list is in the range `[1, 100]`.
*   `0 <= Node.val <= 9`
*   It is guaranteed that the list represents a number that does not have leading zeros.

**Follow up:** Could you solve it without reversing the input lists?
Arithmetic Slices II - Subsequence

Given an integer array `nums`, return _the number of all the **arithmetic subsequences** of_ `nums`.

A sequence of numbers is called arithmetic if it consists of **at least three elements** and if the difference between any two consecutive elements is the same.

*   For example, `[1, 3, 5, 7, 9]`, `[7, 7, 7, 7]`, and `[3, -1, -5, -9]` are arithmetic sequences.
*   For example, `[1, 1, 2, 5, 7]` is not an arithmetic sequence.

A **subsequence** of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

*   For example, `[2,5,10]` is a subsequence of `[1,2,1,**2**,4,1,**5**,**10**]`.

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

**Example 1:**

**Input:** nums = \[2,4,6,8,10\]
**Output:** 7
**Explanation:** All arithmetic subsequence slices are:
\[2,4,6\]
\[4,6,8\]
\[6,8,10\]
\[2,4,6,8\]
\[4,6,8,10\]
\[2,4,6,8,10\]
\[2,6,10\]

**Example 2:**

**Input:** nums = \[7,7,7,7,7\]
**Output:** 16
**Explanation:** Any subsequence of this array is arithmetic.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `-231 <= nums[i] <= 231 - 1`
Number of Boomerangs

You are given `n` `points` in the plane that are all **distinct**, where `points[i] = [xi, yi]`. A **boomerang** is a tuple of points `(i, j, k)` such that the distance between `i` and `j` equals the distance between `i` and `k` **(the order of the tuple matters)**.

Return _the number of boomerangs_.

**Example 1:**

**Input:** points = \[\[0,0\],\[1,0\],\[2,0\]\]
**Output:** 2
**Explanation:** The two boomerangs are \[\[1,0\],\[0,0\],\[2,0\]\] and \[\[1,0\],\[2,0\],\[0,0\]\].

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `n == points.length`
*   `1 <= n <= 500`
*   `points[i].length == 2`
*   `-104 <= xi, yi <= 104`
*   All the points are **unique**.
Find All Numbers Disappeared in an Array

Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, return _an array of all the integers in the range_ `[1, n]` _that do not appear in_ `nums`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 105`
*   `1 <= nums[i] <= n`

**Follow up:** Could you do it without extra space and in `O(n)` runtime? You may assume the returned list does not count as extra space.
Serialize and Deserialize BST

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a **binary search tree**. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

**The encoded string should be as compact as possible.**

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `0 <= Node.val <= 104`
*   The input tree is **guaranteed** to be a binary search tree.
Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return _the **root node reference** (possibly updated) of the BST_.

Basically, the deletion can be divided into two stages:

1.  Search for a node to remove.
2.  If the node is found, delete the node.

**Example 1:**

**Input:** root = \[5,3,6,2,4,null,7\], key = 3
**Output:** \[5,4,6,2,null,null,7\]
**Explanation:** Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is \[5,4,6,2,null,null,7\], shown in the above BST.
Please notice that another valid answer is \[5,2,6,null,4,null,7\] and it's also accepted.
 

**Example 2:**

**Input:** root = \[5,3,6,2,4,null,7\], key = 0
**Output:** \[5,3,6,2,4,null,7\]
**Explanation:** The tree does not contain a node with value = 0.

**Example 3:**

**Input:** root = \[\], key = 0
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `-105 <= Node.val <= 105`
*   Each node has a **unique** value.
*   `root` is a valid binary search tree.
*   `-105 <= key <= 105`

**Follow up:** Could you solve it with time complexity `O(height of tree)`?
Sort Characters By Frequency

Given a string `s`, sort it in **decreasing order** based on the **frequency** of the characters. The **frequency** of a character is the number of times it appears in the string.

Return _the sorted string_. If there are multiple answers, return _any of them_.

**Example 1:**

**Input:** s =  "tree "
**Output:**  "eert "
**Explanation:** 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore  "eetr " is also a valid answer.

**Example 2:**

**Input:** s =  "cccaaa "
**Output:**  "aaaccc "
**Explanation:** Both 'c' and 'a' appear three times, so both  "cccaaa " and  "aaaccc " are valid answers.
Note that  "cacaca " is incorrect, as the same characters must be together.

**Example 3:**

**Input:** s =  "Aabb "
**Output:**  "bbAa "
**Explanation:**  "bbaA " is also a valid answer, but  "Aabb " is incorrect.
Note that 'A' and 'a' are treated as two different characters.

**Constraints:**

*   `1 <= s.length <= 5 * 105`
*   `s` consists of uppercase and lowercase English letters and digits.
Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array `points` where `points[i] = [xstart, xend]` denotes a balloon whose **horizontal diameter** stretches between `xstart` and `xend`. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up **directly vertically** (in the positive y-direction) from different points along the x-axis. A balloon with `xstart` and `xend` is **burst** by an arrow shot at `x` if `xstart <= x <= xend`. There is **no limit** to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array `points`, return _the **minimum** number of arrows that must be shot to burst all balloons_.

**Example 1:**

**Input:** points = \[\[10,16\],\[2,8\],\[1,6\],\[7,12\]\]
**Output:** 2
**Explanation:** The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons \[2,8\] and \[1,6\].
- Shoot an arrow at x = 11, bursting the balloons \[10,16\] and \[7,12\].

**Example 2:**

**Input:** points = \[\[1,2\],\[3,4\],\[5,6\],\[7,8\]\]
**Output:** 4
**Explanation:** One arrow needs to be shot for each balloon for a total of 4 arrows.

**Example 3:**

**Input:** points = \[\[1,2\],\[2,3\],\[3,4\],\[4,5\]\]
**Output:** 2
**Explanation:** The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons \[1,2\] and \[2,3\].
- Shoot an arrow at x = 4, bursting the balloons \[3,4\] and \[4,5\].

**Constraints:**

*   `1 <= points.length <= 105`
*   `points[i].length == 2`
*   `-231 <= xstart < xend <= 231 - 1`
Minimum Moves to Equal Array Elements

Given an integer array `nums` of size `n`, return _the minimum number of moves required to make all array elements equal_.

In one move, you can increment `n - 1` elements of the array by `1`.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** 3
**Explanation:** Only three moves are needed (remember each move increments two elements):
\[1,2,3\]  =>  \[2,3,3\]  =>  \[3,4,3\]  =>  \[4,4,4\]

**Example 2:**

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

**Constraints:**

*   `n == nums.length`
*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
*   The answer is guaranteed to fit in a **32-bit** integer.
4Sum II

Given four integer arrays `nums1`, `nums2`, `nums3`, and `nums4` all of length `n`, return the number of tuples `(i, j, k, l)` such that:

*   `0 <= i, j, k, l < n`
*   `nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0`

**Example 1:**

**Input:** nums1 = \[1,2\], nums2 = \[-2,-1\], nums3 = \[-1,2\], nums4 = \[0,2\]
**Output:** 2
**Explanation:**
The two tuples are:
1. (0, 0, 0, 1) -> nums1\[0\] + nums2\[0\] + nums3\[0\] + nums4\[1\] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1\[1\] + nums2\[1\] + nums3\[0\] + nums4\[0\] = 2 + (-1) + (-1) + 0 = 0

**Example 2:**

**Input:** nums1 = \[0\], nums2 = \[0\], nums3 = \[0\], nums4 = \[0\]
**Output:** 1

**Constraints:**

*   `n == nums1.length`
*   `n == nums2.length`
*   `n == nums3.length`
*   `n == nums4.length`
*   `1 <= n <= 200`
*   `-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228`
Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child `i` has a greed factor `g[i]`, which is the minimum size of a cookie that the child will be content with; and each cookie `j` has a size `s[j]`. If `s[j] >= g[i]`, we can assign the cookie `j` to the child `i`, and the child `i` will be content. Your goal is to maximize the number of your content children and output the maximum number.

**Example 1:**

**Input:** g = \[1,2,3\], s = \[1,1\]
**Output:** 1
**Explanation:** You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

**Example 2:**

**Input:** g = \[1,2\], s = \[1,2,3\]
**Output:** 2
**Explanation:** You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

**Constraints:**

*   `1 <= g.length <= 3 * 104`
*   `0 <= s.length <= 3 * 104`
*   `1 <= g[i], s[j] <= 231 - 1`
132 Pattern

Given an array of `n` integers `nums`, a **132 pattern** is a subsequence of three integers `nums[i]`, `nums[j]` and `nums[k]` such that `i < j < k` and `nums[i] < nums[k] < nums[j]`.

Return `true` _if there is a **132 pattern** in_ `nums`_, otherwise, return_ `false`_._

**Example 1:**

**Input:** nums = \[1,2,3,4\]
**Output:** false
**Explanation:** There is no 132 pattern in the sequence.

**Example 2:**

**Input:** nums = \[3,1,4,2\]
**Output:** true
**Explanation:** There is a 132 pattern in the sequence: \[1, 4, 2\].

**Example 3:**

**Input:** nums = \[-1,3,2,0\]
**Output:** true
**Explanation:** There are three 132 patterns in the sequence: \[-1, 3, 2\], \[-1, 3, 0\] and \[-1, 2, 0\].

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 2 * 105`
*   `-109 <= nums[i] <= 109`
Circular Array Loop

You are playing a game involving a **circular** array of non-zero integers `nums`. Each `nums[i]` denotes the number of indices forward/backward you must move if you are located at index `i`:

*   If `nums[i]` is positive, move `nums[i]` steps **forward**, and
*   If `nums[i]` is negative, move `nums[i]` steps **backward**.

Since the array is **circular**, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.

A **cycle** in the array consists of a sequence of indices `seq` of length `k` where:

*   Following the movement rules above results in the repeating index sequence `seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...`
*   Every `nums[seq[j]]` is either **all positive** or **all negative**.
*   `k > 1`

Return `true` _if there is a **cycle** in_ `nums`_, or_ `false` _otherwise_.

**Example 1:**

**Input:** nums = \[2,-1,1,2,2\]
**Output:** true
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).

**Example 2:**

**Input:** nums = \[-1,-2,-3,-4,-5,6\]
**Output:** false
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
The only cycle is of size 1, so we return false.

**Example 3:**

**Input:** nums = \[1,-1,5,1,4\]
**Output:** true
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so **it is not a cycle**.
We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).

**Constraints:**

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

**Follow up:** Could you solve it in `O(n)` time complexity and `O(1)` extra space complexity?