bowang0911/leetcode huggingface dataset:
Sliding Window Median

The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

*   For examples, if `arr = [2,3,4]`, the median is `3`.
*   For examples, if `arr = [1,2,3,4]`, the median is `(2 + 3) / 2 = 2.5`.

You are given an integer array `nums` and an integer `k`. There is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position.

Return _the median array for each window in the original array_. Answers within `10-5` of the actual value will be accepted.

**Example 1:**

**Input:** nums = \[1,3,-1,-3,5,3,6,7\], k = 3
**Output:** \[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000\]
**Explanation:** 
Window position                Median
---------------                -----
\[**1  3  -1**\] -3  5  3  6  7        1
 1 \[**3  -1  -3**\] 5  3  6  7       -1
 1  3 \[**\-1  -3  5**\] 3  6  7       -1
 1  3  -1 \[**\-3  5  3**\] 6  7        3
 1  3  -1  -3 \[**5  3  6**\] 7        5
 1  3  -1  -3  5 \[**3  6  7**\]       6

**Example 2:**

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

**Constraints:**

*   `1 <= k <= nums.length <= 105`
*   `-231 <= nums[i] <= 231 - 1`
Magical String

A magical string `s` consists of only `'1'` and `'2'` and obeys the following rules:

*   The string s is magical because concatenating the number of contiguous occurrences of characters `'1'` and `'2'` generates the string `s` itself.

The first few elements of `s` is `s = "1221121221221121122...... "`. If we group the consecutive `1`'s and `2`'s in `s`, it will be `"1 22 11 2 1 22 1 22 11 2 11 22 ...... "` and the occurrences of `1`'s or `2`'s in each group are `"1 2 2 1 1 2 1 2 2 1 2 2 ...... "`. You can see that the occurrence sequence is `s` itself.

Given an integer `n`, return the number of `1`'s in the first `n` number in the magical string `s`.

**Example 1:**

**Input:** n = 6
**Output:** 3
**Explanation:** The first 6 elements of magical string s is  "122112 " and it contains three 1's, so return 3.

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 105`
License Key Formatting

You are given a license key represented as a string `s` that consists of only alphanumeric characters and dashes. The string is separated into `n + 1` groups by `n` dashes. You are also given an integer `k`.

We want to reformat the string `s` such that each group contains exactly `k` characters, except for the first group, which could be shorter than `k` but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.

Return _the reformatted license key_.

**Example 1:**

**Input:** s =  "5F3Z-2e-9-w ", k = 4
**Output:**  "5F3Z-2E9W "
**Explanation:** The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

**Example 2:**

**Input:** s =  "2-5g-3-J ", k = 2
**Output:**  "2-5G-3J "
**Explanation:** The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of English letters, digits, and dashes `'-'`.
*   `1 <= k <= 104`
Smallest Good Base

Given an integer `n` represented as a string, return _the smallest **good base** of_ `n`.

We call `k >= 2` a **good base** of `n`, if all digits of `n` base `k` are `1`'s.

**Example 1:**

**Input:** n =  "13 "
**Output:**  "3 "
**Explanation:** 13 base 3 is 111.

**Example 2:**

**Input:** n =  "4681 "
**Output:**  "8 "
**Explanation:** 4681 base 8 is 11111.

**Example 3:**

**Input:** n =  "1000000000000000000 "
**Output:**  "999999999999999999 "
**Explanation:** 1000000000000000000 base 999999999999999999 is 11.

**Constraints:**

*   `n` is an integer in the range `[3, 1018]`.
*   `n` does not contain any leading zeros.
Find Permutation

A permutation `perm` of `n` integers of all the integers in the range `[1, n]` can be represented as a string `s` of length `n - 1` where:

*   `s[i] == 'I'` if `perm[i] < perm[i + 1]`, and
*   `s[i] == 'D'` if `perm[i] > perm[i + 1]`.

Given a string `s`, reconstruct the lexicographically smallest permutation `perm` and return it.

**Example 1:**

**Input:** s =  "I "
**Output:** \[1,2\]
**Explanation:** \[1,2\] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

**Example 2:**

**Input:** s =  "DI "
**Output:** \[2,1,3\]
**Explanation:** Both \[2,1,3\] and \[3,1,2\] can be represented as  "DI ", but since we want to find the smallest lexicographical permutation, you should return \[2,1,3\]

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is either `'I'` or `'D'`.
Max Consecutive Ones

Given a binary array `nums`, return _the maximum number of consecutive_ `1`_'s in the array_.

**Example 1:**

**Input:** nums = \[1,1,0,1,1,1\]
**Output:** 3
**Explanation:** The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 105`
*   `nums[i]` is either `0` or `1`.
Predict the Winner

