bowang0911/leetcode huggingface dataset:
Moving Stones Until Consecutive II

There are some stones in different positions on the X-axis. You are given an integer array `stones`, the positions of the stones.

Call a stone an **endpoint stone** if it has the smallest or largest position. In one move, you pick up an **endpoint stone** and move it to an unoccupied position so that it is no longer an **endpoint stone**.

*   In particular, if the stones are at say, `stones = [1,2,5]`, you cannot move the endpoint stone at position `5`, since moving it to any position (such as `0`, or `3`) will still keep that stone as an endpoint stone.

The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).

Return _an integer array_ `answer` _of length_ `2` _where_:

*   `answer[0]` _is the minimum number of moves you can play, and_
*   `answer[1]` _is the maximum number of moves you can play_.

**Example 1:**

**Input:** stones = \[7,4,9\]
**Output:** \[1,2\]
**Explanation:** We can move 4 -> 8 for one move to finish the game.
Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.

**Example 2:**

**Input:** stones = \[6,5,4,3,10\]
**Output:** \[2,3\]
**Explanation:** We can move 3 -> 8 then 10 -> 7 to finish the game.
Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game.
Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.

**Constraints:**

*   `3 <= stones.length <= 104`
*   `1 <= stones[i] <= 109`
*   All the values of `stones` are **unique**.
Robot Bounded In Circle

On an infinite plane, a robot initially stands at `(0, 0)` and faces north. Note that:

*   The **north direction** is the positive direction of the y-axis.
*   The **south direction** is the negative direction of the y-axis.
*   The **east direction** is the positive direction of the x-axis.
*   The **west direction** is the negative direction of the x-axis.

The robot can receive one of three instructions:

*   `"G "`: go straight 1 unit.
*   `"L "`: turn 90 degrees to the left (i.e., anti-clockwise direction).
*   `"R "`: turn 90 degrees to the right (i.e., clockwise direction).

The robot performs the `instructions` given in order, and repeats them forever.

Return `true` if and only if there exists a circle in the plane such that the robot never leaves the circle.

**Example 1:**

**Input:** instructions =  "GGLLGG "
**Output:** true
**Explanation:** The robot is initially at (0, 0) facing the north direction.
 "G ": move one step. Position: (0, 1). Direction: North.
 "G ": move one step. Position: (0, 2). Direction: North.
 "L ": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.
 "L ": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.
 "G ": move one step. Position: (0, 1). Direction: South.
 "G ": move one step. Position: (0, 0). Direction: South.
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0).
Based on that, we return true.

**Example 2:**

**Input:** instructions =  "GG "
**Output:** false
**Explanation:** The robot is initially at (0, 0) facing the north direction.
 "G ": move one step. Position: (0, 1). Direction: North.
 "G ": move one step. Position: (0, 2). Direction: North.
Repeating the instructions, keeps advancing in the north direction and does not go into cycles.
Based on that, we return false.

**Example 3:**

**Input:** instructions =  "GL "
**Output:** true
**Explanation:** The robot is initially at (0, 0) facing the north direction.
 "G ": move one step. Position: (0, 1). Direction: North.
 "L ": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West.
 "G ": move one step. Position: (-1, 1). Direction: West.
 "L ": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South.
 "G ": move one step. Position: (-1, 0). Direction: South.
 "L ": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East.
 "G ": move one step. Position: (0, 0). Direction: East.
 "L ": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North.
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
Based on that, we return true.

**Constraints:**

*   `1 <= instructions.length <= 100`
*   `instructions[i]` is `'G'`, `'L'` or, `'R'`.
Flower Planting With No Adjacent

You have `n` gardens, labeled from `1` to `n`, and an array `paths` where `paths[i] = [xi, yi]` describes a bidirectional path between garden `xi` to garden `yi`. In each garden, you want to plant one of 4 types of flowers.

All gardens have **at most 3** paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return _**any** such a choice as an array_ `answer`_, where_ `answer[i]` _is the type of flower planted in the_ `(i+1)th` _garden. The flower types are denoted_ `1`_,_ `2`_,_ `3`_, or_ `4`_. It is guaranteed an answer exists._

**Example 1:**

