2025-02-26
1749. Maximum Absolute Sum of Any Subarray

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You are given an integer array nums. The absolute sum of a subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] is abs(nums_l + nums_l+1 + ... + nums_r-1 + nums_r).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

Constraints:

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

2025-02-27
873. Length of Longest Fibonacci Subsequence

Topic: Array, Hash Table, Dynamic Programming
Difficulty: Medium

Problem:
A sequence x_1, x_2, ..., x_n is Fibonacci-like if:

• n >= 3
• x_i + x_i+1 == x_i+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints:

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

2025-02-28
1092. Shortest Common Supersequence

Topic: String, Dynamic Programming
Difficulty: Hard

Problem:
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

2025-03-01
2460. Apply Operations to an Array

Topic: Array, Two Pointers, Simulation
Difficulty: Easy

Problem:
You are given a 0-indexed array nums of size n consisting of non-negative integers.

You need to apply n - 1 operations to this array where, in the i^th operation (0-indexed), you will apply the following on the i^th element of nums:

• If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.

After performing all the operations, shift all the 0's to the end of the array.

• For example, the array [1,0,2,0,0,1] after shifting all its 0's to the end, is [1,2,1,0,0,0].

Return the resulting array.

Note that the operations are applied sequentially, not all at once.

Example 1:

Input: nums = [1,2,2,1,1,0]
Output: [1,4,2,0,0,0]
Explanation: We do the following operations:
- i = 0: nums[0] and nums[1] are not equal, so we skip this operation.
- i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4,0,1,1,0].
- i = 2: nums[2] and nums[3] are not equal, so we skip this operation.
- i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2,0,0].
- i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0,0].
After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].

Example 2:

Input: nums = [0,1]
Output: [1,0]
Explanation: No operation can be applied, we just shift the 0 to the end.

Constraints:

• 2 <= nums.length <= 2000
• 0 <= nums[i] <= 1000

2025-03-02
2570. Merge Two 2D Arrays by Summing Values

Topic: Array, Hash Table, Two Pointers
Difficulty: Easy

Problem:
You are given two 2D integer arrays nums1 and nums2.

• nums1[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.
• nums2[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

• Only ids that appear in at least one of the two arrays should be included in the resulting array.
• Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays, then assume its value in that array to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

Constraints:

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= id_i, val_i <= 1000
• Both arrays contain unique ids.
• Both arrays are in strictly ascending order by id.

2025-03-03
2161. Partition Array According to Given Pivot

Topic: Array, Two Pointers, Simulation
Difficulty: Medium

Problem:
You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

• Every element less than pivot appears before every element greater than pivot.
• Every element equal to pivot appears in between the elements less than and greater than pivot.
• The relative order of the elements less than pivot and the elements greater than pivot is maintained.
• More formally, consider every p_i, p_j where p_i is the new position of the i^th element and p_j is the new position of the j^th element. If i < j and both elements are smaller (or larger) than pivot, then p_i < p_j.

Return nums after the rearrangement.

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation: 
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.
The elements 12 and 14 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation: 
The element -3 is less than the pivot so it is on the left side of the array.
The elements 4 and 3 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

Constraints:

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot equals to an element of nums.

2025-03-04
1780. Check if Number is a Sum of Powers of Three

Topic: Math
Difficulty: Medium

Problem:
Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3^x.

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3^1 + 3^2

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3^0 + 3^2 + 3^4

Example 3:

Input: n = 21
Output: false

Constraints:

• 1 <= n <= 10^7

2025-03-05
2579. Count Total Number of Colored Cells

Topic: Math
Difficulty: Medium

Problem:
There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer n, indicating that you must do the following routine for n minutes:

• At the first minute, color any arbitrary unit cell blue.
• Every minute thereafter, color blue every uncolored cell that touches a blue cell.

Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.

Image: https://assets.leetcode.com/uploads/2023/01/10/example-copy-2.png

Return the number of colored cells at the end of n minutes.

Example 1:

Input: n = 1
Output: 1
Explanation: After 1 minute, there is only 1 blue cell, so we return 1.

Example 2:

Input: n = 2
Output: 5
Explanation: After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5.

Constraints:

• 1 <= n <= 10^5

2025-03-06
2965. Find Missing and Repeated Values

Topic: Array, Hash Table, Math, Matrix
Difficulty: Easy

Problem:
You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n^2]. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.

Return a 0-indexed integer array ans of size 2 where ans[0] equals to a and ans[1] equals to b.

Example 1:

Input: grid = [[1,3],[2,2]]
Output: [2,4]
Explanation: Number 2 is repeated and number 4 is missing so the answer is [2,4].

Example 2:

Input: grid = [[9,1,7],[8,9,2],[3,4,6]]
Output: [9,5]
Explanation: Number 9 is repeated and number 5 is missing so the answer is [9,5].

Constraints:

• 2 <= n == grid.length == grid[i].length <= 50
• 1 <= grid[i][j] <= n * n
• For all x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.
• For all x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.
• For all x that 1 <= x <= n * n except two of them there is exatly one pair of i, j that 0 <= i, j <= n - 1 and grid[i][j] == x.

2025-03-07
2523. Closest Prime Numbers in Range

Topic: Math, Number Theory
Difficulty: Medium

Problem:
Given two positive integers left and right, find the two integers num1 and num2 such that:

• left <= num1 < num2 <= right .
• Both num1 and num2 are prime numbers.
• num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

• 1 <= left <= right <= 10^6

2025-03-08
2379. Minimum Recolors to Get K Consecutive Black Blocks

Topic: String, Sliding Window
Difficulty: Easy

Problem:
You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the i^th block. The characters 'W' and 'B' denote the colors white and black, respectively.

You are also given an integer k, which is the desired number of consecutive black blocks.

In one operation, you can recolor a white block such that it becomes a black block.

Return the minimum number of operations needed such that there is at least one occurrence of k consecutive black blocks.

Example 1:

Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks
so that blocks = "BBBBBBBWBW". 
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.

Example 2:

Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation:
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.

Constraints:

• n == blocks.length
• 1 <= n <= 100
• blocks[i] is either 'W' or 'B'.
• 1 <= k <= n

2025-03-09
3208. Alternating Groups II

Topic: Array, Sliding Window
Difficulty: Medium

Problem:
There is a circle of red and blue tiles. You are given an array of integers colors and an integer k. The color of tile i is represented by colors[i]:

• colors[i] == 0 means that tile i is red.
• colors[i] == 1 means that tile i is blue.

An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).