You are given an integer array `nums`. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of `0`. At each turn, the player takes one of the numbers from either end of the array (i.e., `nums[0]` or `nums[nums.length - 1]`) which reduces the size of the array by `1`. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return `true` if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return `true`. You may assume that both players are playing optimally.

**Example 1:**

**Input:** nums = \[1,5,2\]
**Output:** false
**Explanation:** Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

**Example 2:**

**Input:** nums = \[1,5,233,7\]
**Output:** true
**Explanation:** Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

**Constraints:**

*   `1 <= nums.length <= 20`
*   `0 <= nums[i] <= 107`
Max Consecutive Ones II

Given a binary array `nums`, return _the maximum number of consecutive_ `1`_'s in the array if you can flip at most one_ `0`.

**Example 1:**

**Input:** nums = \[1,0,1,1,0\]
**Output:** 4
**Explanation:** 
- If we flip the first zero, nums becomes \[1,1,1,1,0\] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes \[1,0,1,1,1\] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

**Example 2:**

**Input:** nums = \[1,0,1,1,0,1\]
**Output:** 4
**Explanation:** 
- If we flip the first zero, nums becomes \[1,1,1,1,0,1\] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes \[1,0,1,1,1,1\] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `nums[i]` is either `0` or `1`.

**Follow up:** What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Zuma Game

You are playing a variation of the game Zuma.

In this variation of Zuma, there is a **single row** of colored balls on a board, where each ball can be colored red `'R'`, yellow `'Y'`, blue `'B'`, green `'G'`, or white `'W'`. You also have several colored balls in your hand.

Your goal is to **clear all** of the balls from the board. On each turn:

*   Pick **any** ball from your hand and insert it in between two balls in the row or on either end of the row.
*   If there is a group of **three or more consecutive balls** of the **same color**, remove the group of balls from the board.
    *   If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.
*   If there are no more balls on the board, then you win the game.
*   Repeat this process until you either win or do not have any more balls in your hand.

Given a string `board`, representing the row of balls on the board, and a string `hand`, representing the balls in your hand, return _the **minimum** number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return_ `-1`.

**Example 1:**

**Input:** board =  "WRRBBW ", hand =  "RB "
**Output:** -1
**Explanation:** It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the board becomes WRRRBBW. WRRRBBW -> WBBW.
- Insert 'B' so the board becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the board, and you are out of balls to insert.

**Example 2:**

**Input:** board =  "WWRRBBWW ", hand =  "WRBRW "
**Output:** 2
**Explanation:** To make the board empty:
- Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW.
- Insert 'B' so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty.
2 balls from your hand were needed to clear the board.

**Example 3:**

**Input:** board =  "G ", hand =  "GGGGG "
**Output:** 2
**Explanation:** To make the board empty:
- Insert 'G' so the board becomes GG.
- Insert 'G' so the board becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the board.

**Constraints:**

*   `1 <= board.length <= 16`
*   `1 <= hand.length <= 5`
*   `board` and `hand` consist of the characters `'R'`, `'Y'`, `'B'`, `'G'`, and `'W'`.
*   The initial row of balls on the board will **not** have any groups of three or more consecutive balls of the same color.
Robot Room Cleaner

You are controlling a robot that is located somewhere in a room. The room is modeled as an `m x n` binary grid where `0` represents a wall and `1` represents an empty slot.

The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API `Robot`.

You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is `90` degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.

Design an algorithm to clean the entire room using the following APIs:

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

**Note** that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.

**Custom testing:**

The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded ". In other words, you must control the robot using only the four mentioned APIs without knowing the room layout and the initial robot's position.

**Example 1:**

**Input:** room = \[\[1,1,1,1,1,0,1,1\],\[1,1,1,1,1,0,1,1\],\[1,0,1,1,1,1,1,1\],\[0,0,0,1,0,0,0,0\],\[1,1,1,1,1,1,1,1\]\], row = 1, col = 3
**Output:** Robot cleaned all rooms.
**Explanation:** All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

**Example 2:**

**Input:** room = \[\[1\]\], row = 0, col = 0
**Output:** Robot cleaned all rooms.

**Constraints:**

*   `m == room.length`
*   `n == room[i].length`
*   `1 <= m <= 100`
*   `1 <= n <= 200`
*   `room[i][j]` is either `0` or `1`.
*   `0 <= row < m`
*   `0 <= col < n`
*   `room[row][col] == 1`
*   All the empty cells can be visited from the starting position.
The Maze

