bowang0911/leetcode huggingface dataset:
Employee Importance

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees `employees` where:

*   `employees[i].id` is the ID of the `ith` employee.
*   `employees[i].importance` is the importance value of the `ith` employee.
*   `employees[i].subordinates` is a list of the IDs of the direct subordinates of the `ith` employee.

Given an integer `id` that represents an employee's ID, return _the **total** importance value of this employee and all their direct and indirect subordinates_.

**Example 1:**

**Input:** employees = \[\[1,5,\[2,3\]\],\[2,3,\[\]\],\[3,3,\[\]\]\], id = 1
**Output:** 11
**Explanation:** Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

**Example 2:**

**Input:** employees = \[\[1,2,\[5\]\],\[5,-3,\[\]\]\], id = 5
**Output:** -3
**Explanation:** Employee 5 has an importance value of -3 and has no direct subordinates.
Thus, the total importance value of employee 5 is -3.

**Constraints:**

*   `1 <= employees.length <= 2000`
*   `1 <= employees[i].id <= 2000`
*   All `employees[i].id` are **unique**.
*   `-100 <= employees[i].importance <= 100`
*   One employee has at most one direct leader and may have several subordinates.
*   The IDs in `employees[i].subordinates` are valid IDs.
Stickers to Spell Word

We are given `n` different types of `stickers`. Each sticker has a lowercase English word on it.

You would like to spell out the given string `target` by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return _the minimum number of stickers that you need to spell out_ `target`. If the task is impossible, return `-1`.

**Note:** In all test cases, all words were chosen randomly from the `1000` most common US English words, and `target` was chosen as a concatenation of two random words.

**Example 1:**

**Input:** stickers = \[ "with ", "example ", "science "\], target =  "thehat "
**Output:** 3
**Explanation:**
We can use 2  "with " stickers, and 1  "example " sticker.
After cutting and rearrange the letters of those stickers, we can form the target  "thehat ".
Also, this is the minimum number of stickers necessary to form the target string.

**Example 2:**

**Input:** stickers = \[ "notice ", "possible "\], target =  "basicbasic "
**Output:** -1
Explanation:
We cannot form the target  "basicbasic " from cutting letters from the given stickers.

**Constraints:**

*   `n == stickers.length`
*   `1 <= n <= 50`
*   `1 <= stickers[i].length <= 10`
*   `1 <= target.length <= 15`
*   `stickers[i]` and `target` consist of lowercase English letters.
Top K Frequent Words

Given an array of strings `words` and an integer `k`, return _the_ `k` _most frequent strings_.

Return the answer **sorted** by **the frequency** from highest to lowest. Sort the words with the same frequency by their **lexicographical order**.

**Example 1:**

**Input:** words = \[ "i ", "love ", "leetcode ", "i ", "love ", "coding "\], k = 2
**Output:** \[ "i ", "love "\]
**Explanation:**  "i " and  "love " are the two most frequent words.
Note that  "i " comes before  "love " due to a lower alphabetical order.

**Example 2:**

**Input:** words = \[ "the ", "day ", "is ", "sunny ", "the ", "the ", "the ", "sunny ", "is ", "is "\], k = 4
**Output:** \[ "the ", "is ", "sunny ", "day "\]
**Explanation:**  "the ",  "is ",  "sunny " and  "day " are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

**Constraints:**

*   `1 <= words.length <= 500`
*   `1 <= words[i].length <= 10`
*   `words[i]` consists of lowercase English letters.
*   `k` is in the range `[1, The number of **unique** words[i]]`

**Follow-up:** Could you solve it in `O(n log(k))` time and `O(n)` extra space?
Binary Number with Alternating Bits

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

**Example 1:**

**Input:** n = 5
**Output:** true
**Explanation:** The binary representation of 5 is: 101

**Example 2:**

**Input:** n = 7
**Output:** false
**Explanation:** The binary representation of 7 is: 111.

**Example 3:**

**Input:** n = 11
**Output:** false
**Explanation:** The binary representation of 11 is: 1011.

**Constraints:**

*   `1 <= n <= 231 - 1`
Number of Distinct Islands

You are given an `m x n` binary matrix `grid`. An island is a group of `1`'s (representing land) connected **4-directionally** (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Return _the number of **distinct** islands_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 50`
*   `grid[i][j]` is either `0` or `1`.
Max Area of Island

You are given an `m x n` binary matrix `grid`. An island is a group of `1`'s (representing land) connected **4-directionally** (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The **area** of an island is the number of cells with a value `1` in the island.

Return _the maximum **area** of an island in_ `grid`. If there is no island, return `0`.

**Example 1:**

