bowang0911/leetcode huggingface dataset:
Peeking Iterator

Design an iterator that supports the `peek` operation on an existing iterator in addition to the `hasNext` and the `next` operations.

Implement the `PeekingIterator` class:

*   `PeekingIterator(Iterator nums)` Initializes the object with the given integer iterator `iterator`.
*   `int next()` Returns the next element in the array and moves the pointer to the next element.
*   `boolean hasNext()` Returns `true` if there are still elements in the array.
*   `int peek()` Returns the next element in the array **without** moving the pointer.

**Note:** Each language may have a different implementation of the constructor and `Iterator`, but they all support the `int next()` and `boolean hasNext()` functions.

**Example 1:**

**Input**
\[ "PeekingIterator ",  "next ",  "peek ",  "next ",  "next ",  "hasNext "\]
\[\[\[1, 2, 3\]\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, 1, 2, 2, 3, false\]

**Explanation**
PeekingIterator peekingIterator = new PeekingIterator(\[1, 2, 3\]); // \[**1**,2,3\]
peekingIterator.next();    // return 1, the pointer moves to the next element \[1,**2**,3\].
peekingIterator.peek();    // return 2, the pointer does not move \[1,**2**,3\].
peekingIterator.next();    // return 2, the pointer moves to the next element \[1,2,**3**\]
peekingIterator.next();    // return 3, the pointer moves to the next element \[1,2,3\]
peekingIterator.hasNext(); // return False

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 1000`
*   All the calls to `next` and `peek` are valid.
*   At most `1000` calls will be made to `next`, `hasNext`, and `peek`.

**Follow up:** How would you extend your design to be generic and work with all types, not just integer?
Inorder Successor in BST

Given the `root` of a binary search tree and a node `p` in it, return _the in-order successor of that node in the BST_. If the given node has no in-order successor in the tree, return `null`.

The successor of a node `p` is the node with the smallest key greater than `p.val`.

**Example 1:**

**Input:** root = \[2,1,3\], p = 1
**Output:** 2
**Explanation:** 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

**Example 2:**

**Input:** root = \[5,3,6,2,4,null,null,1\], p = 6
**Output:** null
**Explanation:** There is no in-order successor of the current node, so the answer is `null`.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-105 <= Node.val <= 105`
*   All Nodes will have unique values.
Walls and Gates

You are given an `m x n` grid `rooms` initialized with these three possible values.

*   `-1` A wall or an obstacle.
*   `0` A gate.
*   `INF` Infinity means an empty room. We use the value `231 - 1 = 2147483647` to represent `INF` as you may assume that the distance to a gate is less than `2147483647`.

Fill each empty room with the distance to _its nearest gate_. If it is impossible to reach a gate, it should be filled with `INF`.

**Example 1:**

**Input:** rooms = \[\[2147483647,-1,0,2147483647\],\[2147483647,2147483647,2147483647,-1\],\[2147483647,-1,2147483647,-1\],\[0,-1,2147483647,2147483647\]\]
**Output:** \[\[3,-1,0,1\],\[2,2,1,-1\],\[1,-1,2,-1\],\[0,-1,3,4\]\]

**Example 2:**

**Input:** rooms = \[\[-1\]\]
**Output:** \[\[-1\]\]

**Constraints:**

*   `m == rooms.length`
*   `n == rooms[i].length`
*   `1 <= m, n <= 250`
*   `rooms[i][j]` is `-1`, `0`, or `231 - 1`.
Find the Duplicate Number

Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive.

There is only **one repeated number** in `nums`, return _this repeated number_.

You must solve the problem **without** modifying the array `nums` and uses only constant extra space.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= n <= 105`
*   `nums.length == n + 1`
*   `1 <= nums[i] <= n`
*   All the integers in `nums` appear only **once** except for **precisely one integer** which appears **two or more** times.

**Follow up:**

*   How can we prove that at least one duplicate number must exist in `nums`?
*   Can you solve the problem in linear runtime complexity?
Unique Word Abbreviation

The **abbreviation** of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an **abbreviation** of itself.

For example:

*   `dog --> d1g` because there is one letter between the first letter `'d'` and the last letter `'g'`.
*   `internationalization --> i18n` because there are 18 letters between the first letter `'i'` and the last letter `'n'`.
*   `it --> it` because any word with only two characters is an **abbreviation** of itself.

Implement the `ValidWordAbbr` class:

*   `ValidWordAbbr(String[] dictionary)` Initializes the object with a `dictionary` of words.
*   `boolean isUnique(string word)` Returns `true` if **either** of the following conditions are met (otherwise returns `false`):
    *   There is no word in `dictionary` whose **abbreviation** is equal to `word`'s **abbreviation**.
    *   For any word in `dictionary` whose **abbreviation** is equal to `word`'s **abbreviation**, that word and `word` are **the same**.

**Example 1:**

**Input**
\[ "ValidWordAbbr ",  "isUnique ",  "isUnique ",  "isUnique ",  "isUnique ",  "isUnique "\]
\[\[\[ "deer ",  "door ",  "cake ",  "card "\]\], \[ "dear "\], \[ "cart "\], \[ "cane "\], \[ "make "\], \[ "cake "\]\]
**Output**
\[null, false, true, false, true, true\]

**Explanation**
ValidWordAbbr validWordAbbr = new ValidWordAbbr(\[ "deer ",  "door ",  "cake ",  "card "\]);
validWordAbbr.isUnique( "dear "); // return false, dictionary word  "deer " and word  "dear " have the same abbreviation  "d2r " but are not the same.
validWordAbbr.isUnique( "cart "); // return true, no words in the dictionary have the abbreviation  "c2t ".
validWordAbbr.isUnique( "cane "); // return false, dictionary word  "cake " and word  "cane " have the same abbreviation   "c2e " but are not the same.
validWordAbbr.isUnique( "make "); // return true, no words in the dictionary have the abbreviation  "m2e ".
validWordAbbr.isUnique( "cake "); // return true, because  "cake " is already in the dictionary and no other word in the dictionary has  "c2e " abbreviation.

**Constraints:**

*   `1 <= dictionary.length <= 3 * 104`
*   `1 <= dictionary[i].length <= 20`
*   `dictionary[i]` consists of lowercase English letters.
*   `1 <= word.length <= 20`
*   `word` consists of lowercase English letters.
*   At most `5000` calls will be made to `isUnique`.
Game of Life

According to [Wikipedia's article](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life): "The **Game of Life**, also known simply as **Life**, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. "

The board is made up of an `m x n` grid of cells, where each cell has an initial state: **live** (represented by a `1`) or **dead** (represented by a `0`). Each cell interacts with its [eight neighbors](https://en.wikipedia.org/wiki/Moore_neighborhood) (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1.  Any live cell with fewer than two live neighbors dies as if caused by under-population.
2.  Any live cell with two or three live neighbors lives on to the next generation.
3.  Any live cell with more than three live neighbors dies, as if by over-population.
4.  Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the `m x n` grid `board`, return _the next state_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `m == board.length`
*   `n == board[i].length`
*   `1 <= m, n <= 25`
*   `board[i][j]` is `0` or `1`.

**Follow up:**

*   Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
*   In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?
Word Pattern

Given a `pattern` and a string `s`, find if `s` follows the same pattern.

Here **follow** means a full match, such that there is a bijection between a letter in `pattern` and a **non-empty** word in `s`.

**Example 1:**

**Input:** pattern =  "abba ", s =  "dog cat cat dog "
**Output:** true

**Example 2:**

**Input:** pattern =  "abba ", s =  "dog cat cat fish "
**Output:** false

**Example 3:**

**Input:** pattern =  "aaaa ", s =  "dog cat cat dog "
**Output:** false

**Constraints:**

*   `1 <= pattern.length <= 300`
*   `pattern` contains only lower-case English letters.
*   `1 <= s.length <= 3000`
*   `s` contains only lowercase English letters and spaces `' '`.
*   `s` **does not contain** any leading or trailing spaces.
*   All the words in `s` are separated by a **single space**.
Word Pattern II

Given a `pattern` and a string `s`, return `true` _if_ `s` _**matches** the_ `pattern`_._

A string `s` **matches** a `pattern` if there is some **bijective mapping** of single characters to strings such that if each character in `pattern` is replaced by the string it maps to, then the resulting string is `s`. A **bijective mapping** means that no two characters map to the same string, and no character maps to two different strings.

**Example 1:**

**Input:** pattern =  "abab ", s =  "redblueredblue "
**Output:** true
**Explanation:** One possible mapping is as follows:
'a' ->  "red "
'b' ->  "blue "

**Example 2:**

**Input:** pattern =  "aaaa ", s =  "asdasdasdasd "
**Output:** true
**Explanation:** One possible mapping is as follows:
'a' ->  "asd "

**Example 3:**

**Input:** pattern =  "aabb ", s =  "xyzabcxzyabc "
**Output:** false

**Constraints:**

*   `1 <= pattern.length, s.length <= 20`
*   `pattern` and `s` consist of only lowercase English letters.
Nim Game

You are playing the following Nim Game with your friend:

*   Initially, there is a heap of stones on the table.
*   You and your friend will alternate taking turns, and **you go first**.
*   On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
*   The one who removes the last stone is the winner.

Given `n`, the number of stones in the heap, return `true` _if you can win the game assuming both you and your friend play optimally, otherwise return_ `false`.

**Example 1:**

**Input:** n = 4
**Output:** false
**Explanation:** These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

**Example 2:**

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

**Example 3:**

**Input:** n = 2
**Output:** true

**Constraints:**

*   `1 <= n <= 231 - 1`
Flip Game

You are playing a Flip Game with your friend.

You are given a string `currentState` that contains only `'+'` and `'-'`. You and your friend take turns to flip **two consecutive** `"++ "` into `"-- "`. The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return all possible states of the string `currentState` after **one valid move**. You may return the answer in **any order**. If there is no valid move, return an empty list `[]`.

**Example 1:**

**Input:** currentState =  "++++ "
**Output:** \[ "--++ ", "+--+ ", "++-- "\]

**Example 2:**

**Input:** currentState =  "+ "
**Output:** \[\]

**Constraints:**

*   `1 <= currentState.length <= 500`
*   `currentState[i]` is either `'+'` or `'-'`.
Flip Game II

You are playing a Flip Game with your friend.

You are given a string `currentState` that contains only `'+'` and `'-'`. You and your friend take turns to flip **two consecutive** `"++ "` into `"-- "`. The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return `true` _if the starting player can **guarantee a win**_, and `false` otherwise.

**Example 1:**

**Input:** currentState =  "++++ "
**Output:** true
**Explanation:** The starting player can guarantee a win by flipping the middle  "++ " to become  "+--+ ".

**Example 2:**

**Input:** currentState =  "+ "
**Output:** false

**Constraints:**

*   `1 <= currentState.length <= 60`
*   `currentState[i]` is either `'+'` or `'-'`.

**Follow up:** Derive your algorithm's runtime complexity.
Find Median from Data Stream

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

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

Implement the MedianFinder class:

*   `MedianFinder()` initializes the `MedianFinder` object.
*   `void addNum(int num)` adds the integer `num` from the data stream to the data structure.
*   `double findMedian()` returns the median of all elements so far. Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input**
\[ "MedianFinder ",  "addNum ",  "addNum ",  "findMedian ",  "addNum ",  "findMedian "\]
\[\[\], \[1\], \[2\], \[\], \[3\], \[\]\]
**Output**
\[null, null, null, 1.5, null, 2.0\]

**Explanation**
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = \[1\]
medianFinder.addNum(2);    // arr = \[1, 2\]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr\[1, 2, 3\]
medianFinder.findMedian(); // return 2.0

**Constraints:**

*   `-105 <= num <= 105`
*   There will be at least one element in the data structure before calling `findMedian`.
*   At most `5 * 104` calls will be made to `addNum` and `findMedian`.

**Follow up:**

*   If all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?
*   If `99%` of all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?
Best Meeting Point

Given an `m x n` binary grid `grid` where each `1` marks the home of one friend, return _the minimal **total travel distance**_.

The **total travel distance** is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using [Manhattan Distance](http://en.wikipedia.org/wiki/Taxicab_geometry), where `distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|`.

**Example 1:**

**Input:** grid = \[\[1,0,0,0,1\],\[0,0,0,0,0\],\[0,0,1,0,0\]\]
**Output:** 6
**Explanation:** Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

**Example 2:**

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

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 200`
*   `grid[i][j]` is either `0` or `1`.
*   There will be **at least two** friends in the `grid`.
Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

**Clarification:** The input/output format is the same as [how LeetCode serializes a binary tree](https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Example 1:**

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

**Example 2:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `-1000 <= Node.val <= 1000`
Binary Tree Longest Consecutive Sequence

Given the `root` of a binary tree, return _the length of the longest **consecutive sequence path**_.

A **consecutive sequence path** is a path where the values **increase by one** along the path.

Note that the path can start **at any node** in the tree, and you cannot go from a node to its parent in the path.

**Example 1:**

**Input:** root = \[1,null,3,2,4,null,null,null,5\]
**Output:** 3
**Explanation:** Longest consecutive sequence path is 3-4-5, so return 3.

**Example 2:**

**Input:** root = \[2,null,3,2,null,1\]
**Output:** 2
**Explanation:** Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 3 * 104]`.
*   `-3 * 104 <= Node.val <= 3 * 104`
Bulls and Cows

You are playing the **[Bulls and Cows](https://en.wikipedia.org/wiki/Bulls_and_Cows)** game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

*   The number of "bulls ", which are digits in the guess that are in the correct position.
*   The number of "cows ", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number `secret` and your friend's guess `guess`, return _the hint for your friend's guess_.

The hint should be formatted as `"xAyB "`, where `x` is the number of bulls and `y` is the number of cows. Note that both `secret` and `guess` may contain duplicate digits.

**Example 1:**

**Input:** secret =  "1807 ", guess =  "7810 "
**Output:**  "1A3B "
**Explanation:** Bulls are connected with a '|' and cows are underlined:
 "1807 "
  |
 "7810 "

**Example 2:**

**Input:** secret =  "1123 ", guess =  "0111 "
**Output:**  "1A1B "
**Explanation:** Bulls are connected with a '|' and cows are underlined:
 "1123 "         "1123 "
  |      or     |
 "0111 "         "0111 "
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

**Constraints:**

*   `1 <= secret.length, guess.length <= 1000`
*   `secret.length == guess.length`
*   `secret` and `guess` consist of digits only.
Longest Increasing Subsequence

Given an integer array `nums`, return _the length of the longest **strictly increasing**_ _**subsequence**_.

**Example 1:**

**Input:** nums = \[10,9,2,5,3,7,101,18\]
**Output:** 4
**Explanation:** The longest increasing subsequence is \[2,3,7,101\], therefore the length is 4.

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 2500`
*   `-104 <= nums[i] <= 104`

**Follow up:** Can you come up with an algorithm that runs in `O(n log(n))` time complexity?
Remove Invalid Parentheses

Given a string `s` that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return _a list of **unique strings** that are valid with the minimum number of removals_. You may return the answer in **any order**.

**Example 1:**

**Input:** s =  "()())() "
**Output:** \[ "(())() ", "()()() "\]

**Example 2:**

**Input:** s =  "(a)())() "
**Output:** \[ "(a())() ", "(a)()() "\]

**Example 3:**

**Input:** s =  ")( "
**Output:** \[ " "\]

**Constraints:**

*   `1 <= s.length <= 25`
*   `s` consists of lowercase English letters and parentheses `'('` and `')'`.
*   There will be at most `20` parentheses in `s`.
Smallest Rectangle Enclosing Black Pixels

You are given an `m x n` binary matrix `image` where `0` represents a white pixel and `1` represents a black pixel.

The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically.

Given two integers `x` and `y` that represents the location of one of the black pixels, return _the area of the smallest (axis-aligned) rectangle that encloses all black pixels_.

You must write an algorithm with less than `O(mn)` runtime complexity

**Example 1:**

**Input:** image = \[\[ "0 ", "0 ", "1 ", "0 "\],\[ "0 ", "1 ", "1 ", "0 "\],\[ "0 ", "1 ", "0 ", "0 "\]\], x = 0, y = 2
**Output:** 6

**Example 2:**

**Input:** image = \[\[ "1 "\]\], x = 0, y = 0
**Output:** 1

**Constraints:**

*   `m == image.length`
*   `n == image[i].length`
*   `1 <= m, n <= 100`
*   `image[i][j]` is either `'0'` or `'1'`.
*   `0 <= x < m`
*   `0 <= y < n`
*   `image[x][y] == '1'.`
*   The black pixels in the `image` only form **one component**.
Range Sum Query - Immutable

Given an integer array `nums`, handle multiple queries of the following type:

1.  Calculate the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** where `left <= right`.

Implement the `NumArray` class:

*   `NumArray(int[] nums)` Initializes the object with the integer array `nums`.
*   `int sumRange(int left, int right)` Returns the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** (i.e. `nums[left] + nums[left + 1] + ... + nums[right]`).

**Example 1:**

**Input**
\[ "NumArray ",  "sumRange ",  "sumRange ",  "sumRange "\]
\[\[\[-2, 0, 3, -5, 2, -1\]\], \[0, 2\], \[2, 5\], \[0, 5\]\]
**Output**
\[null, 1, -1, -3\]

**Explanation**
NumArray numArray = new NumArray(\[-2, 0, 3, -5, 2, -1\]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-105 <= nums[i] <= 105`
*   `0 <= left <= right < nums.length`
*   At most `104` calls will be made to `sumRange`.
Range Sum Query 2D - Immutable

Given a 2D matrix `matrix`, handle multiple queries of the following type:

*   Calculate the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

Implement the `NumMatrix` class:

*   `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
*   `int sumRegion(int row1, int col1, int row2, int col2)` Returns the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

You must design an algorithm where `sumRegion` works on `O(1)` time complexity.

**Example 1:**

**Input**
\[ "NumMatrix ",  "sumRegion ",  "sumRegion ",  "sumRegion "\]
\[\[\[\[3, 0, 1, 4, 2\], \[5, 6, 3, 2, 1\], \[1, 2, 0, 1, 5\], \[4, 1, 0, 1, 7\], \[1, 0, 3, 0, 5\]\]\], \[2, 1, 4, 3\], \[1, 1, 2, 2\], \[1, 2, 2, 4\]\]
**Output**
\[null, 8, 11, 12\]

**Explanation**
NumMatrix numMatrix = new NumMatrix(\[\[3, 0, 1, 4, 2\], \[5, 6, 3, 2, 1\], \[1, 2, 0, 1, 5\], \[4, 1, 0, 1, 7\], \[1, 0, 3, 0, 5\]\]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 200`
*   `-104 <= matrix[i][j] <= 104`
*   `0 <= row1 <= row2 < m`
*   `0 <= col1 <= col2 < n`
*   At most `104` calls will be made to `sumRegion`.