2024-11-04
3163. String Compression III

Topic: String
Difficulty: Medium

Problem:
Given a string word, compress it using the following algorithm:

• Begin with an empty string comp. While word is not empty, use the following operation:
• Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
• Append the length of the prefix followed by c to comp.

Return the string comp.

Example 1:

Input: word = "abcde"

Output: "1a1b1c1d1e"

Explanation:

Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.

For each prefix, append "1" followed by the character to comp.

Example 2:

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Explanation:

Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.

• For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
• For prefix "aaaaa", append "5" followed by "a" to comp.
• For prefix "bb", append "2" followed by "b" to comp.

Constraints:

• 1 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.

2024-11-05
2914. Minimum Number of Changes to Make Binary String Beautiful

Topic: String
Difficulty: Medium

Problem:
You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

• Each substring has an even length.
• Each substring contains only 1's or only 0's.

You can change any character in s to 0 or 1.

Return the minimum number of changes required to make the string s beautiful.

Example 1:

Input: s = "1001"
Output: 2
Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100".
It can be seen that the string "1100" is beautiful because we can partition it into "11|00".
It can be proven that 2 is the minimum number of changes needed to make the string beautiful.

Example 2:

Input: s = "10"
Output: 1
Explanation: We change s[1] to 1 to get string "11".
It can be seen that the string "11" is beautiful because we can partition it into "11".
It can be proven that 1 is the minimum number of changes needed to make the string beautiful.

Example 3:

Input: s = "0000"
Output: 0
Explanation: We don't need to make any changes as the string "0000" is beautiful already.

Constraints:

• 2 <= s.length <= 10^5
• s has an even length.
• s[i] is either '0' or '1'.

2024-11-06
3011. Find if Array Can Be Sorted

Topic: Array, Bit Manipulation, Sorting
Difficulty: Medium

Problem:
You are given a 0-indexed array of positive integers nums.

In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero).

Return true if you can sort the array, else return false.

Example 1:

Input: nums = [8,4,2,30,15]
Output: true
Explanation: Let's look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation "10", "100", and "1000" respectively. The numbers 15 and 30 have four set bits each with binary representation "1111" and "11110".
We can sort the array using 4 operations:
- Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
- Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
- Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
- Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30].
The array has become sorted, hence we return true.
Note that there may be other sequences of operations which also sort the array.

Example 2:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: The array is already sorted, hence we return true.

Example 3:

Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 2^8

2024-11-07
2275. Largest Combination With Bitwise AND Greater Than Zero

Topic: Array, Hash Table, Bit Manipulation, Counting
Difficulty: Medium

Problem:
The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2:

Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

Constraints:

• 1 <= candidates.length <= 10^5
• 1 <= candidates[i] <= 10^7

2024-11-08
1829. Maximum XOR for Each Query

Topic: Array, Bit Manipulation, Prefix Sum
Difficulty: Medium

Problem:
You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

1. Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
2. Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

• nums.length == n
• 1 <= n <= 10^5
• 1 <= maximumBit <= 20
• 0 <= nums[i] < 2^maximumBit
• nums​​​ is sorted in ascending order.

2024-11-09
3133. Minimum Array End

Topic: Bit Manipulation
Difficulty: Medium

Problem:
You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.

Return the minimum possible value of nums[n - 1].

Example 1:

Input: n = 3, x = 4

Output: 6

Explanation:

nums can be [4,5,6] and its last element is 6.

Example 2:

Input: n = 2, x = 7

Output: 15

Explanation:

nums can be [7,15] and its last element is 15.

Constraints:

• 1 <= n, x <= 10^8

2024-11-10
3097. Shortest Subarray With OR at Least K II

Topic: Array, Bit Manipulation, Sliding Window
Difficulty: Medium

Problem:
You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Example 1:

Input: nums = 1,2,3, k = 2

Output: 1

Explanation:

The subarray [3] has OR value of 3. Hence, we return 1.

Example 2:

Input: nums = 2,1,8, k = 10

Output: 3

Explanation:

The subarray [2,1,8] has OR value of 11. Hence, we return 3.

Example 3:

Input: nums = 1,2, k = 0

Output: 1

Explanation:

The subarray [1] has OR value of 1. Hence, we return 1.

Constraints:

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

2024-11-11
2601. Prime Subtraction Operation

Topic: Array, Math, Binary Search, Greedy, Number Theory
Difficulty: Medium

Problem:
You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

• Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].

Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

Example 1:

Input: nums = [4,9,6,10]
Output: true
Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

Example 2:

Input: nums = [6,8,11,12]
Output: true
Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

Example 3:

Input: nums = [5,8,3]
Output: false
Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

2024-11-12
2070. Most Beautiful Item for Each Query

Topic: Array, Binary Search, Sorting
Difficulty: Medium

Problem:
You are given a 2D integer array items where items[i] = [price_i, beauty_i] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the j^th query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

Constraints:

• 1 <= items.length, queries.length <= 10^5
• items[i].length == 2
• 1 <= price_i, beauty_i, queries[j] <= 10^9

2024-11-13
2563. Count the Number of Fair Pairs