**Input:** grid = \[\[0,0,1,0,0,0,0,1,0,0,0,0,0\],\[0,0,0,0,0,0,0,1,1,1,0,0,0\],\[0,1,1,0,1,0,0,0,0,0,0,0,0\],\[0,1,0,0,1,1,0,0,1,0,1,0,0\],\[0,1,0,0,1,1,0,0,1,1,1,0,0\],\[0,0,0,0,0,0,0,0,0,0,1,0,0\],\[0,0,0,0,0,0,0,1,1,1,0,0,0\],\[0,0,0,0,0,0,0,1,1,0,0,0,0\]\]
**Output:** 6
**Explanation:** The answer is not 11, because the island must be connected 4-directionally.

**Example 2:**

**Input:** grid = \[\[0,0,0,0,0,0,0,0\]\]
**Output:** 0

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 50`
*   `grid[i][j]` is either `0` or `1`.
Count Binary Substrings

Given a binary string `s`, return the number of non-empty substrings that have the same number of `0`'s and `1`'s, and all the `0`'s and all the `1`'s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

**Example 1:**

**Input:** s =  "00110011 "
**Output:** 6
**Explanation:** There are 6 substrings that have equal number of consecutive 1's and 0's:  "0011 ",  "01 ",  "1100 ",  "10 ",  "0011 ", and  "01 ".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also,  "00110011 " is not a valid substring because all the 0's (and 1's) are not grouped together.

**Example 2:**

**Input:** s =  "10101 "
**Output:** 4
**Explanation:** There are 4 substrings:  "10 ",  "01 ",  "10 ",  "01 " that have equal number of consecutive 1's and 0's.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is either `'0'` or `'1'`.
Degree of an Array

Given a non-empty array of non-negative integers `nums`, the **degree** of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of `nums`, that has the same degree as `nums`.

**Example 1:**

**Input:** nums = \[1,2,2,3,1\]
**Output:** 2
**Explanation:** 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
\[1, 2, 2, 3, 1\], \[1, 2, 2, 3\], \[2, 2, 3, 1\], \[1, 2, 2\], \[2, 2, 3\], \[2, 2\]
The shortest length is 2. So return 2.

**Example 2:**

**Input:** nums = \[1,2,2,3,1,4,2\]
**Output:** 6
**Explanation:** 
The degree is 3 because the element 2 is repeated 3 times.
So \[2,2,3,1,4,2\] is the shortest subarray, therefore returning 6.

**Constraints:**

*   `nums.length` will be between 1 and 50,000.
*   `nums[i]` will be an integer between 0 and 49,999.
Partition to K Equal Sum Subsets

Given an integer array `nums` and an integer `k`, return `true` if it is possible to divide this array into `k` non-empty subsets whose sums are all equal.

**Example 1:**

**Input:** nums = \[4,3,2,3,5,2,1\], k = 4
**Output:** true
**Explanation:** It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

**Example 2:**

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

**Constraints:**

*   `1 <= k <= nums.length <= 16`
*   `1 <= nums[i] <= 104`
*   The frequency of each element is in the range `[1, 4]`.
Falling Squares

There are several squares being dropped onto the X-axis of a 2D plane.

You are given a 2D integer array `positions` where `positions[i] = [lefti, sideLengthi]` represents the `ith` square with a side length of `sideLengthi` that is dropped with its left edge aligned with X-coordinate `lefti`.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands **on the top side of another square** or **on the X-axis**. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the **height of the current tallest stack of squares**.

Return _an integer array_ `ans` _where_ `ans[i]` _represents the height described above after dropping the_ `ith` _square_.

**Example 1:**

**Input:** positions = \[\[1,2\],\[2,3\],\[6,1\]\]
**Output:** \[2,5,5\]
**Explanation:**
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of \[2, 5, 5\].

**Example 2:**

**Input:** positions = \[\[100,100\],\[200,100\]\]
**Output:** \[100,100\]
**Explanation:**
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of \[100, 100\].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.

**Constraints:**

*   `1 <= positions.length <= 1000`
*   `1 <= lefti <= 108`
*   `1 <= sideLengthi <= 106`
Search in a Binary Search Tree

You are given the `root` of a binary search tree (BST) and an integer `val`.

Find the node in the BST that the node's value equals `val` and return the subtree rooted with that node. If such a node does not exist, return `null`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 5000]`.
*   `1 <= Node.val <= 107`
*   `root` is a binary search tree.
*   `1 <= val <= 107`
Insert into a Binary Search Tree

You are given the `root` node of a binary search tree (BST) and a `value` to insert into the tree. Return _the root node of the BST after the insertion_. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**

**Input:** root = \[4,2,7,1,3\], val = 5
**Output:** \[4,2,7,1,3,5\]
**Explanation:** Another accepted tree is:
 

**Example 2:**

**Input:** root = \[40,20,60,10,30,50,70\], val = 25
**Output:** \[40,20,60,10,30,50,70,null,null,25\]