**Input:** n = 3, paths = \[\[1,2\],\[2,3\],\[3,1\]\]
**Output:** \[1,2,3\]
**Explanation:**
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, \[1,2,3\] is a valid answer. Other valid answers include \[1,2,4\], \[1,4,2\], and \[3,2,1\].

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `1 <= n <= 104`
*   `0 <= paths.length <= 2 * 104`
*   `paths[i].length == 2`
*   `1 <= xi, yi <= n`
*   `xi != yi`
*   Every garden has **at most 3** paths coming into or leaving it.
Partition Array for Maximum Sum

Given an integer array `arr`, partition the array into (contiguous) subarrays of length **at most** `k`. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return _the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a **32-bit** integer._

**Example 1:**

**Input:** arr = \[1,15,7,9,2,5,10\], k = 3
**Output:** 84
**Explanation:** arr becomes \[15,15,15,9,10,10,10\]

**Example 2:**

**Input:** arr = \[1,4,1,5,7,3,6,1,9,9,3\], k = 4
**Output:** 83

**Example 3:**

**Input:** arr = \[1\], k = 1
**Output:** 1

**Constraints:**

*   `1 <= arr.length <= 500`
*   `0 <= arr[i] <= 109`
*   `1 <= k <= arr.length`
Longest Duplicate Substring

Given a string `s`, consider all _duplicated substrings_: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return **any** duplicated substring that has the longest possible length. If `s` does not have a duplicated substring, the answer is `" "`.

**Example 1:**

**Input:** s = "banana"
**Output:** "ana"

**Example 2:**

**Input:** s = "abcd"
**Output:** ""

**Constraints:**

*   `2 <= s.length <= 3 * 104`
*   `s` consists of lowercase English letters.
Last Stone Weight

You are given an array of integers `stones` where `stones[i]` is the weight of the `ith` stone.

We are playing a game with the stones. On each turn, we choose the **heaviest two stones** and smash them together. Suppose the heaviest two stones have weights `x` and `y` with `x <= y`. The result of this smash is:

*   If `x == y`, both stones are destroyed, and
*   If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has new weight `y - x`.

At the end of the game, there is **at most one** stone left.

Return _the weight of the last remaining stone_. If there are no stones left, return `0`.

**Example 1:**

**Input:** stones = \[2,7,4,1,8,1\]
**Output:** 1
**Explanation:** 
We combine 7 and 8 to get 1 so the array converts to \[2,4,1,1,1\] then,
we combine 2 and 4 to get 2 so the array converts to \[2,1,1,1\] then,
we combine 2 and 1 to get 1 so the array converts to \[1,1,1\] then,
we combine 1 and 1 to get 0 so the array converts to \[1\] then that's the value of the last stone.

**Example 2:**

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

**Constraints:**

*   `1 <= stones.length <= 30`
*   `1 <= stones[i] <= 1000`
Remove All Adjacent Duplicates In String

You are given a string `s` consisting of lowercase English letters. A **duplicate removal** consists of choosing two **adjacent** and **equal** letters and removing them.

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

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

**Example 1:**

**Input:** s =  "abbaca "
**Output:**  "ca "
**Explanation:** 
For example, in  "abbaca " we could remove  "bb " since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is  "aaca ", of which only  "aa " is possible, so the final string is  "ca ".

**Example 2:**

**Input:** s =  "azxxzy "
**Output:**  "ay "

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase English letters.
Longest String Chain

You are given an array of `words` where each word consists of lowercase English letters.

`wordA` is a **predecessor** of `wordB` if and only if we can insert **exactly one** letter anywhere in `wordA` **without changing the order of the other characters** to make it equal to `wordB`.

*   For example, `"abc "` is a **predecessor** of `"abac "`, while `"cba "` is not a **predecessor** of `"bcad "`.

A **word chain** is a sequence of words `[word1, word2, ..., wordk]` with `k >= 1`, where `word1` is a **predecessor** of `word2`, `word2` is a **predecessor** of `word3`, and so on. A single word is trivially a **word chain** with `k == 1`.

Return _the **length** of the **longest possible word chain** with words chosen from the given list of_ `words`.

**Example 1:**

**Input:** words = \[ "a ", "b ", "ba ", "bca ", "bda ", "bdca "\]
**Output:** 4
**Explanation**: One of the longest word chains is \[ "a ", "ba ", "bda ", "bdca "\].

**Example 2:**