Topic: Array, Two Pointers, Binary Search, Sorting
Difficulty: Medium

Problem:
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

• 0 <= i < j < n, and
• lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

Constraints:

• 1 <= nums.length <= 10^5
• nums.length == n
• -10^9 <= nums[i] <= 10^9
• -10^9 <= lower <= upper <= 10^9

2024-11-14
2064. Minimized Maximum of Products Distributed to Any Store

Topic: Array, Binary Search
Difficulty: Medium

Problem:
You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the i^th product type.

You need to distribute all products to the retail stores following these rules:

• A store can only be given at most one product type but can be given any amount of it.
• After distribution, each store will have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

Example 1:

Input: n = 6, quantities = [11,6]
Output: 3
Explanation: One optimal way is:
- The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
- The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3
The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2:

Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: One optimal way is:
- The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
- The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
- The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5
The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3:

Input: n = 1, quantities = [100000]
Output: 100000
Explanation: The only optimal way is:
- The 100000 products of type 0 are distributed to the only store.
The maximum number of products given to any store is max(100000) = 100000.

Constraints:

• m == quantities.length
• 1 <= m <= n <= 10^5
• 1 <= quantities[i] <= 10^5

2024-11-15
1574. Shortest Subarray to be Removed to Make Array Sorted

Topic: Array, Two Pointers, Binary Search, Stack, Monotonic Stack
Difficulty: Medium

Problem:
Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Constraints:

• 1 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^9

2024-11-16
3254. Find the Power of K-Size Subarrays I

Topic: Array, Sliding Window
Difficulty: Medium

Problem:
You are given an array of integers nums of length n and a positive integer k.

The power of an array is defined as:

• Its maximum element if all of its elements are consecutive and sorted in ascending order.
• -1 otherwise.

You need to find the power of all subarrays of nums of size k.

Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].

Example 1:

Input: nums = 1,2,3,4,3,2,5, k = 3

Output: 3,4,-1,-1,-1

Explanation:

There are 5 subarrays of nums of size 3:

• [1, 2, 3] with the maximum element 3.
• [2, 3, 4] with the maximum element 4.
• [3, 4, 3] whose elements are not consecutive.
• [4, 3, 2] whose elements are not sorted.
• [3, 2, 5] whose elements are not consecutive.

Example 2:

Input: nums = 2,2,2,2,2, k = 4

Output: -1,-1

Example 3:

Input: nums = 3,2,3,2,3,2, k = 2

Output: -1,3,-1,3,-1

Constraints:

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10^5
• 1 <= k <= n

2024-11-17
862. Shortest Subarray with Sum at Least K

Topic: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue
Difficulty: Hard

Problem:
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9

2024-11-18
1652. Defuse the Bomb

Topic: Array, Sliding Window
Difficulty: Easy

Problem:
You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

• If k > 0, replace the i^th number with the sum of the next k numbers.
• If k < 0, replace the i^th number with the sum of the previous k numbers.
• If k == 0, replace the i^th number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.

Constraints:

• n == code.length
• 1 <= n <= 100
• 1 <= code[i] <= 100
• -(n - 1) <= k <= n - 1

2024-11-19
2461. Maximum Sum of Distinct Subarrays With Length K

Topic: Array, Hash Table, Sliding Window
Difficulty: Medium

Problem:
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

• The length of the subarray is k, and
• All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

2024-11-20
2516. Take K of Each Character From Left and Right

Topic: Hash Table, String, Sliding Window
Difficulty: Medium

Problem:
You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: 
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only the letters 'a', 'b', and 'c'.
• 0 <= k <= s.length

2024-11-21
2257. Count Unguarded Cells in the Grid

Topic: Array, Matrix, Simulation
Difficulty: Medium

Problem:
You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/03/10/example1drawio2.png

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/03/10/example2drawio.png

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

Constraints:

• 1 <= m, n <= 10^5
• 2 <= m * n <= 10^5
• 1 <= guards.length, walls.length <= 5 * 10^4
• 2 <= guards.length + walls.length <= m * n
• guards[i].length == walls[j].length == 2
• 0 <= row_i, row_j < m
• 0 <= col_i, col_j < n
• All the positions in guards and walls are unique.

2024-11-22
1072. Flip Columns For Maximum Number of Equal Rows

Topic: Array, Hash Table, Matrix
Difficulty: Medium

Problem:
You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

2024-11-23
1861. Rotating the Box

Topic: Array, Two Pointers, Matrix
Difficulty: Medium

Problem:
You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:

• A stone '#'
• A stationary obstacle '*'
• Empty '.'

The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.

It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the box.

Return an n x m matrix representing the box after the rotation described above.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcodewithstones.png

Input: box = [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]]

Example 2:

Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode2withstones.png

Input: box = [["#",".","*","."],
              ["#","#","*","."]]
Output: [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]

Example 3:

Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode3withstone.png

Input: box = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
Output: [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]

Constraints:

• m == box.length
• n == box[i].length
• 1 <= m, n <= 500
• box[i][j] is either '#', '*', or '.'.