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)

Problem url: [LeetCode Monotonic Array](https://leetcode.com/problems/monotonic-array/?envType=daily-question&amp;envId=2023-09-29)

Text:
An array is monotonic if it is either monotone increasing or monotone decreasing.
An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j].
An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].
Given an integer array nums, return true if the given array is monotonic, or false otherwise.

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

Example 2:
- Input: nums = [6,5,4,4]
- Output: true

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

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

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

Text:

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

n == nums.length
1 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9

Problem URL: [Reverse Words in a String III - LeetCode](https://leetcode.com/problems/reverse-words-in-a-string-iii/?envType=daily-question&amp;envId=2023-10-01)

Text:

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.

Problem Statement:

There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the ith piece.

Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.

Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.

Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.

Alice and Bob cannot remove pieces from the edge of the line.

If a player cannot make a move on their turn, that player loses and the other player wins.

Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.

Example:

Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.

Constraints:

- 1 <= colors.length <= 105
- colors consists of only the letters 'A' and 'B'

[Problem](https://leetcode.com/problems/number-of-good-pairs/?envType=daily-question&amp;envId=2023-10-03): Given an array of integers nums, return the number of good pairs.
A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array is good.

Example 3:
Input: nums = [1,2,3]
Output: 0

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

Problem: Design and implement a HashMap data structure without using any built-in hash table libraries. The HashMap should have the following functionalities:

- Initialize the object with an empty map.
- Insert a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
- Return the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
- Remove the key and its corresponding value if the map contains the mapping for the key.

Example:

plaintext
Input:
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output:
[null, null, null, 1, -1, null, 1, null, -1]

Explanation:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // Remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:
- 0 <= key, value <= 10^6
- At most 10^4 calls will be made to put, get, and remove.

Problem URL: [https://leetcode.com/problems/design-hashmap/?envType=daily-question&amp;envId=2023-10-04](https://leetcode.com/problems/design-hashmap/?envType=daily-question&amp;envId=2023-10-04)

Problem url: [https://leetcode.com/problems/majority-element-ii/](https://leetcode.com/problems/majority-element-ii/?envType=daily-question&amp;envId=2023-10-05)

Given an integer array nums of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

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

Example 3:

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

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

Follow up: Could you solve the problem in linear time and in O(1) space?

Problem: Integer Break

URL: [https://leetcode.com/problems/integer-break/?envType=daily-question&amp;envId=2023-10-06](https://leetcode.com/problems/integer-break/?envType=daily-question&amp;envId=2023-10-06)

Description: Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:
- 2 <= n <= 58

Problem:

Given three integers n, m, and k, you are tasked with building an array arr with the following properties:

- arr consists of exactly n integers.
- Each element in arr is a positive integer between 1 and m.
- After applying a certain algorithm to arr, the resulting search_cost is equal to k.

Your goal is to return the number of ways to build arr satisfying the given conditions. Since the answer may be large, it should be computed modulo 10^9 + 7.

Example:

- Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays meeting the given conditions are: [1, 1], [2, 1], [2, 2], [3, 1], [3, 2], [3, 3].

- Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the given conditions.

- Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array satisfying the conditions is [1, 1, 1, 1, 1, 1, 1, 1, 1].

Constraints:

- 1 <= n <= 50
- 1 <= m <= 100
- 0 <= k <= n