https://leetcode.com/problems/counting-bits/

338. Counting Bits
Easy
9.5K
449
Companies

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.



Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101



Constraints:

0 <= n <= 10^5



Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

https://leetcode.com/problems/extra-characters-in-a-string/

2707. Extra Characters in a String
Medium
600
36
Companies

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.



Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.



Constraints:

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] and s consists of only lowercase English letters
dictionary contains distinct words

https://leetcode.com/problems/unique-paths/

62. Unique Paths
Medium
15K
405
Companies

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.



Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down



Constraints:

1 <= m, n <= 100

### Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

### Example

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

### Constraints

- The number of nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked list.

### Follow up

Can you solve it using O(1) (i.e. constant) memory?

### Additional Information

Problem URL: [https://leetcode.com/problems/linked-list-cycle/?envType=daily-question&amp;envId=2023-09-04](https://leetcode.com/problems/linked-list-cycle/?envType=daily-question&amp;envId=2023-09-04)

Problem Description

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Input

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Output

Return the head of the copied linked list.

Examples

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

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

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.

Problem URL

The problem can be found at: [Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/?envType=daily-question&amp;envId=2023-09-05)

Problem Description:

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts. The length of each part should be as equal as possible, with no two parts having a size differing by more than one. This may lead to some parts being null. The parts should be in the order of occurrence in the input list, with parts occurring earlier always having a size greater than or equal to parts occurring later. Return an array of the k parts.

Example 1:

Input:
head = [1,2,3]
k = 5

Output:
[[1],[2],[3],[],[]]

Explanation:
The first element (output[0]) has value 1 and next node as null. The last element (output[4]) is null, but its string representation as a ListNode is [].

Example 2:

Input:
head = [1,2,3,4,5,6,7,8,9,10]
k = 3

Output:
[[1,2,3,4],[5,6,7],[8,9,10]]

Explanation:
The input has been split into consecutive parts with a size difference at most 1, and earlier parts are larger in size than the later parts.

Constraints:

- The number of nodes in the list is in the range [0, 1000].
- 0 <= Node.val <= 1000
- 1 <= k <= 50
https://leetcode.com/problems/split-linked-list-in-parts/?envType=daily-question&amp;envId=2023-09-06

[Problem url](https://leetcode.com/problems/reverse-linked-list-ii/?envType=daily-question&amp;envId=2023-09-07)

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Follow up: Could you do it in one pass?

Problem url: [https://leetcode.com/problems/pascals-triangle/?envType=daily-question&amp;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)