2024-11-28
2290. Minimum Obstacle Removal to Reach Corner

Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard

Problem:
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

• 0 represents an empty cell,
• 1 represents an obstacle that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).

Example 1:

Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10^5
• 2 <= m * n <= 10^5
• grid[i][j] is either 0 or 1.
• grid[0][0] == grid[m - 1][n - 1] == 0

2024-11-29
2577. Minimum Time to Visit a Cell In a Grid

Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard

Problem:
You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0^th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

Example 1:

Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-8.png

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

Example 2:

Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-9.png

Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: There is no path from the top left to the bottom-right cell.

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 0 <= grid[i][j] <= 10^5
• grid[0][0] == 0

.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0;
}
.spoiler {overflow:hidden;}
.spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
.spoilerbuttonvalue="Show Message" + .spoiler > div {margin-top:-500%;}
.spoilerbuttonvalue="Hide Message" + .spoiler {padding:5px;}

2024-11-30
2097. Valid Arrangement of Pairs

Topic: Depth-First Search, Graph, Eulerian Circuit
Difficulty: Hard

Problem:
You are given a 0-indexed 2D integer array pairs where pairs[i] = [start_i, end_i]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have end_i-1 == start_i.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 9 == 9 = start_1 
end_1 = 4 == 4 = start_2
end_2 = 5 == 5 = start_3

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 3 == 3 = start_1
end_1 = 2 == 2 = start_2
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 2 == 2 = start_1
end_1 = 1 == 1 = start_2

Constraints:

• 1 <= pairs.length <= 10^5
• pairs[i].length == 2
• 0 <= start_i, end_i <= 10^9
• start_i != end_i
• No two pairs are exactly the same.
• There exists a valid arrangement of pairs.

2024-12-01
1346. Check If N and Its Double Exist

Topic: Array, Hash Table, Two Pointers, Binary Search, Sorting
Difficulty: Easy

Problem:
Given an array arr of integers, check if there exist two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

2024-12-02
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Topic: Two Pointers, String, String Matching
Difficulty: Easy

Problem:
Given a sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

2024-12-03
2109. Adding Spaces to a String

Topic: Array, Two Pointers, String, Simulation
Difficulty: Medium

Problem:
You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

• For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Return the modified string after the spaces have been added.

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation: 
The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".
We then place spaces before those characters.

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"
Explanation:
We are also able to place spaces before the first character of the string.

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists only of lowercase and uppercase English letters.
• 1 <= spaces.length <= 3 * 10^5
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

2024-12-04
2825. Make String a Subsequence Using Cyclic Increments

Topic: Two Pointers, String
Difficulty: Medium

Problem:
You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'. 
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1. 
Increment str1[0] to become 'a'. 
Increment str1[1] to become 'd'. 
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. 
Therefore, false is returned.

Constraints:

• 1 <= str1.length <= 10^5
• 1 <= str2.length <= 10^5
• str1 and str2 consist of only lowercase English letters.

2024-12-05
2337. Move Pieces to Obtain a String

Topic: Two Pointers, String
Difficulty: Medium

Problem:
You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.

Example 1:

Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "L______RR".
Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

Example 3:

Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

Constraints:

• n == start.length == target.length
• 1 <= n <= 10^5
• start and target consist of the characters 'L', 'R', and '_'.

2024-12-06
2554. Maximum Number of Integers to Choose From a Range I

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

Problem:
You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

• The chosen integers have to be in the range [1, n].
• Each integer can be chosen at most once.
• The chosen integers should not be in the array banned.
• The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints:

• 1 <= banned.length <= 10^4
• 1 <= banned[i], n <= 10^4
• 1 <= maxSum <= 10^9

2024-12-07
1760. Minimum Limit of Balls in a Bag

Topic: Array, Binary Search
Difficulty: Medium

Problem:
You are given an integer array nums where the i^th bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

• Take any bag of balls and divide it into two new bags with a positive number of balls.
• For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Example 1:

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= maxOperations, nums[i] <= 10^9

2024-12-08
2054. Two Best Non-Overlapping Events

Topic: Array, Binary Search, Dynamic Programming, Sorting, Heap (Priority Queue)
Difficulty: Medium

Problem:
You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i^th event starts at startTime_i and ends at endTime_i, and if you attend this event, you will receive a value of value_i. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/09/21/picture5.png

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/09/21/picture1.png

Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

Image: https://assets.leetcode.com/uploads/2021/09/21/picture3.png

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

Constraints:

• 2 <= events.length <= 10^5
• events[i].length == 3
• 1 <= startTime_i <= endTime_i <= 10^9
• 1 <= value_i <= 10^6

2024-12-09
3152. Special Array II

Topic: Array, Binary Search, Prefix Sum
Difficulty: Medium

Problem:
An array is considered special if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [from_i, to_i] your task is to check that subarray nums[from_i..to_i] is special or not.

Return an array of booleans answer such that answer[i] is true if nums[from_i..to_i] is special.

Example 1:

Input: nums = 3,4,1,2,6, queries = [0,4]

Output: false

Explanation:

The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:

Input: nums = 4,3,1,6, queries = [0,2,2,3]

Output: false,true

Explanation:

1. The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
2. The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

2024-12-10
2981. Find Longest Special Substring That Occurs Thrice I

Topic: Hash Table, String, Binary Search, Sliding Window, Counting
Difficulty: Medium

Problem:
You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

Constraints:

• 3 <= s.length <= 50
• s consists of only lowercase English letters.

2024-12-11
2779. Maximum Beauty of an Array After Applying Operation

Topic: Array, Binary Search, Sliding Window, Sorting
Difficulty: Medium

Problem:
You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

• Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].
• Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].

The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return the maximum possible beauty of the array nums after applying the operation any number of times.

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

Example 1:

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:
- Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
- Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: In this example we don't have to apply any operations.
The beauty of the array nums is 4 (whole array).

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i], k <= 10^5

2024-12-12
2558. Take Gifts From the Richest Pile

Topic: Array, Heap (Priority Queue), Simulation
Difficulty: Easy

Problem:
You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

• Choose the pile with the maximum number of gifts.
• If there is more than one pile with the maximum number of gifts, choose any.
• Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

Constraints:

• 1 <= gifts.length <= 10^3
• 1 <= gifts[i] <= 10^9
• 1 <= k <= 10^3

2024-12-13
2593. Find Score of an Array After Marking All Elements

Topic: Array, Hash Table, Sorting, Heap (Priority Queue), Simulation
Difficulty: Medium

Problem:
You are given an array nums consisting of positive integers.

Starting with score = 0, apply the following algorithm:

• Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
• Add the value of the chosen integer to score.
• Mark the chosen element and its two adjacent elements if they exist.
• Repeat until all the array elements are marked.

Return the score you get after applying the above algorithm.

Example 1:

Input: nums = [2,1,3,4,5,2]
Output: 7
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2].
- 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2].
- 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2].
Our score is 1 + 2 + 4 = 7.

Example 2:

Input: nums = [2,3,5,1,3,2]
Output: 5
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2].
- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2].
- 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2].
Our score is 1 + 2 + 2 = 5.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

2024-12-14
2762. Continuous Subarrays

Topic: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue
Difficulty: Medium

Problem:
You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i_1, i_2 <= j, 0 <= |nums[i_1] - nums[i_2]| <= 2.

Return the total number of continuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation: 
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
Thereare no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation: 
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

2024-12-15
1792. Maximum Average Pass Ratio

Topic: Array, Greedy, Heap (Priority Queue)
Difficulty: Medium

Problem:
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= pass_i <= total_i <= 10^5
• 1 <= extraStudents <= 10^5

2024-12-16
3264. Final Array State After K Multiplication Operations I

Topic: Array, Math, Heap (Priority Queue), Simulation
Difficulty: Easy

Problem:
You are given an integer array nums, an integer k, and an integer multiplier.

You need to perform k operations on nums. In each operation:

• Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
• Replace the selected minimum value x with x * multiplier.

Return an integer array denoting the final state of nums after performing all k operations.

Example 1:

Input: nums = 2,1,3,5,6, k = 5, multiplier = 2

Output: 8,4,6,5,6

Explanation:

OperationResultAfter operation 12, 2, 3, 5, 6After operation 24, 2, 3, 5, 6After operation 34, 4, 3, 5, 6After operation 44, 4, 6, 5, 6After operation 58, 4, 6, 5, 6

Example 2:

Input: nums = 1,2, k = 3, multiplier = 4

Output: 16,8

Explanation:

OperationResultAfter operation 14, 2After operation 24, 8After operation 316, 8

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

2024-12-17
2182. Construct String With Repeat Limit

Topic: Hash Table, String, Greedy, Heap (Priority Queue), Counting
Difficulty: Medium

Problem:
You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

• 1 <= repeatLimit <= s.length <= 10^5
• s consists of lowercase English letters.