Return the number of alternating groups.

Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.

Example 1:

Input: colors = 0,1,0,1,0, k = 3

Output: 3

Explanation:

Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183519.png

Alternating groups:

Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182448.png

Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182844.png

Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-183057.png

Example 2:

Input: colors = 0,1,0,0,1,0,1, k = 6

Output: 2

Explanation:

Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183907.png

Alternating groups:

Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184128.png

Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184240.png

Example 3:

Input: colors = 1,1,0,1, k = 4

Output: 0

Explanation:

Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184516.png

Constraints:

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

2025-03-10
3306. Count of Substrings Containing Every Vowel and K Consonants II

Topic: Hash Table, String, Sliding Window
Difficulty: Medium

Problem:
You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

• word[0..5], which is "ieaouq".
• word[6..11], which is "qieaou".
• word[7..12], which is "ieaouq".

Constraints:

• 5 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.
• 0 <= k <= word.length - 5

2025-03-11
1358. Number of Substrings Containing All Three Characters

Topic: Hash Table, String, Sliding Window
Difficulty: Medium

Problem:
Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

• 3 <= s.length <= 5 x 10^4
• s only consists of a, b or c characters.

2025-03-12
2529. Maximum Count of Positive Integer and Negative Integer

Topic: Array, Binary Search, Counting
Difficulty: Easy

Problem:
Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

• In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note that 0 is neither positive nor negative.

Example 1:

Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.

Example 2:

Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.

Example 3:

Input: nums = [5,20,66,1314]
Output: 4
Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.

Constraints:

• 1 <= nums.length <= 2000
• -2000 <= nums[i] <= 2000
• nums is sorted in a non-decreasing order.

Follow up: Can you solve the problem in O(log(n)) time complexity?

2025-03-13
3356. Zero Array Transformation II

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

Problem:
You are given an integer array nums of length n and a 2D array queries where queries[i] = [l_i, r_i, val_i].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [l_i, r_i] in nums by at most val_i.
• The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

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

Output: 2

Explanation:

• For i = 0 (l = 0, r = 2, val = 1):
• Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
• The array will become [1, 0, 1].
• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
• The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

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

Output: -1

Explanation:

• For i = 0 (l = 1, r = 3, val = 2):
• Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
• The array will become [4, 1, 0, 0].
• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
• The array will become [3, 0, 0, 0], which is not a Zero Array.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 5 * 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 3
• 0 <= l_i <= r_i < nums.length
• 1 <= val_i <= 5

2025-03-14
2226. Maximum Candies Allocated to K Children

Topic: Array, Binary Search
Difficulty: Medium

Problem:
You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

• 1 <= candies.length <= 10^5
• 1 <= candies[i] <= 10^7
• 1 <= k <= 10^12

2025-03-15
2560. House Robber IV

Topic: Array, Binary Search
Difficulty: Medium

Problem:
There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array nums representing how much money is stashed in each house. More formally, the i^th house from the left has nums[i] dollars.

You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.

Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

Example 1:

Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation: 
There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.

Example 2:

Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= (nums.length + 1)/2

2025-03-17
2206. Divide Array Into Equal Pairs

Topic: Array, Hash Table, Bit Manipulation, Counting
Difficulty: Easy

Problem:
You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

• nums.length == 2 * n
• 1 <= n <= 500
• 1 <= nums[i] <= 500

2025-03-18
2401. Longest Nice Subarray

Topic: Array, Bit Manipulation, Sliding Window
Difficulty: Medium

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

We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

Return the length of the longest nice subarray.

A subarray is a contiguous part of an array.

Note that subarrays of length 1 are always considered nice.

Example 1:

Input: nums = [1,3,8,48,10]
Output: 3
Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.

Example 2:

Input: nums = [3,1,5,11,13]
Output: 1
Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

Constraints:

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