There is a ball in a `maze` with empty spaces (represented as `0`) and walls (represented as `1`). The ball can go through the empty spaces by rolling **up, down, left or right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the `m x n` `maze`, the ball's `start` position and the `destination`, where `start = [startrow, startcol]` and `destination = [destinationrow, destinationcol]`, return `true` if the ball can stop at the destination, otherwise return `false`.

You may assume that **the borders of the maze are all walls** (see examples).

**Example 1:**

**Input:** maze = \[\[0,0,1,0,0\],\[0,0,0,0,0\],\[0,0,0,1,0\],\[1,1,0,1,1\],\[0,0,0,0,0\]\], start = \[0,4\], destination = \[4,4\]
**Output:** true
**Explanation:** One possible way is : left -> down -> left -> down -> right -> down -> right.

**Example 2:**

**Input:** maze = \[\[0,0,1,0,0\],\[0,0,0,0,0\],\[0,0,0,1,0\],\[1,1,0,1,1\],\[0,0,0,0,0\]\], start = \[0,4\], destination = \[3,2\]
**Output:** false
**Explanation:** There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

**Example 3:**

**Input:** maze = \[\[0,0,0,0,0\],\[1,1,0,0,1\],\[0,0,0,0,0\],\[0,1,0,0,1\],\[0,1,0,0,0\]\], start = \[4,3\], destination = \[0,1\]
**Output:** false

**Constraints:**

*   `m == maze.length`
*   `n == maze[i].length`
*   `1 <= m, n <= 100`
*   `maze[i][j]` is `0` or `1`.
*   `start.length == 2`
*   `destination.length == 2`
*   `0 <= startrow, destinationrow <= m`
*   `0 <= startcol, destinationcol <= n`
*   Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
*   The maze contains **at least 2 empty spaces**.
Non-decreasing Subsequences

Given an integer array `nums`, return _all the different possible non-decreasing subsequences of the given array with at least two elements_. You may return the answer in **any order**.

**Example 1:**

**Input:** nums = \[4,6,7,7\]
**Output:** \[\[4,6\],\[4,6,7\],\[4,6,7,7\],\[4,7\],\[4,7,7\],\[6,7\],\[6,7,7\],\[7,7\]\]

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 15`
*   `-100 <= nums[i] <= 100`
Construct the Rectangle

A web developer needs to know how to design a web page's size. So, given a specific rectangular web page's area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1.  The area of the rectangular web page you designed must equal to the given target area.
2.  The width `W` should not be larger than the length `L`, which means `L >= W`.
3.  The difference between length `L` and width `W` should be as small as possible.

Return _an array `[L, W]` where `L` and `W` are the length and width of the web page you designed in sequence._

**Example 1:**

**Input:** area = 4
**Output:** \[2,2\]
**Explanation:** The target area is 4, and all the possible ways to construct it are \[1,4\], \[2,2\], \[4,1\]. 
But according to requirement 2, \[1,4\] is illegal; according to requirement 3,  \[4,1\] is not optimal compared to \[2,2\]. So the length L is 2, and the width W is 2.

**Example 2:**

**Input:** area = 37
**Output:** \[37,1\]

**Example 3:**

**Input:** area = 122122
**Output:** \[427,286\]

**Constraints:**

*   `1 <= area <= 107`
Reverse Pairs

Given an integer array `nums`, return _the number of **reverse pairs** in the array_.

A **reverse pair** is a pair `(i, j)` where:

*   `0 <= i < j < nums.length` and
*   `nums[i] > 2 * nums[j]`.

**Example 1:**

**Input:** nums = \[1,3,2,3,1\]
**Output:** 2
**Explanation:** The reverse pairs are:
(1, 4) --> nums\[1\] = 3, nums\[4\] = 1, 3 > 2 \* 1
(3, 4) --> nums\[3\] = 3, nums\[4\] = 1, 3 > 2 \* 1

**Example 2:**

**Input:** nums = \[2,4,3,5,1\]
**Output:** 3
**Explanation:** The reverse pairs are:
(1, 4) --> nums\[1\] = 4, nums\[4\] = 1, 4 > 2 \* 1
(2, 4) --> nums\[2\] = 3, nums\[4\] = 1, 3 > 2 \* 1
(3, 4) --> nums\[3\] = 5, nums\[4\] = 1, 5 > 2 \* 1

**Constraints:**

*   `1 <= nums.length <= 5 * 104`
*   `-231 <= nums[i] <= 231 - 1`
Target Sum

You are given an integer array `nums` and an integer `target`.

You want to build an **expression** out of nums by adding one of the symbols `'+'` and `'-'` before each integer in nums and then concatenate all the integers.

*   For example, if `nums = [2, 1]`, you can add a `'+'` before `2` and a `'-'` before `1` and concatenate them to build the expression `"+2-1 "`.

Return the number of different **expressions** that you can build, which evaluates to `target`.

**Example 1:**

**Input:** nums = \[1,1,1,1,1\], target = 3
**Output:** 5
**Explanation:** There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 20`
*   `0 <= nums[i] <= 1000`
*   `0 <= sum(nums[i]) <= 1000`
*   `-1000 <= target <= 1000`
Teemo Attacking

Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly `duration` seconds. More formally, an attack at second `t` will mean Ashe is poisoned during the **inclusive** time interval `[t, t + duration - 1]`. If Teemo attacks again **before** the poison effect ends, the timer for it is **reset**, and the poison effect will end `duration` seconds after the new attack.

