bowang0911/leetcode huggingface dataset:
Contain Virus

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as an `m x n` binary grid `isInfected`, where `isInfected[i][j] == 0` represents uninfected cells, and `isInfected[i][j] == 1` represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two **4-directionally** adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region (i.e., the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night). There **will never be a tie**.

Return _the number of walls used to quarantine all the infected regions_. If the world will become fully infected, return the number of walls used.

**Example 1:**

**Input:** isInfected = \[\[0,1,0,0,0,0,0,1\],\[0,1,0,0,0,0,0,1\],\[0,0,0,0,0,0,0,1\],\[0,0,0,0,0,0,0,0\]\]
**Output:** 10
**Explanation:** There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:
 
On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.
 

**Example 2:**

**Input:** isInfected = \[\[1,1,1\],\[1,0,1\],\[1,1,1\]\]
**Output:** 4
**Explanation:** Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

**Example 3:**

**Input:** isInfected = \[\[1,1,1,0,0,0,0,0,0\],\[1,0,1,0,1,1,1,1,1\],\[1,1,1,0,0,0,0,0,0\]\]
**Output:** 13
**Explanation:** The region on the left only builds two new walls.

**Constraints:**

*   `m == isInfected.length`
*   `n == isInfected[i].length`
*   `1 <= m, n <= 50`
*   `isInfected[i][j]` is either `0` or `1`.
*   There is always a contiguous viral region throughout the described process that will **infect strictly more uncontaminated squares** in the next round.
Number Of Corner Rectangles

Given an `m x n` integer matrix `grid` where each entry is only `0` or `1`, return _the number of **corner rectangles**_.

A **corner rectangle** is four distinct `1`'s on the grid that forms an axis-aligned rectangle. Note that only the corners need to have the value `1`. Also, all four `1`'s used must be distinct.

**Example 1:**

**Input:** grid = \[\[1,0,0,1,0\],\[0,0,1,0,1\],\[0,0,0,1,0\],\[1,0,1,0,1\]\]
**Output:** 1
**Explanation:** There is only one corner rectangle, with corners grid\[1\]\[2\], grid\[1\]\[4\], grid\[3\]\[2\], grid\[3\]\[4\].

**Example 2:**

**Input:** grid = \[\[1,1,1\],\[1,1,1\],\[1,1,1\]\]
**Output:** 9
**Explanation:** There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

**Example 3:**

**Input:** grid = \[\[1,1,1,1\]\]
**Output:** 0
**Explanation:** Rectangles must have four distinct corners.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 200`
*   `grid[i][j]` is either `0` or `1`.
*   The number of `1`'s in the grid is in the range `[1, 6000]`.
IP to CIDR

An **IP address** is a formatted 32-bit unsigned integer where each group of 8 bits is printed as a decimal number and the dot character `'.'` splits the groups.

*   For example, the binary number `00001111 10001000 11111111 01101011` (spaces added for clarity) formatted as an IP address would be `"15.136.255.107 "`.

A **CIDR block** is a format used to denote a specific set of IP addresses. It is a string consisting of a base IP address, followed by a slash, followed by a prefix length `k`. The addresses it covers are all the IPs whose **first `k` bits** are the same as the base IP address.

*   For example, `"123.45.67.89/20 "` is a CIDR block with a prefix length of `20`. Any IP address whose binary representation matches `01111011 00101101 0100xxxx xxxxxxxx`, where `x` can be either `0` or `1`, is in the set covered by the CIDR block.

You are given a start IP address `ip` and the number of IP addresses we need to cover `n`. Your goal is to use **as few CIDR blocks as possible** to cover all the IP addresses in the **inclusive** range `[ip, ip + n - 1]` **exactly**. No other IP addresses outside of the range should be covered.

Return _the **shortest** list of **CIDR blocks** that covers the range of IP addresses. If there are multiple answers, return **any** of them_.

**Example 1:**

**Input:** ip =  "255.0.0.7 ", n = 10
**Output:** \[ "255.0.0.7/32 ", "255.0.0.8/29 ", "255.0.0.16/32 "\]
**Explanation:**
The IP addresses that need to be covered are:
- 255.0.0.7  -> 11111111 00000000 00000000 00000111
- 255.0.0.8  -> 11111111 00000000 00000000 00001000
- 255.0.0.9  -> 11111111 00000000 00000000 00001001
- 255.0.0.10 -> 11111111 00000000 00000000 00001010
- 255.0.0.11 -> 11111111 00000000 00000000 00001011
- 255.0.0.12 -> 11111111 00000000 00000000 00001100
- 255.0.0.13 -> 11111111 00000000 00000000 00001101
- 255.0.0.14 -> 11111111 00000000 00000000 00001110
- 255.0.0.15 -> 11111111 00000000 00000000 00001111
- 255.0.0.16 -> 11111111 00000000 00000000 00010000
The CIDR block  "255.0.0.7/32 " covers the first address.
The CIDR block  "255.0.0.8/29 " covers the middle 8 addresses (binary format of 11111111 00000000 00000000 00001xxx).
The CIDR block  "255.0.0.16/32 " covers the last address.
Note that while the CIDR block  "255.0.0.0/28 " does cover all the addresses, it also includes addresses outside of the range, so we cannot use it.

**Example 2:**

**Input:** ip =  "117.145.102.62 ", n = 8
**Output:** \[ "117.145.102.62/31 ", "117.145.102.64/30 ", "117.145.102.68/31 "\]

**Constraints:**

*   `7 <= ip.length <= 15`
*   `ip` is a valid **IPv4** on the form `"a.b.c.d "` where `a`, `b`, `c`, and `d` are integers in the range `[0, 255]`.
*   `1 <= n <= 1000`
*   Every implied address `ip + x` (for `x < n`) will be a valid IPv4 address.
Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: `'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn `'9'` to be `'0'`, or `'0'` to be `'9'`. Each move consists of turning one wheel one slot.