**Input:** words = \[ "xbc ", "pcxbcf ", "xb ", "cxbc ", "pcxbc "\]
**Output:** 5
**Explanation:** All the words can be put in a word chain \[ "xb ",  "xbc ",  "cxbc ",  "pcxbc ",  "pcxbcf "\].

**Example 3:**

**Input:** words = \[ "abcd ", "dbqca "\]
**Output:** 1
**Explanation:** The trivial word chain \[ "abcd "\] is one of the longest word chains.
\[ "abcd ", "dbqca "\] is not a valid word chain because the ordering of the letters is changed.

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 16`
*   `words[i]` only consists of lowercase English letters.
Last Stone Weight II

You are given an array of integers `stones` where `stones[i]` is the weight of the `ith` stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights `x` and `y` with `x <= y`. The result of this smash is:

*   If `x == y`, both stones are destroyed, and
*   If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has new weight `y - x`.

At the end of the game, there is **at most one** stone left.

Return _the smallest possible weight of the left stone_. If there are no stones left, return `0`.

**Example 1:**

**Input:** stones = \[2,7,4,1,8,1\]
**Output:** 1
**Explanation:**
We can combine 2 and 4 to get 2, so the array converts to \[2,7,1,8,1\] then,
we can combine 7 and 8 to get 1, so the array converts to \[2,1,1,1\] then,
we can combine 2 and 1 to get 1, so the array converts to \[1,1,1\] then,
we can combine 1 and 1 to get 0, so the array converts to \[1\], then that's the optimal value.

**Example 2:**

**Input:** stones = \[31,26,33,21,40\]
**Output:** 5

**Constraints:**

*   `1 <= stones.length <= 30`
*   `1 <= stones[i] <= 100`
Height Checker

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in **non-decreasing order** by height. Let this ordering be represented by the integer array `expected` where `expected[i]` is the expected height of the `ith` student in line.

You are given an integer array `heights` representing the **current order** that the students are standing in. Each `heights[i]` is the height of the `ith` student in line (**0-indexed**).

Return _the **number of indices** where_ `heights[i] != expected[i]`.

**Example 1:**

**Input:** heights = \[1,1,4,2,1,3\]
**Output:** 3
**Explanation:** 
heights:  \[1,1,4,2,1,3\]
expected: \[1,1,1,2,3,4\]
Indices 2, 4, and 5 do not match.

**Example 2:**

**Input:** heights = \[5,1,2,3,4\]
**Output:** 5
**Explanation:**
heights:  \[5,1,2,3,4\]
expected: \[1,2,3,4,5\]
All indices do not match.

**Example 3:**

**Input:** heights = \[1,2,3,4,5\]
**Output:** 0
**Explanation:**
heights:  \[1,2,3,4,5\]
expected: \[1,2,3,4,5\]
All indices match.

**Constraints:**

*   `1 <= heights.length <= 100`
*   `1 <= heights[i] <= 100`
Grumpy Bookstore Owner

There is a bookstore owner that has a store open for `n` minutes. Every minute, some number of customers enter the store. You are given an integer array `customers` of length `n` where `customers[i]` is the number of the customer that enters the store at the start of the `ith` minute and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where `grumpy[i]` is `1` if the bookstore owner is grumpy during the `ith` minute, and is `0` otherwise.

When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for `minutes` consecutive minutes, but can only use it once.

Return _the maximum number of customers that can be satisfied throughout the day_.

**Example 1:**

**Input:** customers = \[1,0,1,2,1,1,7,5\], grumpy = \[0,1,0,1,0,1,0,1\], minutes = 3
**Output:** 16
**Explanation:** The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

**Example 2:**

**Input:** customers = \[1\], grumpy = \[0\], minutes = 1
**Output:** 1

**Constraints:**

*   `n == customers.length == grumpy.length`
*   `1 <= minutes <= n <= 2 * 104`
*   `0 <= customers[i] <= 1000`
*   `grumpy[i]` is either `0` or `1`.
Previous Permutation With One Swap

Given an array of positive integers `arr` (not necessarily distinct), return _the_ _lexicographically_ _largest permutation that is smaller than_ `arr`, that can be **made with exactly one swap**. If it cannot be done, then return the same array.

**Note** that a _swap_ exchanges the positions of two numbers `arr[i]` and `arr[j]`

**Example 1:**

**Input:** arr = \[3,2,1\]
**Output:** \[3,1,2\]
**Explanation:** Swapping 2 and 1.

**Example 2:**

**Input:** arr = \[1,1,5\]
**Output:** \[1,1,5\]
**Explanation:** This is already the smallest permutation.

**Example 3:**

**Input:** arr = \[1,9,4,6,7\]
**Output:** \[1,7,4,6,9\]
**Explanation:** Swapping 9 and 7.

**Constraints:**

*   `1 <= arr.length <= 104`
*   `1 <= arr[i] <= 104`
Distant Barcodes

In a warehouse, there is a row of barcodes, where the `ith` barcode is `barcodes[i]`.

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= barcodes.length <= 10000`
*   `1 <= barcodes[i] <= 10000`
Shortest Way to Form String

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).

