2023-06-07
1318. Minimum Flips to Make a OR b Equal to c
Topic: Bit Manipulation
Difficulty: Medium
Problem:
Given 3 positives numbers
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/06/sample_3_1676.png
Example 2:
Example 3:
Constraints:
•
•
•
1318. Minimum Flips to Make a OR b Equal to c
Topic: Bit Manipulation
Difficulty: Medium
Problem:
Given 3 positives numbers
a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/06/sample_3_1676.png
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)
Example 2:
Input: a = 4, b = 2, c = 7
Output: 1
Example 3:
Input: a = 1, b = 2, c = 3
Output: 0
Constraints:
•
1 <= a <= 10^9•
1 <= b <= 10^9•
1 <= c <= 10^92023-06-08
1351. Count Negative Numbers in a Sorted Matrix
Topic: Array, Binary Search, Matrix
Difficulty: Easy
Problem:
Given a
Example 1:
Example 2:
Constraints:
•
•
•
•
Follow up: Could you find an
1351. Count Negative Numbers in a Sorted Matrix
Topic: Array, Binary Search, Matrix
Difficulty: Easy
Problem:
Given a
m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
Example 2:
Input: grid = [[3,2],[1,0]]
Output: 0
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 100•
-100 <= grid[i][j] <= 100Follow up: Could you find an
O(n + m) solution?2023-06-09
744. Find Smallest Letter Greater Than Target
Topic: Array, Binary Search
Difficulty: Easy
Problem:
You are given an array of characters
Return the smallest character in
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
744. Find Smallest Letter Greater Than Target
Topic: Array, Binary Search
Difficulty: Easy
Problem:
You are given an array of characters
letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.Return the smallest character in
letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.Example 1:
Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:
Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
Example 3:
Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
Constraints:
•
2 <= letters.length <= 10^4•
letters[i] is a lowercase English letter.•
letters is sorted in non-decreasing order.•
letters contains at least two different characters.•
target is a lowercase English letter.2023-06-10
1802. Maximum Value at a Given Index in a Bounded Array
Topic: Binary Search, Greedy
Difficulty: Medium
Problem:
You are given three positive integers:
•
•
•
• The sum of all the elements of
•
Return
Note that
Example 1:
Example 2:
Constraints:
•
•
1802. Maximum Value at a Given Index in a Bounded Array
Topic: Binary Search, Greedy
Difficulty: Medium
Problem:
You are given three positive integers:
n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:•
nums.length == n•
nums[i] is a positive integer where 0 <= i < n.•
abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.• The sum of all the elements of
nums does not exceed maxSum.•
nums[index] is maximized.Return
nums[index] of the constructed array.Note that
abs(x) equals x if x >= 0, and -x otherwise.Example 1:
Input: n = 4, index = 2, maxSum = 6
Output: 2
Explanation: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].
Example 2:
Input: n = 6, index = 1, maxSum = 10
Output: 3
Constraints:
•
1 <= n <= maxSum <= 10^9•
0 <= index < n2023-06-11
1146. Snapshot Array
Topic: Array, Hash Table, Binary Search, Design
Difficulty: Medium
Problem:
Implement a SnapshotArray that supports the following interface:
•
•
•
•
Example 1:
Constraints:
•
•
•
•
• At most
1146. Snapshot Array
Topic: Array, Hash Table, Binary Search, Design
Difficulty: Medium
Problem:
Implement a SnapshotArray that supports the following interface:
•
SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.•
void set(index, val) sets the element at the given index to be equal to val.•
int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.•
int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_idExample 1:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
Constraints:
•
1 <= length <= 5 * 10^4•
0 <= index < length•
0 <= val <= 10^9•
0 <= snap_id < (the total number of times we call snap())• At most
5 * 10^4 calls will be made to set, snap, and get.2023-06-12
228. Summary Ranges
Topic: Array
Difficulty: Easy
Problem:
You are given a sorted unique integer array
A range
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of
Each range
•
•
Example 1:
Example 2:
Constraints:
•
•
• All the values of
•
228. Summary Ranges
Topic: Array
Difficulty: Easy
Problem:
You are given a sorted unique integer array
nums.A range
[a,b] is the set of all integers from a to b (inclusive).Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of
nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.Each range
[a,b] in the list should be output as:•
"a->b" if a != b•
"a" if a == bExample 1:
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Example 2:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
Constraints:
•
0 <= nums.length <= 20•
-2^31 <= nums[i] <= 2^31 - 1• All the values of
nums are unique.•
nums is sorted in ascending order.2023-06-13
2352. Equal Row and Column Pairs
Topic: Array, Hash Table, Matrix, Simulation
Difficulty: Medium
Problem:
Given a 0-indexed
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Image: https://assets.leetcode.com/uploads/2022/06/01/ex1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2022/06/01/ex2.jpg
Constraints:
•
•
•
2352. Equal Row and Column Pairs
Topic: Array, Hash Table, Matrix, Simulation
Difficulty: Medium
Problem:
Given a 0-indexed
n x n integer matrix grid, return the number of pairs (r_i, c_j) such that row r_i and column c_j are equal.A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Image: https://assets.leetcode.com/uploads/2022/06/01/ex1.jpg
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]
Example 2:
Image: https://assets.leetcode.com/uploads/2022/06/01/ex2.jpg
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]
Constraints:
•
n == grid.length == grid[i].length•
1 <= n <= 200•
1 <= grid[i][j] <= 10^52023-06-14
530. Minimum Absolute Difference in BST
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg
Constraints:
• The number of nodes in the tree is in the range
•
Note: This question is the same as 783: <https://leetcode.com/problems/minimum-distance-between-bst-nodes/>
530. Minimum Absolute Difference in BST
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.Example 1:
Image: https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Image: https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg
Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:
• The number of nodes in the tree is in the range
[2, 10^4].•
0 <= Node.val <= 10^5Note: This question is the same as 783: <https://leetcode.com/problems/minimum-distance-between-bst-nodes/>
2023-06-15
1161. Maximum Level Sum of a Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
Return the smallest level
Example 1:
Image: https://assets.leetcode.com/uploads/2019/05/03/capture.JPG
Example 2:
Constraints:
• The number of nodes in the tree is in the range
•
1161. Maximum Level Sum of a Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.Return the smallest level
x such that the sum of all the values of nodes at level x is maximal.Example 1:
Image: https://assets.leetcode.com/uploads/2019/05/03/capture.JPG
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-10^5 <= Node.val <= 10^52023-06-16
1569. Number of Ways to Reorder Array to Get Same BST
Topic: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree
Difficulty: Hard
Problem:
Given an array
• For example, given
Return the number of ways to reorder
Since the answer may be very large, return it modulo
Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/12/bb.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/12/ex1.png
Example 3:
Image: https://assets.leetcode.com/uploads/2020/08/12/ex4.png
Constraints:
•
•
• All integers in
1569. Number of Ways to Reorder Array to Get Same BST
Topic: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree
Difficulty: Hard
Problem:
Given an array
nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.• For example, given
nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.Return the number of ways to reorder
nums such that the BST formed is identical to the original BST formed from nums.Since the answer may be very large, return it modulo
10^9 + 7.Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/12/bb.png
Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/12/ex1.png
Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST:
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
Example 3:
Image: https://assets.leetcode.com/uploads/2020/08/12/ex4.png
Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.
Constraints:
•
1 <= nums.length <= 1000•
1 <= nums[i] <= nums.length• All integers in
nums are distinct.2023-06-17
1187. Make Array Strictly Increasing
Topic: Array, Binary Search, Dynamic Programming, Sorting
Difficulty: Hard
Problem:
Given two integer arrays
In one operation, you can choose two indices
If there is no way to make
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1187. Make Array Strictly Increasing
Topic: Array, Binary Search, Dynamic Programming, Sorting
Difficulty: Hard
Problem:
Given two integer arrays
arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.In one operation, you can choose two indices
0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].If there is no way to make
arr1 strictly increasing, return -1.Example 1:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].
Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].
Example 3:
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.
Constraints:
•
1 <= arr1.length, arr2.length <= 2000•
0 <= arr1[i], arr2[i] <= 10^92023-06-18
2328. Number of Increasing Paths in a Grid
Topic: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization, Matrix
Difficulty: Hard
Problem:
You are given an
Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo
Two paths are considered different if they do not have exactly the same sequence of visited cells.
Example 1:
Image: https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png
Example 2:
Constraints:
•
•
•
•
•
2328. Number of Increasing Paths in a Grid
Topic: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization, Matrix
Difficulty: Hard
Problem:
You are given an
m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo
10^9 + 7.Two paths are considered different if they do not have exactly the same sequence of visited cells.
Example 1:
Image: https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png
Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].
- Paths with length 3: [1 -> 3 -> 4].
The total number of paths is 4 + 3 + 1 = 8.
Example 2:
Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -> 2].
The total number of paths is 2 + 1 = 3.
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 1000•
1 <= m * n <= 10^5•
1 <= grid[i][j] <= 10^52023-06-19
1732. Find the Highest Altitude
Topic: Array, Prefix Sum
Difficulty: Easy
Problem:
There is a biker going on a road trip. The road trip consists of
You are given an integer array
Example 1:
Example 2:
Constraints:
•
•
•
1732. Find the Highest Altitude
Topic: Array, Prefix Sum
Difficulty: Easy
Problem:
There is a biker going on a road trip. The road trip consists of
n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.You are given an integer array
gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.Example 1:
Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
Constraints:
•
n == gain.length•
1 <= n <= 100•
-100 <= gain[i] <= 1002023-06-20
2090. K Radius Subarray Averages
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
You are given a 0-indexed array
The k-radius average for a subarray of
Build and return an array
The average of
• For example, the average of four elements
Example 1:
Image: https://assets.leetcode.com/uploads/2021/11/07/eg1.png
Example 2:
Example 3:
Constraints:
•
•
•
2090. K Radius Subarray Averages
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
You are given a 0-indexed array
nums of n integers, and an integer k.The k-radius average for a subarray of
nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.Build and return an array
avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.The average of
x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.• For example, the average of four elements
2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.Example 1:
Image: https://assets.leetcode.com/uploads/2021/11/07/eg1.png
Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.
Example 2:
Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
avg[0] = 100000 / 1 = 100000.
Example 3:
Input: nums = [8], k = 100000
Output: [-1]
Explanation:
- avg[0] is -1 because there are less than k elements before and after index 0.
Constraints:
•
n == nums.length•
1 <= n <= 10^5•
0 <= nums[i], k <= 10^52023-06-21
2448. Minimum Cost to Make Array Equal
Topic: Array, Binary Search, Greedy, Sorting, Prefix Sum
Difficulty: Hard
Problem:
You are given two 0-indexed arrays
You can do the following operation any number of times:
• Increase or decrease any element of the array
The cost of doing one operation on the
Return the minimum total cost such that all the elements of the array
Example 1:
Example 2:
Constraints:
•
•
•
2448. Minimum Cost to Make Array Equal
Topic: Array, Binary Search, Greedy, Sorting, Prefix Sum
Difficulty: Hard
Problem:
You are given two 0-indexed arrays
nums and cost consisting each of n positive integers.You can do the following operation any number of times:
• Increase or decrease any element of the array
nums by 1.The cost of doing one operation on the
i^th element is cost[i].Return the minimum total cost such that all the elements of the array
nums become equal.Example 1:
Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:
- Increase the 0^th element one time. The cost is 2.
- Decrease the 1^st element one time. The cost is 3.
- Decrease the 2^nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.
Example 2:
Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.
Constraints:
•
n == nums.length == cost.length•
1 <= n <= 10^5•
1 <= nums[i], cost[i] <= 10^62023-06-22
714. Best Time to Buy and Sell Stock with Transaction Fee
Topic: Array, Dynamic Programming, Greedy
Difficulty: Medium
Problem:
You are given an array
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Example 2:
Constraints:
•
•
•
714. Best Time to Buy and Sell Stock with Transaction Fee
Topic: Array, Dynamic Programming, Greedy
Difficulty: Medium
Problem:
You are given an array
prices where prices[i] is the price of a given stock on the i^th day, and an integer fee representing a transaction fee.Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Constraints:
•
1 <= prices.length <= 5 * 10^4•
1 <= prices[i] < 5 * 10^4•
0 <= fee < 5 * 10^42023-06-23
1027. Longest Arithmetic Subsequence
Topic: Array, Hash Table, Binary Search, Dynamic Programming
Difficulty: Medium
Problem:
Given an array
Note that:
• A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
• A sequence
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1027. Longest Arithmetic Subsequence
Topic: Array, Hash Table, Binary Search, Dynamic Programming
Difficulty: Medium
Problem:
Given an array
nums of integers, return the length of the longest arithmetic subsequence in nums.Note that:
• A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
• A sequence
seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).Example 1:
Input: nums = [3,6,9,12]
Output: 4
Explanation: The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: nums = [9,4,7,2,10]
Output: 3
Explanation: The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation: The longest arithmetic subsequence is [20,15,10,5].
Constraints:
•
2 <= nums.length <= 1000•
0 <= nums[i] <= 5002023-06-24
956. Tallest Billboard
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You are given a collection of
Return the largest possible height of your billboard installation. If you cannot support the billboard, return
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
956. Tallest Billboard
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You are given a collection of
rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.Return the largest possible height of your billboard installation. If you cannot support the billboard, return
0.Example 1:
Input: rods = [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:
Input: rods = [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Example 3:
Input: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.
Constraints:
•
1 <= rods.length <= 20•
1 <= rods[i] <= 1000•
sum(rods[i]) <= 50002023-06-25
1575. Count All Possible Routes
Topic: Array, Dynamic Programming, Memoization
Difficulty: Hard
Problem:
You are given an array of distinct positive integers locations where
At each step, if you are at city
Notice that
Return the count of all possible routes from
Example 1:
Example 2:
Example 3:
Constraints:
•
•
• All integers in
•
•
1575. Count All Possible Routes
Topic: Array, Dynamic Programming, Memoization
Difficulty: Hard
Problem:
You are given an array of distinct positive integers locations where
locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.At each step, if you are at city
i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.Notice that
fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).Return the count of all possible routes from
start to finish. Since the answer may be too large, return it modulo 10^9 + 7.Example 1:
Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3
Example 2:
Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5
Example 3:
Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.
Constraints:
•
2 <= locations.length <= 100•
1 <= locations[i] <= 10^9• All integers in
locations are distinct.•
0 <= start, finish < locations.length•
1 <= fuel <= 2002023-06-26
2462. Total Cost to Hire K Workers
Topic: Array, Two Pointers, Heap (Priority Queue), Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
You are also given two integers
• You will run
• In each hiring session, choose the worker with the lowest cost from either the first
• For example, if
• In the second hiring session, we will choose
• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
• A worker can only be chosen once.
Return the total cost to hire exactly
Example 1:
Example 2:
Constraints:
•
•
•
2462. Total Cost to Hire K Workers
Topic: Array, Two Pointers, Heap (Priority Queue), Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
costs where costs[i] is the cost of hiring the i^th worker.You are also given two integers
k and candidates. We want to hire exactly k workers according to the following rules:• You will run
k sessions and hire exactly one worker in each session.• In each hiring session, choose the worker with the lowest cost from either the first
candidates workers or the last candidates workers. Break the tie by the smallest index.• For example, if
costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4^th worker because they have the lowest cost [3,2,7,7,1,2].• In the second hiring session, we will choose
1^st worker because they have the same lowest cost as 4^th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
• A worker can only be chosen once.
Return the total cost to hire exactly
k workers.Example 1:
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.
Example 2:
Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.
Constraints:
•
1 <= costs.length <= 10^5•
1 <= costs[i] <= 10^5•
1 <= k, candidates <= costs.length