**Example 3:**

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

**Constraints:**

*   The number of nodes in the tree will be in the range `[0, 104]`.
*   `-108 <= Node.val <= 108`
*   All the values `Node.val` are **unique**.
*   `-108 <= val <= 108`
*   It's **guaranteed** that `val` does not exist in the original BST.
Search in a Sorted Array of Unknown Size

This is an **_interactive problem_**.

You have a sorted array of **unique** elements and an **unknown size**. You do not have an access to the array but you can use the `ArrayReader` interface to access it. You can call `ArrayReader.get(i)` that:

*   returns the value at the `ith` index (**0-indexed**) of the secret array (i.e., `secret[i]`), or
*   returns `231 - 1` if the `i` is out of the boundary of the array.

You are also given an integer `target`.

Return the index `k` of the hidden array where `secret[k] == target` or return `-1` otherwise.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

**Input:** secret = \[-1,0,3,5,9,12\], target = 9
**Output:** 4
**Explanation:** 9 exists in secret and its index is 4.

**Example 2:**

**Input:** secret = \[-1,0,3,5,9,12\], target = 2
**Output:** -1
**Explanation:** 2 does not exist in secret so return -1.

**Constraints:**

*   `1 <= secret.length <= 104`
*   `-104 <= secret[i], target <= 104`
*   `secret` is sorted in a strictly increasing order.
Kth Largest Element in a Stream

Design a class to find the `kth` largest element in a stream. Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

Implement `KthLargest` class:

*   `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`.
*   `int add(int val)` Appends the integer `val` to the stream and returns the element representing the `kth` largest element in the stream.

**Example 1:**

**Input**
\[ "KthLargest ",  "add ",  "add ",  "add ",  "add ",  "add "\]
\[\[3, \[4, 5, 8, 2\]\], \[3\], \[5\], \[10\], \[9\], \[4\]\]
**Output**
\[null, 4, 5, 5, 8, 8\]

**Explanation**
KthLargest kthLargest = new KthLargest(3, \[4, 5, 8, 2\]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

**Constraints:**

*   `1 <= k <= 104`
*   `0 <= nums.length <= 104`
*   `-104 <= nums[i] <= 104`
*   `-104 <= val <= 104`
*   At most `104` calls will be made to `add`.
*   It is guaranteed that there will be at least `k` elements in the array when you search for the `kth` element.
Binary Search

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

**Input:** nums = \[-1,0,3,5,9,12\], target = 9
**Output:** 4
**Explanation:** 9 exists in nums and its index is 4

**Example 2:**

**Input:** nums = \[-1,0,3,5,9,12\], target = 2
**Output:** -1
**Explanation:** 2 does not exist in nums so return -1

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-104 < nums[i], target < 104`
*   All the integers in `nums` are **unique**.
*   `nums` is sorted in ascending order.
Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement `MyHashSet` class:

*   `void add(key)` Inserts the value `key` into the HashSet.
*   `bool contains(key)` Returns whether the value `key` exists in the HashSet or not.
*   `void remove(key)` Removes the value `key` in the HashSet. If `key` does not exist in the HashSet, do nothing.

**Example 1:**

**Input**
\[ "MyHashSet ",  "add ",  "add ",  "contains ",  "contains ",  "add ",  "contains ",  "remove ",  "contains "\]
\[\[\], \[1\], \[2\], \[1\], \[3\], \[2\], \[2\], \[2\], \[2\]\]
**Output**
\[null, null, null, true, false, null, true, null, false\]

**Explanation**
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = \[1\]
myHashSet.add(2);      // set = \[1, 2\]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = \[1, 2\]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = \[1\]
myHashSet.contains(2); // return False, (already removed)

**Constraints:**

*   `0 <= key <= 106`
*   At most `104` calls will be made to `add`, `remove`, and `contains`.
Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the `MyHashMap` class:

*   `MyHashMap()` initializes the object with an empty map.
*   `void put(int key, int value)` inserts a `(key, value)` pair into the HashMap. If the `key` already exists in the map, update the corresponding `value`.
*   `int get(int key)` returns the `value` to which the specified `key` is mapped, or `-1` if this map contains no mapping for the `key`.
*   `void remove(key)` removes the `key` and its corresponding `value` if the map contains the mapping for the `key`.

**Example 1:**

**Input**
\[ "MyHashMap ",  "put ",  "put ",  "get ",  "get ",  "put ",  "get ",  "remove ",  "get "\]
\[\[\], \[1, 1\], \[2, 2\], \[1\], \[3\], \[2, 1\], \[2\], \[2\], \[2\]\]
**Output**
\[null, null, null, 1, -1, null, 1, null, -1\]

**Explanation**
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now \[\[1,1\]\]
myHashMap.put(2, 2); // The map is now \[\[1,1\], \[2,2\]\]
myHashMap.get(1);    // return 1, The map is now \[\[1,1\], \[2,2\]\]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now \[\[1,1\], \[2,2\]\]
myHashMap.put(2, 1); // The map is now \[\[1,1\], \[2,1\]\] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now \[\[1,1\], \[2,1\]\]
myHashMap.remove(2); // remove the mapping for 2, The map is now \[\[1,1\]\]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now \[\[1,1\]\]

**Constraints:**

*   `0 <= key, value <= 106`
*   At most `104` calls will be made to `put`, `get`, and `remove`.
Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.  
A node in a singly linked list should have two attributes: `val` and `next`. `val` is the value of the current node, and `next` is a pointer/reference to the next node.  
If you want to use the doubly linked list, you will need one more attribute `prev` to indicate the previous node in the linked list. Assume all nodes in the linked list are **0-indexed**.

Implement the `MyLinkedList` class:

*   `MyLinkedList()` Initializes the `MyLinkedList` object.
*   `int get(int index)` Get the value of the `indexth` node in the linked list. If the index is invalid, return `-1`.
*   `void addAtHead(int val)` Add a node of value `val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
*   `void addAtTail(int val)` Append a node of value `val` as the last element of the linked list.
*   `void addAtIndex(int index, int val)` Add a node of value `val` before the `indexth` node in the linked list. If `index` equals the length of the linked list, the node will be appended to the end of the linked list. If `index` is greater than the length, the node **will not be inserted**.
*   `void deleteAtIndex(int index)` Delete the `indexth` node in the linked list, if the index is valid.

**Example 1:**

**Input**
\[ "MyLinkedList ",  "addAtHead ",  "addAtTail ",  "addAtIndex ",  "get ",  "deleteAtIndex ",  "get "\]
\[\[\], \[1\], \[3\], \[1, 2\], \[1\], \[1\], \[1\]\]
**Output**
\[null, null, null, null, 2, null, 3\]

**Explanation**
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

**Constraints:**

*   `0 <= index, val <= 1000`
*   Please do not use the built-in LinkedList library.
*   At most `2000` calls will be made to `get`, `addAtHead`, `addAtTail`, `addAtIndex` and `deleteAtIndex`.
Insert into a Sorted Circular Linked List

Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value `insertVal` into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., the given node is `null`), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.