Given two strings `source` and `target`, return _the minimum number of **subsequences** of_ `source` _such that their concatenation equals_ `target`. If the task is impossible, return `-1`.

**Example 1:**

**Input:** source =  "abc ", target =  "abcbc "
**Output:** 2
**Explanation:** The target  "abcbc " can be formed by  "abc " and  "bc ", which are subsequences of source  "abc ".

**Example 2:**

**Input:** source =  "abc ", target =  "acdbc "
**Output:** -1
**Explanation:** The target string cannot be constructed from the subsequences of source string due to the character  "d " in target string.

**Example 3:**

**Input:** source =  "xyz ", target =  "xzyxz "
**Output:** 3
**Explanation:** The target string can be constructed as follows  "xz " +  "y " +  "xz ".

**Constraints:**

*   `1 <= source.length, target.length <= 1000`
*   `source` and `target` consist of lowercase English letters.
Confusing Number

A **confusing number** is a number that when rotated `180` degrees becomes a different number with **each digit valid**.

We can rotate digits of a number by `180` degrees to form new digits.

*   When `0`, `1`, `6`, `8`, and `9` are rotated `180` degrees, they become `0`, `1`, `9`, `8`, and `6` respectively.
*   When `2`, `3`, `4`, `5`, and `7` are rotated `180` degrees, they become **invalid**.

Note that after rotating a number, we can ignore leading zeros.

*   For example, after rotating `8000`, we have `0008` which is considered as just `8`.

Given an integer `n`, return `true` _if it is a **confusing number**, or_ `false` _otherwise_.

**Example 1:**

**Input:** n = 6
**Output:** true
**Explanation:** We get 9 after rotating 6, 9 is a valid number, and 9 != 6.

**Example 2:**

**Input:** n = 89
**Output:** true
**Explanation:** We get 68 after rotating 89, 68 is a valid number and 68 != 89.

**Example 3:**

**Input:** n = 11
**Output:** false
**Explanation:** We get 11 after rotating 11, 11 is a valid number but the value remains the same, thus 11 is not a confusing number

**Constraints:**

*   `0 <= n <= 109`
Campus Bikes

On a campus represented on the X-Y plane, there are `n` workers and `m` bikes, with `n <= m`.

You are given an array `workers` of length `n` where `workers[i] = [xi, yi]` is the position of the `ith` worker. You are also given an array `bikes` of length `m` where `bikes[j] = [xj, yj]` is the position of the `jth` bike. All the given positions are **unique**.

Assign a bike to each worker. Among the available bikes and workers, we choose the `(workeri, bikej)` pair with the shortest **Manhattan distance** between each other and assign the bike to that worker.

If there are multiple `(workeri, bikej)` pairs with the same shortest **Manhattan distance**, we choose the pair with **the smallest worker index**. If there are multiple ways to do that, we choose the pair with **the smallest bike index**. Repeat this process until there are no available workers.

Return _an array_ `answer` _of length_ `n`_, where_ `answer[i]` _is the index (**0-indexed**) of the bike that the_ `ith` _worker is assigned to_.

The **Manhattan distance** between two points `p1` and `p2` is `Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|`.

**Example 1:**

**Input:** workers = \[\[0,0\],\[2,1\]\], bikes = \[\[1,2\],\[3,3\]\]
**Output:** \[1,0\]
**Explanation:** Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is \[1, 0\].

**Example 2:**