You are given a **non-decreasing** integer array `timeSeries`, where `timeSeries[i]` denotes that Teemo attacks Ashe at second `timeSeries[i]`, and an integer `duration`.

Return _the **total** number of seconds that Ashe is poisoned_.

**Example 1:**

**Input:** timeSeries = \[1,4\], duration = 2
**Output:** 4
**Explanation:** Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

**Example 2:**

**Input:** timeSeries = \[1,2\], duration = 2
**Output:** 3
**Explanation:** Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3.
Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.

**Constraints:**

*   `1 <= timeSeries.length <= 104`
*   `0 <= timeSeries[i], duration <= 107`
*   `timeSeries` is sorted in **non-decreasing** order.
Next Greater Element I

The **next greater element** of some element `x` in an array is the **first greater** element that is **to the right** of `x` in the same array.

You are given two **distinct 0-indexed** integer arrays `nums1` and `nums2`, where `nums1` is a subset of `nums2`.

For each `0 <= i < nums1.length`, find the index `j` such that `nums1[i] == nums2[j]` and determine the **next greater element** of `nums2[j]` in `nums2`. If there is no next greater element, then the answer for this query is `-1`.

Return _an array_ `ans` _of length_ `nums1.length` _such that_ `ans[i]` _is the **next greater element** as described above._

**Example 1:**

**Input:** nums1 = \[4,1,2\], nums2 = \[1,3,4,2\]
**Output:** \[-1,3,-1\]
**Explanation:** The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = \[1,3,4,2\]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = \[1,3,4,2\]. The next greater element is 3.
- 2 is underlined in nums2 = \[1,3,4,2\]. There is no next greater element, so the answer is -1.

**Example 2:**

**Input:** nums1 = \[2,4\], nums2 = \[1,2,3,4\]
**Output:** \[3,-1\]
**Explanation:** The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = \[1,2,3,4\]. The next greater element is 3.
- 4 is underlined in nums2 = \[1,2,3,4\]. There is no next greater element, so the answer is -1.

**Constraints:**

*   `1 <= nums1.length <= nums2.length <= 1000`
*   `0 <= nums1[i], nums2[i] <= 104`
*   All integers in `nums1` and `nums2` are **unique**.
*   All the integers of `nums1` also appear in `nums2`.

**Follow up:** Could you find an `O(nums1.length + nums2.length)` solution?
Random Point in Non-overlapping Rectangles

You are given an array of non-overlapping axis-aligned rectangles `rects` where `rects[i] = [ai, bi, xi, yi]` indicates that `(ai, bi)` is the bottom-left corner point of the `ith` rectangle and `(xi, yi)` is the top-right corner point of the `ith` rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.

Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.

**Note** that an integer point is a point that has integer coordinates.

Implement the `Solution` class:

*   `Solution(int[][] rects)` Initializes the object with the given rectangles `rects`.
*   `int[] pick()` Returns a random integer point `[u, v]` inside the space covered by one of the given rectangles.

**Example 1:**

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

**Explanation**
Solution solution = new Solution(\[\[-2, -2, 1, 1\], \[2, 2, 4, 6\]\]);
solution.pick(); // return \[1, -2\]
solution.pick(); // return \[1, -1\]
solution.pick(); // return \[-1, -2\]
solution.pick(); // return \[-2, -2\]
solution.pick(); // return \[0, 0\]

**Constraints:**

*   `1 <= rects.length <= 100`
*   `rects[i].length == 4`
*   `-109 <= ai < xi <= 109`
*   `-109 <= bi < yi <= 109`
*   `xi - ai <= 2000`
*   `yi - bi <= 2000`
*   All the rectangles do not overlap.
*   At most `104` calls will be made to `pick`.
Diagonal Traverse

Given an `m x n` matrix `mat`, return _an array of all the elements of the array in a diagonal order_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n <= 104`
*   `1 <= m * n <= 104`
*   `-105 <= mat[i][j] <= 105`