**Example 1:**

  

**Input:** head = \[3,4,1\], insertVal = 2
**Output:** \[3,4,1,2\]
**Explanation:** In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.

 

**Example 2:**

**Input:** head = \[\], insertVal = 1
**Output:** \[1\]
**Explanation:** The list is empty (given head is `null`). We create a new single circular list and return the reference to that single node.

**Example 3:**

**Input:** head = \[1\], insertVal = 0
**Output:** \[1,0\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 5 * 104]`.
*   `-106 <= Node.val, insertVal <= 106`
To Lower Case

Given a string `s`, return _the string after replacing every uppercase letter with the same lowercase letter_.

**Example 1:**

**Input:** s =  "Hello "
**Output:**  "hello "

**Example 2:**

**Input:** s =  "here "
**Output:**  "here "

**Example 3:**

**Input:** s =  "LOVELY "
**Output:**  "lovely "

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` consists of printable ASCII characters.
Random Pick with Blacklist

You are given an integer `n` and an array of **unique** integers `blacklist`. Design an algorithm to pick a random integer in the range `[0, n - 1]` that is **not** in `blacklist`. Any integer that is in the mentioned range and not in `blacklist` should be **equally likely** to be returned.

Optimize your algorithm such that it minimizes the number of calls to the **built-in** random function of your language.

Implement the `Solution` class:

*   `Solution(int n, int[] blacklist)` Initializes the object with the integer `n` and the blacklisted integers `blacklist`.
*   `int pick()` Returns a random integer in the range `[0, n - 1]` and not in `blacklist`.

**Example 1:**

**Input**
\[ "Solution ",  "pick ",  "pick ",  "pick ",  "pick ",  "pick ",  "pick ",  "pick "\]
\[\[7, \[2, 3, 5\]\], \[\], \[\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, 0, 4, 1, 6, 1, 0, 4\]

**Explanation**
Solution solution = new Solution(7, \[2, 3, 5\]);
solution.pick(); // return 0, any integer from \[0,1,4,6\] should be ok. Note that for every call of pick,
                 // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4).
solution.pick(); // return 4
solution.pick(); // return 1
solution.pick(); // return 6
solution.pick(); // return 1
solution.pick(); // return 0
solution.pick(); // return 4

**Constraints:**

*   `1 <= n <= 109`
*   `0 <= blacklist.length <= min(105, n - 1)`
*   `0 <= blacklist[i] < n`
*   All the values of `blacklist` are **unique**.
*   At most `2 * 104` calls will be made to `pick`.