**Input:** workers = \[\[0,0\],\[1,1\],\[2,0\]\], bikes = \[\[1,0\],\[2,2\],\[2,1\]\]
**Output:** \[0,2,1\]
**Explanation:** Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is \[0,2,1\].

**Constraints:**

*   `n == workers.length`
*   `m == bikes.length`
*   `1 <= n <= m <= 1000`
*   `workers[i].length == bikes[j].length == 2`
*   `0 <= xi, yi < 1000`
*   `0 <= xj, yj < 1000`
*   All worker and bike locations are **unique**.
Minimize Rounding Error to Meet Target

Given an array of `prices` `[p1,p2...,pn]` and a `target`, round each price `pi` to `Roundi(pi)` so that the rounded array `[Round1(p1),Round2(p2)...,Roundn(pn)]` sums to the given `target`. Each operation `Roundi(pi)` could be either `Floor(pi)` or `Ceil(pi)`.

Return the string `"-1 "` if the rounded array is impossible to sum to `target`. Otherwise, return the smallest rounding error, which is defined as `Σ |Roundi(pi) - (pi)|` for `i` from `1` to `n`, as a string with three places after the decimal.

**Example 1:**

**Input:** prices = \[ "0.700 ", "2.800 ", "4.900 "\], target = 8
**Output:**  "1.000 "
**Explanation:**
Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .

**Example 2:**

**Input:** prices = \[ "1.500 ", "2.500 ", "3.500 "\], target = 10
**Output:**  "-1 "
**Explanation:** It is impossible to meet the target.

**Example 3:**

**Input:** prices = \[ "1.500 ", "2.500 ", "3.500 "\], target = 9
**Output:**  "1.500 "

**Constraints:**

*   `1 <= prices.length <= 500`
*   Each string `prices[i]` represents a real number in the range `[0.0, 1000.0]` and has exactly 3 decimal places.
*   `0 <= target <= 106`
All Paths from Source Lead to Destination

Given the `edges` of a directed graph where `edges[i] = [ai, bi]` indicates there is an edge between nodes `ai` and `bi`, and two nodes `source` and `destination` of this graph, determine whether or not all paths starting from `source` eventually, end at `destination`, that is:

*   At least one path exists from the `source` node to the `destination` node
*   If a path exists from the `source` node to a node with no outgoing edges, then that node is equal to `destination`.
*   The number of possible paths from `source` to `destination` is a finite number.

Return `true` if and only if all roads from `source` lead to `destination`.

**Example 1:**

**Input:** n = 3, edges = \[\[0,1\],\[0,2\]\], source = 0, destination = 2
**Output:** false
**Explanation:** It is possible to reach and get stuck on both node 1 and node 2.

**Example 2:**

**Input:** n = 4, edges = \[\[0,1\],\[0,3\],\[1,2\],\[2,1\]\], source = 0, destination = 3
**Output:** false
**Explanation:** We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

**Example 3:**

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

**Constraints:**

*   `1 <= n <= 104`
*   `0 <= edges.length <= 104`
*   `edges.length == 2`
*   `0 <= ai, bi <= n - 1`
*   `0 <= source <= n - 1`
*   `0 <= destination <= n - 1`
*   The given graph may have self-loops and parallel edges.
Missing Element in Sorted Array

Given an integer array `nums` which is sorted in **ascending order** and all of its elements are **unique** and given also an integer `k`, return the `kth` missing number starting from the leftmost number of the array.

**Example 1:**

**Input:** nums = \[4,7,9,10\], k = 1
**Output:** 5
**Explanation:** The first missing number is 5.

**Example 2:**

**Input:** nums = \[4,7,9,10\], k = 3
**Output:** 8
**Explanation:** The missing numbers are \[5,6,8,...\], hence the third missing number is 8.

**Example 3:**

**Input:** nums = \[1,2,4\], k = 3
**Output:** 6
**Explanation:** The missing numbers are \[3,5,6,7,...\], hence the third missing number is 6.

**Constraints:**

*   `1 <= nums.length <= 5 * 104`
*   `1 <= nums[i] <= 107`
*   `nums` is sorted in **ascending order,** and all the elements are **unique**.
*   `1 <= k <= 108`

**Follow up:** Can you find a logarithmic time complexity (i.e., `O(log(n))`) solution?