The lock initially starts at `'0000'`, a string representing the state of the 4 wheels.

You are given a list of `deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a `target` representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

**Example 1:**

**Input:** deadends = \[ "0201 ", "0101 ", "0102 ", "1212 ", "2002 "\], target =  "0202 "
**Output:** 6
**Explanation:** 
A sequence of valid moves would be  "0000 " ->  "1000 " ->  "1100 " ->  "1200 " ->  "1201 " ->  "1202 " ->  "0202 ".
Note that a sequence like  "0000 " ->  "0001 " ->  "0002 " ->  "0102 " ->  "0202 " would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end  "0102 ".

**Example 2:**

**Input:** deadends = \[ "8888 "\], target =  "0009 "
**Output:** 1
**Explanation:** We can turn the last wheel in reverse to move from  "0000 " ->  "0009 ".

**Example 3:**

**Input:** deadends = \[ "8887 ", "8889 ", "8878 ", "8898 ", "8788 ", "8988 ", "7888 ", "9888 "\], target =  "8888 "
**Output:** -1
**Explanation:** We cannot reach the target without getting stuck.

**Constraints:**

*   `1 <= deadends.length <= 500`
*   `deadends[i].length == 4`
*   `target.length == 4`
*   target **will not be** in the list `deadends`.
*   `target` and `deadends[i]` consist of digits only.
Cracking the Safe

There is a safe protected by a password. The password is a sequence of `n` digits where each digit can be in the range `[0, k - 1]`.

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the **most recent** `n` **digits** that were entered each time you type a digit.

*   For example, the correct password is `"345 "` and you enter in `"012345 "`:
    *   After typing `0`, the most recent `3` digits is `"0 "`, which is incorrect.
    *   After typing `1`, the most recent `3` digits is `"01 "`, which is incorrect.
    *   After typing `2`, the most recent `3` digits is `"012 "`, which is incorrect.
    *   After typing `3`, the most recent `3` digits is `"123 "`, which is incorrect.
    *   After typing `4`, the most recent `3` digits is `"234 "`, which is incorrect.
    *   After typing `5`, the most recent `3` digits is `"345 "`, which is correct and the safe unlocks.

Return _any string of **minimum length** that will unlock the safe **at some point** of entering it_.

**Example 1:**

**Input:** n = 1, k = 2
**Output:**  "10 "
**Explanation:** The password is a single digit, so enter each digit.  "01 " would also unlock the safe.

**Example 2:**

**Input:** n = 2, k = 2
**Output:**  "01100 "
**Explanation:** For each possible password:
-  "00 " is typed in starting from the 4th digit.
-  "01 " is typed in starting from the 1st digit.
-  "10 " is typed in starting from the 3rd digit.
-  "11 " is typed in starting from the 2nd digit.
Thus  "01100 " will unlock the safe.  "10011 ", and  "11001 " would also unlock the safe.

**Constraints:**

*   `1 <= n <= 4`
*   `1 <= k <= 10`
*   `1 <= kn <= 4096`
Reach a Number

You are standing at position `0` on an infinite number line. There is a destination at position `target`.

You can make some number of moves `numMoves` so that:

*   On each move, you can either go left or right.
*   During the `ith` move (starting from `i == 1` to `i == numMoves`), you take `i` steps in the chosen direction.

Given the integer `target`, return _the **minimum** number of moves required (i.e., the minimum_ `numMoves`_) to reach the destination_.

**Example 1:**

**Input:** target = 2
**Output:** 3
**Explanation:**
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).

**Example 2:**

**Input:** target = 3
**Output:** 2
**Explanation:**
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).

**Constraints:**

*   `-109 <= target <= 109`
*   `target != 0`
Pour Water

You are given an elevation map represents as an integer array `heights` where `heights[i]` representing the height of the terrain at index `i`. The width at each index is `1`. You are also given two integers `volume` and `k`. `volume` units of water will fall at index `k`.

Water first drops at the index `k` and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

*   If the droplet would eventually fall by moving left, then move left.
*   Otherwise, if the droplet would eventually fall by moving right, then move right.
*   Otherwise, rise to its current position.

Here, **"eventually fall "** means that the droplet will eventually be at a lower level if it moves in that direction. Also, level means the height of the terrain plus any water in that column.

We can assume there is infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than one grid block, and each unit of water has to be in exactly one block.

**Example 1:**

**Input:** heights = \[2,1,1,2,1,2,2\], volume = 4, k = 3
**Output:** \[2,2,2,3,2,2,2\]
**Explanation:**
The first drop of water lands at index k = 3. When moving left or right, the water can only move to the same level or a lower level. (By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left. (A droplet  "made to fall " means go to a lower height than it was at previously.) Since moving left will not make it fall, it stays in place.
 
The next droplet falls at index k = 3. Since the new droplet moving left will eventually make it fall, it moves left. Notice that the droplet still preferred to move left, even though it could move right (and moving right makes it fall quicker.)
 
The third droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would eventually make it fall, it moves right.
 
Finally, the fourth droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would not eventually make it fall, it stays in place.
 

**Example 2:**

**Input:** heights = \[1,2,3,4\], volume = 2, k = 2
**Output:** \[2,3,3,4\]
**Explanation:** The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.

**Example 3:**

**Input:** heights = \[3,1,3\], volume = 5, k = 1
**Output:** \[4,4,4\]

**Constraints:**

*   `1 <= heights.length <= 100`
*   `0 <= heights[i] <= 99`
*   `0 <= volume <= 2000`
*   `0 <= k < heights.length`
Pyramid Transition Matrix

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains **one less block** than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific **triangular patterns** that are allowed. A triangular pattern consists of a **single block** stacked on top of **two blocks**. The patterns are given as a list of three-letter strings `allowed`, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

*   For example, `"ABC "` represents a triangular pattern with a `'C'` block stacked on top of an `'A'` (left) and `'B'` (right) block. Note that this is different from `"BAC "` where `'B'` is on the left bottom and `'A'` is on the right bottom.

You start with a bottom row of blocks `bottom`, given as a single string, that you **must** use as the base of the pyramid.

Given `bottom` and `allowed`, return `true` _if you can build the pyramid all the way to the top such that **every triangular pattern** in the pyramid is in_ `allowed`_, or_ `false` _otherwise_.

**Example 1:**

**Input:** bottom =  "BCD ", allowed = \[ "BCC ", "CDE ", "CEA ", "FFF "\]
**Output:** true
**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build  "CE " on level 2 and then build  "A " on level 1.
There are three triangular patterns in the pyramid, which are  "BCC ",  "CDE ", and  "CEA ". All are allowed.

**Example 2:**

**Input:** bottom =  "AAAA ", allowed = \[ "AAB ", "AAC ", "BCD ", "BBE ", "DEF "\]
**Output:** false
**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

**Constraints:**

*   `2 <= bottom.length <= 6`
*   `0 <= allowed.length <= 216`
*   `allowed[i].length == 3`
*   The letters in all input strings are from the set `{'A', 'B', 'C', 'D', 'E', 'F'}`.
*   All the values of `allowed` are **unique**.
Set Intersection Size At Least Two

You are given a 2D integer array `intervals` where `intervals[i] = [starti, endi]` represents all the integers from `starti` to `endi` inclusively.

A **containing set** is an array `nums` where each interval from `intervals` has **at least two** integers in `nums`.

*   For example, if `intervals = [[1,3], [3,7], [8,9]]`, then `[1,2,4,7,8,9]` and `[2,3,4,8,9]` are **containing sets**.

Return _the minimum possible size of a containing set_.

**Example 1:**

**Input:** intervals = \[\[1,3\],\[3,7\],\[8,9\]\]
**Output:** 5
**Explanation:** let nums = \[2, 3, 4, 8, 9\].
It can be shown that there cannot be any containing array of size 4.

**Example 2:**

**Input:** intervals = \[\[1,3\],\[1,4\],\[2,5\],\[3,5\]\]
**Output:** 3
**Explanation:** let nums = \[2, 3, 4\].
It can be shown that there cannot be any containing array of size 2.

**Example 3:**

**Input:** intervals = \[\[1,2\],\[2,3\],\[2,4\],\[4,5\]\]
**Output:** 5
**Explanation:** let nums = \[1, 2, 3, 4, 5\].
It can be shown that there cannot be any containing array of size 4.

**Constraints:**

*   `1 <= intervals.length <= 3000`
*   `intervals[i].length == 2`
*   `0 <= starti < endi <= 108`
Bold Words in String

Given an array of keywords `words` and a string `s`, make all appearances of all keywords `words[i]` in `s` bold. Any letters between **and** tags become bold.

Return `s` _after adding the bold tags_. The returned string should use the least number of tags possible, and the tags should form a valid combination.

**Example 1:**

**Input:** words = \[ "ab ", "bc "\], s =  "aabcd "
**Output:**  "a**abc**d "
**Explanation:** Note that returning ` "a**a**b**c**d "` would use more tags, so it is incorrect.

**Example 2:**

**Input:** words = \[ "ab ", "cb "\], s =  "aabcd "
**Output:**  "a**ab**cd "

**Constraints:**

*   `1 <= s.length <= 500`
*   `0 <= words.length <= 50`
*   `1 <= words[i].length <= 10`
*   `s` and `words[i]` consist of lowercase English letters.

**Note:** This question is the same as 616: [https://leetcode.com/problems/add-bold-tag-in-string/](https://leetcode.com/problems/add-bold-tag-in-string/)
Employee Free Time

We are given a list `schedule` of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping `Intervals`, and these intervals are in sorted order.

Return the list of finite intervals representing **common, positive-length free time** for _all_ employees, also in sorted order.

(Even though we are representing `Intervals` in the form `[x, y]`, the objects inside are `Intervals`, not lists or arrays. For example, `schedule[0][0].start = 1`, `schedule[0][0].end = 2`, and `schedule[0][0][0]` is not defined). Also, we wouldn't include intervals like \[5, 5\] in our answer, as they have zero length.

**Example 1:**

**Input:** schedule = \[\[\[1,2\],\[5,6\]\],\[\[1,3\]\],\[\[4,10\]\]\]
**Output:** \[\[3,4\]\]
**Explanation:** There are a total of three employees, and all common
free time intervals would be \[-inf, 1\], \[3, 4\], \[10, inf\].
We discard any intervals that contain inf as they aren't finite.

**Example 2:**

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

**Constraints:**

*   `1 <= schedule.length , schedule[i].length <= 50`
*   `0 <= schedule[i].start < schedule[i].end <= 10^8`
Find Anagram Mappings

You are given two integer arrays `nums1` and `nums2` where `nums2` is **an anagram** of `nums1`. Both arrays may contain duplicates.

Return _an index mapping array_ `mapping` _from_ `nums1` _to_ `nums2` _where_ `mapping[i] = j` _means the_ `ith` _element in_ `nums1` _appears in_ `nums2` _at index_ `j`. If there are multiple answers, return **any of them**.

An array `a` is **an anagram** of an array `b` means `b` is made by randomizing the order of the elements in `a`.

**Example 1:**

**Input:** nums1 = \[12,28,46,32,50\], nums2 = \[50,12,32,46,28\]
**Output:** \[1,4,3,2,0\]
**Explanation:** As mapping\[0\] = 1 because the 0th element of nums1 appears at nums2\[1\], and mapping\[1\] = 4 because the 1st element of nums1 appears at nums2\[4\], and so on.

**Example 2:**

**Input:** nums1 = \[84,46\], nums2 = \[84,46\]
**Output:** \[0,1\]

**Constraints:**

*   `1 <= nums1.length <= 100`
*   `nums2.length == nums1.length`
*   `0 <= nums1[i], nums2[i] <= 105`
*   `nums2` is an anagram of `nums1`.
Special Binary String

**Special binary strings** are binary strings with the following two properties:

*   The number of `0`'s is equal to the number of `1`'s.
*   Every prefix of the binary string has at least as many `1`'s as `0`'s.

You are given a **special binary** string `s`.

A move consists of choosing two consecutive, non-empty, special substrings of `s`, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return _the lexicographically largest resulting string possible after applying the mentioned operations on the string_.

**Example 1:**

**Input:** s =  "11011000 "
**Output:**  "11100100 "
**Explanation:** The strings  "10 " \[occuring at s\[1\]\] and  "1100 " \[at s\[3\]\] are swapped.
This is the lexicographically largest string possible after some number of swaps.

**Example 2:**

**Input:** s =  "10 "
**Output:**  "10 "

**Constraints:**

*   `1 <= s.length <= 50`
*   `s[i]` is either `'0'` or `'1'`.
*   `s` is a special binary string.
Prime Number of Set Bits in Binary Representation

Given two integers `left` and `right`, return _the **count** of numbers in the **inclusive** range_ `[left, right]` _having a **prime number of set bits** in their binary representation_.

Recall that the **number of set bits** an integer has is the number of `1`'s present when written in binary.

*   For example, `21` written in binary is `10101`, which has `3` set bits.

**Example 1:**

**Input:** left = 6, right = 10
**Output:** 4
**Explanation:**
6  -> 110 (2 set bits, 2 is prime)
7  -> 111 (3 set bits, 3 is prime)
8  -> 1000 (1 set bit, 1 is not prime)
9  -> 1001 (2 set bits, 2 is prime)
10 -> 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.

**Example 2:**

**Input:** left = 10, right = 15
**Output:** 5
**Explanation:**
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
5 numbers have a prime number of set bits.

**Constraints:**

*   `1 <= left <= right <= 106`
*   `0 <= right - left <= 104`
Partition Labels

You are given a string `s`. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be `s`.

Return _a list of integers representing the size of these parts_.

**Example 1:**

**Input:** s =  "ababcbacadefegdehijhklij "
**Output:** \[9,7,8\]
**Explanation:**
The partition is  "ababcbaca ",  "defegde ",  "hijhklij ".
This is a partition so that each letter appears in at most one part.
A partition like  "ababcbacadefegde ",  "hijhklij " is incorrect, because it splits s into less parts.

**Example 2:**

**Input:** s =  "eccbbbbdec "
**Output:** \[10\]

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of lowercase English letters.
Largest Plus Sign

You are given an integer `n`. You have an `n x n` binary grid `grid` with all values initially `1`'s except for some indices given in the array `mines`. The `ith` element of the array `mines` is defined as `mines[i] = [xi, yi]` where `grid[xi][yi] == 0`.

Return _the order of the largest **axis-aligned** plus sign of_ 1_'s contained in_ `grid`. If there is none, return `0`.

An **axis-aligned plus sign** of `1`'s of order `k` has some center `grid[r][c] == 1` along with four arms of length `k - 1` going up, down, left, and right, and made of `1`'s. Note that there could be `0`'s or `1`'s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for `1`'s.

**Example 1:**

**Input:** n = 5, mines = \[\[4,2\]\]
**Output:** 2
**Explanation:** In the above grid, the largest plus sign can only be of order 2. One of them is shown.

**Example 2:**

**Input:** n = 1, mines = \[\[0,0\]\]
**Output:** 0
**Explanation:** There is no plus sign, so return 0.

**Constraints:**

*   `1 <= n <= 500`
*   `1 <= mines.length <= 5000`
*   `0 <= xi, yi < n`
*   All the pairs `(xi, yi)` are **unique**.