2022-09-13
393. UTF-8 Validation

Topic: Array, Bit Manipulation
Difficulty: Medium

Problem:
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
2. For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Number of Bytes   |        UTF-8 Octet Sequence
                       |              (binary)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x denotes a bit in the binary form of a byte that may be either 0 or 1.

Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

Constraints:

• 1 <= data.length <= 2 * 10^4
• 0 <= data[i] <= 255

2022-09-14
1457. Pseudo-Palindromic Paths in a Binary Tree

Topic: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Image: https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [1, 10^5].
• 1 <= Node.val <= 9

2022-09-15
2007. Find Original Array From Doubled Array

Topic: Array, Hash Table, Greedy, Sorting
Difficulty: Medium

Problem:
An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

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

2022-09-16
1770. Maximum Score from Performing Multiplication Operations

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You are given two integer arrays nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (1-indexed), you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x to your score.
• Remove x from the array nums.

Return the maximum score after performing m operations.

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

Constraints:

• n == nums.length
• m == multipliers.length
• 1 <= m <= 10^3
• m <= n <= 10^5
• -1000 <= nums[i], multipliers[i] <= 1000

2022-09-17
336. Palindrome Pairs

Topic: Array, Hash Table, String, Trie
Difficulty: Hard

Problem:
Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

2022-09-18
42. Trapping Rain Water

Topic: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
Difficulty: Hard

Problem:
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Image: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

2022-09-19
609. Find Duplicate File in System

Topic: Array, Hash Table, String
Difficulty: Medium

Problem:
Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.

A group of duplicate files consists of at least two files that have the same content.

A single directory info string in the input list has the following format:

• "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory "root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

• "directory_path/file_name.txt"

Example 1:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Example 2:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Constraints:

• 1 <= paths.length <= 2 * 10^4
• 1 <= paths[i].length <= 3000
• 1 <= sum(paths[i].length) <= 5 * 10^5
• paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.
• You may assume no files or directories share the same name in the same directory.
• You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.

Follow up:

• Imagine you are given a real file system, how will you search files? DFS or BFS?
• If the file content is very large (GB level), how will you modify your solution?
• If you can only read the file by 1kb each time, how will you modify your solution?
• What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?
• How to make sure the duplicated files you find are not false positive?

2022-09-20
718. Maximum Length of Repeated Subarray

Topic: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function
Difficulty: Medium

Problem:
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

2022-09-21
985. Sum of Even Numbers After Queries

Topic: Array, Simulation
Difficulty: Medium

Problem:
You are given an integer array nums and an array queries where queries[i] = [val_i, index_i].

For each query i, first, apply nums[index_i] = nums[index_i] + val_i, then print the sum of the even values of nums.

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

Example 1:

Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: At the beginning, the array is [1,2,3,4].
After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Example 2:

Input: nums = [1], queries = [[4,0]]
Output: [0]

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• 1 <= queries.length <= 10^4
• -10^4 <= val_i <= 10^4
• 0 <= index_i < nums.length

2022-09-22
557. Reverse Words in a String III

Topic: Two Pointers, String
Difficulty: Easy

Problem:
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "God Ding"
Output: "doG gniD"

Constraints:

• 1 <= s.length <= 5 * 10^4
• s contains printable ASCII characters.
• s does not contain any leading or trailing spaces.
• There is at least one word in s.
• All the words in s are separated by a single space.

2022-09-23
1680. Concatenation of Consecutive Binary Numbers

Topic: Math, Bit Manipulation, Simulation
Difficulty: Medium

Problem:
Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10^9 + 7, the result is 505379714.

Constraints:

• 1 <= n <= 10^5

2022-09-24
113. Path Sum II

Topic: Backtracking, Tree, Depth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Image: https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

2022-09-25
622. Design Circular Queue

Topic: Array, Linked List, Design, Queue
Difficulty: Medium

Problem:
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• int Front() Gets the front item from the queue. If the queue is empty, return -1.
• int Rear() Gets the last item from the queue. If the queue is empty, return -1.
• boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
• boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• boolean isEmpty() Checks whether the circular queue is empty or not.
• boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language. 

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

2022-09-26
990. Satisfiability of Equality Equations

Topic: Array, String, Union Find, Graph
Difficulty: Medium

Problem:
You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "x_i==y_i" or "x_i!=y_i".Here, x_i and y_i are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Example 1:

Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

Example 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Constraints:

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] is a lowercase letter.
• equations[i][1] is either '=' or '!'.
• equations[i][2] is '='.
• equations[i][3] is a lowercase letter.

2022-09-27
838. Push Dominoes

Topic: Two Pointers, String, Dynamic Programming
Difficulty: Medium

Problem:
There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

• dominoes[i] = 'L', if the i^th domino has been pushed to the left,
• dominoes[i] = 'R', if the i^th domino has been pushed to the right, and
• dominoes[i] = '.', if the i^th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Example 2:

Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/05/18/domino.png

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Constraints:

• n == dominoes.length
• 1 <= n <= 10^5
• dominoes[i] is either 'L', 'R', or '.'.

2022-09-28
19. Remove Nth Node From End of List

Topic: Linked List, Two Pointers
Difficulty: Medium

Problem:
Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

2022-09-29
658. Find K Closest Elements

Topic: Array, Two Pointers, Binary Search, Sorting, Heap (Priority Queue)
Difficulty: Medium

Problem:
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• arr is sorted in ascending order.
• -10^4 <= arr[i], x <= 10^4

2022-09-30
218. The Skyline Problem

Topic: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Line Sweep, Heap (Priority Queue), Ordered Set
Difficulty: Hard

Problem:
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]:

• left_i is the x coordinate of the left edge of the i^th building.
• right_i is the x coordinate of the right edge of the i^th building.
• height_i is the height of the i^th building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x_1,y_1],[x_2,y_2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

Example 1:

Image: https://assets.leetcode.com/uploads/2020/12/01/merged.jpg

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Constraints:

• 1 <= buildings.length <= 10^4
• 0 <= left_i < right_i <= 2^31 - 1
• 1 <= height_i <= 2^31 - 1
• buildings is sorted by left_i in non-decreasing order.

2022-10-01
91. Decode Ways

Topic: String, Dynamic Programming
Difficulty: Medium

Problem:
A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

2022-10-02
1155. Number of Dice Rolls With Target Sum

Topic: Dynamic Programming
Difficulty: Medium

Problem:
You have n dice and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the k^n total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 10^9 + 7.

Constraints:

• 1 <= n, k <= 30
• 1 <= target <= 1000