Problem url: [https://leetcode.com/problems/pascals-triangle/?envType=daily-question&envId=2023-09-08]

Description:
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:
Input: numRows = 1
Output: [[1]]

Constraints:
1 <= numRows <= 30

Problem URL: [Combination Sum IV - LeetCode](https://leetcode.com/problems/combination-sum-iv/?envType=daily-question&amp;envId=2023-09-09)

Problem Statement:
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to the target.

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

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique.
- 1 <= target <= 1000

Problem Description

Given a number n representing the total number of orders, where each order consists of a pickup and a delivery service. Count all the valid sequences of pickup and delivery such that the delivery for each order always comes after the pickup. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1:

Input: n = 1
Output: 1
Explanation: There is only one unique order (P1, D1), where Delivery 1 always comes after Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: There are six possible orders:
1. (P1, P2, D1, D2)
2. (P1, P2, D2, D1)
3. (P1, D1, P2, D2)
4. (P2, P1, D1, D2)
5. (P2, P1, D2, D1)
6. (P2, D2, P1, D1)
However, the order (P1, D2, P2, D1) is invalid because Pickup 2 comes after Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

Problem URL

The problem can be found [here](https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/?envType=daily-question&amp;envId=2023-09-10).

Problem URL: [Group the People Given the Group Size They Belong To - LeetCode](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/?envType=daily-question&amp;envId=2023-09-11)

Description:

- There are n people that are split into some unknown number of groups.
- Each person is labeled with a unique ID from 0 to n - 1.
- You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in.
- Return a list of groups such that each person i is in a group of size groupSizes[i].
- Each person should appear in exactly one group, and every person must be in a group.
- If there are multiple answers, return any of them.
- It is guaranteed that there will be at least one valid solution for the given input.

Examples:

Example 1:

Input:

groupSizes = [3,3,3,3,3,1,3]

Output:

[[5],[0,1,2],[3,4,6]]

Explanation:
- The first group is [5]. The size is 1, and groupSizes[5] = 1.
- The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
- The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
- Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input:

groupSizes = [2,1,3,3,3,2]

Output:

[[1],[0,5],[2,3,4]]

Constraints:

- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n

Problem Description

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, we need to find the minimum number of characters we need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1

Input: s = "aab"
Output: 0
Explanation: s is already good.

Example 2

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way is to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints

- 1 <= s.length <= 10^5
- s contains only lowercase English letters.

[Problem URL](https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/?envType=daily-question&amp;envId=2023-09-12)

Problem url: [https://leetcode.com/problems/candy/?envType=daily-question&amp;envId=2023-09-13]

Problem:
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second, and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second, and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4

Problem: Reconstruct Itinerary

URL: [Problem URL](https://leetcode.com/problems/reconstruct-itinerary/?envType=daily-question&amp;envId=2023-09-14)

Description:
- Given a list of airline tickets where each ticket represents the departure and arrival airports of a flight.
- Reconstruct the itinerary in order and return it.
- All tickets belong to a man who departs from "JFK".
- The itinerary must begin with "JFK".
- If multiple valid itineraries exist, return the one with the smallest lexical order.
- All tickets must be used once and only once.

Examples:
1. Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

2. Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Constraints:
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- fromi.length == 3
- toi.length == 3
- fromi and toi consist of uppercase English letters.
- fromi != toi

Problem URL: [https://leetcode.com/problems/min-cost-to-connect-all-points/?envType=daily-question&amp;envId=2023-09-15](https://leetcode.com/problems/min-cost-to-connect-all-points/?envType=daily-question&amp;envId=2023-09-15)

Text:
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Constraints:
- 1 <= points.length <= 1000
- -10^6 <= xi, yi <= 10^6
- All pairs (xi, yi) are distinct.

Problem url: [https://leetcode.com/problems/path-with-minimum-effort/?envType=daily-question&amp;envId=2023-09-16](https://leetcode.com/problems/path-with-minimum-effort/?envType=daily-question&amp;envId=2023-09-16)

Text: You are given a 2D array of heights, where each element represents the height of a cell. You start at the top-left cell and want to travel to the bottom-right cell. You can move up, down, left, or right and want to find the route that requires the minimum effort. The effort of a route is defined as the maximum absolute difference in heights between two consecutive cells. Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route [1,3,5,3,5] has a maximum difference of 2, which is better than the route [1,2,2,2,5] with a maximum difference of 3.

Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route [1,2,3,4,5] has a maximum difference of 1, which is better than the route [1,3,5,3,5].

Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:
- rows and columns of the array are positive integers less than or equal to 100.
- The height value of each cell is between 1 and 1,000,000.

https://leetcode.com/problems/shortest-path-visiting-all-nodes/

847. Shortest Path Visiting All Nodes
Hard
3.5K
145
Companies
You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
 
Example 1:
Input: graph = [[1,2,3],[0],[0],[0]] Output: 4 Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3]
 
Constraints:
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] does not contain i.
If graph[a] contains b, then graph[b] contains a.
The input graph is always connected.

Problem Description

You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:
- The number of soldiers in row i is less than the number of soldiers in row j.
- Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 1 
- Row 1: 4 
- Row 2: 1 
- Row 3: 1 
The rows ordered from weakest to strongest are [0,2,3,1].

Constraints:

- m == mat.length
- n == mat[i].length
- 2 <= n, m <= 100
- 1 <= k <= m
- matrix[i][j] is either 0 or 1.

Problem URL: [https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/?envType=daily-question&amp;envId=2023-09-18)

Problem url:
[https://leetcode.com/problems/find-the-duplicate-number/?envType=daily-question&amp;envId=2023-09-19](https://leetcode.com/problems/find-the-duplicate-number/?envType=daily-question&amp;envId=2023-09-19)

Problem description:

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 <= 10^5
- 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.

Problem URL: [Minimum Operations to Reduce X to Zero](https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/?envType=daily-question&amp;envId=2023-09-20)

Text:
Given an integer array nums and an integer x, you are asked to find the minimum number of operations required to reduce x to exactly 0. In each operation, you can remove either the leftmost or the rightmost element from the array nums and subtract its value from x. It is important to note that performing an operation will modify the array for future operations.

If it is impossible to reduce x to 0, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements in the array to reduce `x` to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (total of 5 operations) to reduce `x` to zero.

Constraints:
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
- 1 <= x <= 10^9*

Problem:

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Examples:

Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: Merged array = [1,2,3] and median is 2.

Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: Merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6

Problem URL: [https://leetcode.com/problems/median-of-two-sorted-arrays/?envType=daily-question&amp;envId=2023-09-21](https://leetcode.com/problems/median-of-two-sorted-arrays/?envType=daily-question&amp;envId=2023-09-21)

Problem url: [https://leetcode.com/problems/is-subsequence/?envType=daily-question&amp;envId=2023-09-22](https://leetcode.com/problems/is-subsequence/?envType=daily-question&amp;envId=2023-09-22)

Text: Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
- s and t consist only of lowercase English letters.

Follow up:
Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 10^9, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Problem URL: [Longest String Chain](https://leetcode.com/problems/longest-string-chain/?envType=daily-question&amp;envId=2023-09-23)

Text:
You are given an array of words where each word consists of lowercase English letters.

A word chain is a sequence of words where each word is the predecessor of the next word, obtained by inserting exactly one letter anywhere in the current word. The order of the other characters in the word must remain the same.

Return the length of the longest possible word chain with words chosen from the given list of words.

---
Example 1:

Input:

words = ["a","b","ba","bca","bda","bdca"]

Output:

4

Explanation:
One of the longest word chains is ["a","ba","bda","bdca"].

---
Example 2:

Input:

words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output:

5

Explanation:
All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

---
Example 3:

Input:

words = ["abcd","dbqca"]

Output:

1

Explanation:
The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

---
Constraints:

- 1 <= words.length <= 1000
- 1 <= words[i].length <= 16
- words[i] only consists of lowercase English letters.

Problem Description

We have a pyramid of glasses with the following properties:
- The first row has 1 glass, the second row has 2 glasses, and so on until the 100th row.
- Each glass holds one cup of champagne.

When champagne is poured into the topmost glass, any excess liquid poured will fall equally to the glass immediately to the left and right of it. This process continues until the bottom row where excess champagne falls on the floor.

Given the number of cups of champagne poured (poured), and the index of the glass in the row (query_glass) and the row number (query_row) we need to determine how full the specified glass will be.

Examples

- Example 1:
- Input: poured = 1, query_row = 1, query_glass = 1
- Output: 0.00000
- Explanation: We poured 1 cup of champagne into the top glass of the pyramid (indexed as (0, 0)). There will be no excess liquid, so all the glasses under the top glass will remain empty.

- Example 2:
- Input: poured = 2, query_row = 1, query_glass = 1
- Output: 0.50000
- Explanation: We poured 2 cups of champagne into the top glass of the pyramid (indexed as (0, 0)). There is one cup of excess liquid. The glasses indexed as (1, 0) and (1, 1) will share the excess liquid equally, and each will have half a cup of champagne.

- Example 3:
- Input: poured = 100000009, query_row = 33, query_glass = 17
- Output: 1.00000
- Explanation: We poured 100000009 cups of champagne into the top glass of the pyramid (indexed as (0, 0)). The glass at row 33 and index 17 will have a full cup of champagne.

Constraints
- 0 <= poured <= 10^9
- 0 <= query_glass <= query_row < 100

Problem URL: [https://leetcode.com/problems/find-the-difference/?envType=daily-question&amp;envId=2023-09-25](https://leetcode.com/problems/find-the-difference/?envType=daily-question&amp;envId=2023-09-25)

Problem Description:
You are given two strings, s and t.
String t is generated by randomly shuffling string s and then adding one more letter at a random position.
Your task is to return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:
- 0 <= s.length <= 1000
- t.length == s.length + 1
- Both s and t consist of lowercase English letters.

Problem url: [https://leetcode.com/problems/remove-duplicate-letters/?envType=daily-question&amp;envId=2023-09-26](https://leetcode.com/problems/remove-duplicate-letters/?envType=daily-question&amp;envId=2023-09-26)

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: s = "bcabc"

Output: "abc"

Example 2:

Input: s = "cbacdcbc"

Output: "acdb"

Constraints:

- 1 <= s.length <= 104
- s consists of lowercase English letters.

Note: This question is the same as 1081: [https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/](https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/)

Problem: [LeetCode - Decoded String at Index](https://leetcode.com/problems/decoded-string-at-index/?envType=daily-question&amp;envId=2023-09-27)

You are given an encoded string s. To decode the string and obtain a tape, the following steps are taken:
- If a character read is a letter, that letter is written onto the tape.
- If a character read is a digit d, the entire current tape is written d - 1 more times.

Given an integer k, return the kth letter (1-indexed) in the decoded string.

Example 1:
Input: s = "leet2code3", k = 10
Output: "o"
Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter in the string is "o".

Example 2:
Input: s = "ha22", k = 5
Output: "h"
Explanation: The decoded string is "hahahaha". The 5th letter is "h".

Example 3:
Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times. The 1st letter is "a".

Constraints:
- 2 <= s.length <= 100
- s consists of lowercase English letters and digits 2 through 9.
- s starts with a letter.
- 1 <= k <= 10^9
- It is guaranteed that k is less than or equal to the length of the decoded string.
- The decoded string is guaranteed to have less than 2^63 letters.

Problem Description:

Move all the even integers at the beginning of the given array nums, followed by all the odd integers. Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

Constraints:
- 1 <= nums.length <= 5000
- 0 <= nums[i] <= 5000

Problem URL: [Sort Array By Parity - LeetCode](https://leetcode.com/problems/sort-array-by-parity/?envType=daily-question&amp;envId=2023-09-28)