DEV Community: MD ARIFUL HAQUE

3702. Longest Subsequence With Non-Zero Bitwise XOR

MD ARIFUL HAQUE — Sat, 15 Aug 2026 16:28:14 +0000

3702. Longest Subsequence With Non-Zero Bitwise XOR

Difficulty: Medium

Topics: Senior, Array, Bit Manipulation, Weekly Contest 470

You are given an integer array nums.

Return the length of the longest subsequence¹ in nums whose bitwise XOR is non-zero. If no such subsequence exists, return 0.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: One longest subsequence is [2, 3]. The bitwise XOR is computed as 2 XOR 3 = 1, which is non-zero.

Example 2:

Input: nums = [2,3,4]
Output: 3
Explanation: The longest subsequence is [2, 3, 4]. The bitwise XOR is computed as 2 XOR 3 XOR 4 = 5, which is non-zero.

Example 3:

Input: nums = [0,0,0]
Output: 0

Example 4:

Input: nums = [5]
Output: 1

Example 5:

Input: nums = [0,5]
Output: 2

Example 6:

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

Example 7:

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

Example 8:

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

Example 9:

Input: nums = [0]
Output: 0

Example 10:

Input: nums = [10, 10, 0]
Output: 2

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Hint:

What happens if you take the entire array?
If the XOR of the entire array is 0, can removing one element help?
What if all elements are 0?

Solution:

We solve the problem by first checking the XOR of the entire array. If it's already non‑zero, the whole array is the longest subsequence. If it's zero, we check if all elements are zero (return 0), otherwise we can remove exactly one non‑zero element to make the XOR non‑zero, yielding length n-1. This approach runs in O(n) time.

Approach

Compute the XOR of all elements in nums (totalXor).
If totalXor is non‑zero, the entire array is a valid subsequence → return n.
If totalXor is zero, then we need to see if we can obtain a non‑zero XOR by deleting elements.
First, check if all elements are zero → every subsequence XOR will be zero → return 0.
Otherwise, since the XOR of the whole array is zero, removing any element x gives new XOR = 0 XOR x = x.
If we remove a non‑zero element, the new XOR becomes non‑zero, and the subsequence length becomes n-1.
Since n-1 is the maximum possible length under a zero total XOR (we cannot keep all n), we return n-1.

Let's implement this solution in PHP: 3702. Longest Subsequence With Non-Zero Bitwise XOR

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSubsequence(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo longestSubsequence([1,2,3]) .  "\n";       // Output: 2
echo longestSubsequence([2,3,4]) .  "\n";       // Output: 3
echo longestSubsequence([0,0,0]) .  "\n";       // Output: 0
echo longestSubsequence([5]) .  "\n";           // Output: 1
echo longestSubsequence([0,5]) .  "\n";         // Output: 2
echo longestSubsequence([7,7]) .  "\n";         // Output: 1
echo longestSubsequence([1,2,3,4]) .  "\n";     // Output: 4
echo longestSubsequence([1,1]) .  "\n";         // Output: 1
echo longestSubsequence([0]) .  "\n";           // Output: 0
echo longestSubsequence([10, 10, 0]) .  "\n";   // Output: 2
?>

Explanation:

Key insight: For any array, the XOR of all elements determines the answer immediately.
Case 1: totalXor ≠ 0 → the whole array itself is a valid subsequence, so the longest length is n.
Case 2: totalXor = 0 and all elements are zero → every subsequence XOR is zero, so answer is 0.
Case 3: totalXor = 0 but there is at least one non‑zero element. Removing that non‑zero element yields a new XOR equal to that element (non‑zero). The resulting subsequence has length n-1. It is impossible to have length n because that would give XOR 0. So n-1 is optimal.
We only need a single pass to compute XOR and check for zero/non‑zero elements.

Complexity Analysis

Time complexity: O(n) — we iterate through the array at most twice.
Space complexity: O(1) — only a few integer variables used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Subsequence: A subsequence is a non-empty array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. ↩

3090. Maximum Length Substring With Two Occurrences

MD ARIFUL HAQUE — Fri, 14 Aug 2026 20:35:36 +0000

3090. Maximum Length Substring With Two Occurrences

Difficulty: Easy

Topics: Mid Level, Hash Table, String, Sliding Window, Weekly Contest 390

Given a string s, return the maximum length of a substring¹ such that it contains at most two occurrences of each character.

Example 1:

Input: s = "bcbbbcba"
Output: 4
Explanation: The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".

Example 2:

Input: s = "aaaa"
Output: 2
Explanation: The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".

Example 3:

Input: s = "abc"
Output: 3

Example 4:

Input: s = "aabbcc"
Output: 6

Example 5:

Input: s = "ababab"
Output: 4

Example 6:

Input: s = "a"
Output: 1

Example 7:

Input: s = "zzzzz"
Output: 2

Example 8:

Input: s = "abcabc"
Output: 6

Example 9:

Input: s = "abcaabc"
Output: 5

Constraints:

2 <= s.length <= 100
s consists only of lowercase English letters.

Hint:

We can try all substrings by brute-force since the constraints are very small.

Solution:

We determined the optimal solution by leveraging the small input constraint (n ≤ 100) to evaluate every possible substring, tracking character frequencies, and stopping extension as soon as any character exceeds the allowed two occurrences.

Approach

Brute‑force over all substrings – Since the string length is at most 100, we can safely check every start and end index.
Frequency array – Maintain a count of each character (26 lowercase letters) for the current substring.
Early termination – As we extend the substring by one character, if that character’s count becomes 3, we break because adding more characters cannot fix the violation.
Update maximum – Before breaking or after each valid extension, update the answer with the current substring length.

Let's implement this solution in PHP: 3090. Maximum Length Substring With Two Occurrences

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLengthSubstring(string $s): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLengthSubstring("bcbbbcba") .  "\n";            // Output: 4
echo maximumLengthSubstring("aaaa") .  "\n";                // Output: 2
echo maximumLengthSubstring("abc") .  "\n";                 // Output: 3
echo maximumLengthSubstring("aabbcc") .  "\n";              // Output: 6
echo maximumLengthSubstring("ababab") .  "\n";              // Output: 4
echo maximumLengthSubstring("a") .  "\n";                   // Output: 1
echo maximumLengthSubstring("zzzzz") .  "\n";               // Output: 2
echo maximumLengthSubstring("abcabc") .  "\n";              // Output: 6
echo maximumLengthSubstring("abcaabc") .  "\n";             // Output: 5
?>

Explanation:

Outer loop ($i) defines the starting index of the substring.
Inner loop ($j) defines the ending index, expanding one character at a time.
For each new character, increment its frequency.
If the frequency of any character exceeds 2, the inner loop stops (no longer valid substring starting from $i with this $j).
Otherwise, the current substring is valid, so we update $maxLen with $j - $i + 1.
After the loops finish, $maxLen holds the length of the longest valid substring.

Complexity Analysis

Time Complexity: O(n²) – For each start (n), we may iterate up to the end (n), so worst-case ~10,000 operations for n=100, which is trivial.
Space Complexity: O(1) – We only use a fixed-size array of 26 integers regardless of input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Substring: A substring is a contiguous sequence of characters within a string. ↩

2213. Longest Substring of One Repeating Character

MD ARIFUL HAQUE — Thu, 13 Aug 2026 17:36:30 +0000

2213. Longest Substring of One Repeating Character

Difficulty: Hard

Topics: Senior Staff, Array, String, Segment Tree, Ordered Set, Weekly Contest 285

You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.

The iᵗʰ query updates the character in s at index queryIndices[i] to the character queryCharacters[i].

Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the iᵗʰ query is performed.

Example 1:

Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output: [3,3,4]
Explanation:
- 1ˢᵗ query updates s = "b*b*bacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2ⁿᵈ query updates s = "bbbccc".
- The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3ʳᵈ query updates s = "bbb*b*cc". The longest substring consisting of one repeating character is "bbbb" with length 4.
- Thus, we return [3,3,4].

Example 2:

Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
Output: [2,3]
Explanation:
- 1ˢᵗ query updates s = "ab*a*zz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2ⁿᵈ query updates s = "a*a*azz". The longest substring consisting of one repeating character is "aaa" with length 3.
- Thus, we return [2,3].

Example 3:

Input: s = "a", queryCharacters = "b", queryIndices = [0]
Output: [1]

Example 4:

Input: s = "aaaa", queryCharacters = "b", queryIndices = [2]
Output: [2]

Example 5:

Input: s = "abc", queryCharacters = "a", queryIndices = [0]
Output: [1]

Example 6:

Input: s = "ababab", queryCharacters = "a", queryIndices = [1]
Output: [2]

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
k == queryCharacters.length == queryIndices.length
1 <= k <= 10⁵
queryCharacters consists of lowercase English letters.
0 <= queryIndices[i] < s.length

Hint:

Use a segment tree to perform fast point updates and range queries.
We need each segment tree node to store the length of the longest substring of that segment consisting of only 1 repeating character.
We will also have each segment tree node store the leftmost and rightmost character of the segment, the max length of a prefix substring consisting of only 1 repeating character, and the max length of a suffix substring consisting of only 1 repeating character.
Use this information to properly merge the two segment tree nodes together.

Solution:

We implement a segment tree solution to efficiently handle point updates and range queries for finding the longest substring of identical characters after each update. The segment tree stores five key pieces of information per node: leftmost character, rightmost character, longest prefix length, longest suffix length, and the overall maximum length. By merging child nodes with careful boundary checks, we maintain the correct state after each character update in O(log n) time.

Approach

Segment Tree Design: Each node represents a segment of the string and stores comprehensive information to determine the longest run of identical characters within that segment.
Node Information: For each segment, we store:
- Leftmost character (treeLeftChar)
- Rightmost character (treeRightChar)
- Longest prefix of identical characters (treePrefix)
- Longest suffix of identical characters (treeSuffix)
- Longest substring of identical characters (treeMax)
Build Phase: Recursively construct the segment tree from the initial string, setting leaf nodes with value 1 for all fields.
Merge Operation: When combining two child segments, we:
- Determine if the prefix extends across the boundary when the right child's leftmost char matches the left child's rightmost char
- Similarly compute suffix extension across the boundary
- Calculate the maximum run that crosses the boundary by adding suffix of left child and prefix of right child
Update Phase: Perform point updates by traversing to the leaf, updating it, then merging back up the tree.
Query Response: After each update, the answer is simply treeMax[1] (the root node's maximum).

Let's implement this solution in PHP: 2213. Longest Substring of One Repeating Character

<?php
/**
 * @param String $s
 * @param String $queryCharacters
 * @param Integer[] $queryIndices
 * @return Integer[]
 */
function longestRepeating(string $s, string $queryCharacters, array $queryIndices): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Build segment tree
 * 
 * @param $node
 * @param $l
 * @param $r
 * @param $s
 * @param $treeLeftChar
 * @param $treeRightChar
 * @param $treePrefix
 * @param $treeSuffix
 * @param $treeMax
 * @return void
 */
function build($node, $l, $r, $s, &$treeLeftChar, &$treeRightChar, &$treePrefix, &$treeSuffix, &$treeMax): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Merge two child nodes
 * 
 * @param $node
 * @param $l
 * @param $mid
 * @param $r
 * @param $treeLeftChar
 * @param $treeRightChar
 * @param $treePrefix
 * @param $treeSuffix
 * @param $treeMax
 * @return void
 */
function merge($node, $l, $mid, $r, &$treeLeftChar, &$treeRightChar, &$treePrefix, &$treeSuffix, &$treeMax): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Update a position in the segment tree
 * 
 * @param $node
 * @param $l
 * @param $r
 * @param $idx
 * @param $char
 * @param $treeLeftChar
 * @param $treeRightChar
 * @param $treePrefix
 * @param $treeSuffix
 * @param $treeMax
 * @return void
 */
function update($node, $l, $r, $idx, $char, &$treeLeftChar, &$treeRightChar, &$treePrefix, &$treeSuffix, &$treeMax): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo longestRepeating("babacc", "bcb", [1,3,3]) .  "\n";        // Output: [3, 3, 4]
echo longestRepeating("abyzz", "aa", [2,1]) .  "\n";            // Output: [2, 3]
echo longestRepeating("a", "b", [0]) .  "\n";                   // Output: [1]
echo longestRepeating("aaaa", "b", [2]) .  "\n";                // Output: [2]
echo longestRepeating("abc", "a", [0]) .  "\n";                 // Output: [1]
echo longestRepeating("ababab", "a", [1]) .  "\n";              // Output: [2]
?>

Explanation:

Leaf Node Initialization: For a single character, all metrics are set to 1, and both left and right characters are that character.
Prefix Calculation: The prefix of the merged node is either:
- The prefix of the left child, OR
- If the entire left child is a run and its rightmost char matches the left child's rightmost char, add the prefix of the right child
Suffix Calculation: Similarly, the suffix is either:
- The suffix of the right child, OR
- If the entire right child is a run and its leftmost char matches the left child's rightmost char, add the suffix of the left child
Maximum Calculation: The maximum is:
- The maximum of the two children's maximums
- PLUS a potential crossing run: when the boundary chars match, the crossing run length = suffix of left child + prefix of right child
Efficient Updates: Each update only affects O(log n) nodes, making this approach efficient for up to 10⁵ queries.

Complexity Analysis

Time Complexity: O((n + k) log n) where n is string length and k is number of queries
- Building the tree: O(n)
- Each update: O(log n)
- Total: O(n + k log n)
Space Complexity: O(n) for the segment tree arrays (4 * n space)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2958. Length of Longest Subarray With at Most K Frequency

MD ARIFUL HAQUE — Wed, 12 Aug 2026 15:31:56 +0000

2958. Length of Longest Subarray With at Most K Frequency

Difficulty: Medium

Topics: Staff, Array, Hash Table, Sliding Window, Biweekly Contest 119

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

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

Example 1:

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation:
- The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
- It can be shown that there are no good subarrays with length more than 6.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation:
- The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
- It can be shown that there are no good subarrays with length more than 2.

Example 3:

Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation:
- The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
- It can be shown that there are no good subarrays with length more than 4.

Example 4:

Input: nums = [1,2,3,4,5], k = 1
Output: 5

Example 5:

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

Example 6:

Input: nums = [1,1,1,1], k = 4
Output: 4

Example 7:

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

Example 8:

Input: nums = [1000000000, 1000000000, 1000000000], k = 2
Output: 2

Example 9:

Input: nums = [1,2,1,3,2,1,4,3,2,1], k = 2
Output: 6

Example 10:

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

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= nums.length

Hint:

For each index i, find the rightmost index j >= i such that the frequency of each element in the subarray [i, j] is at most k.
We can use 2 pointers / sliding window to achieve it.

Solution:

We implemented a sliding window solution using two pointers to find the longest contiguous subarray where no element appears more than k times. By dynamically expanding the right pointer and shrinking the left pointer whenever a frequency constraint is violated, we maintain a valid window and track its maximum length in a single pass through the array.

Approach

Sliding Window with Two Pointers - We maintain a window [left, right] that always satisfies the "good" condition (all element frequencies ≤ k)
Frequency Tracking - Use a hash map to count occurrences of each element in the current window
Expand Window - Iterate the right pointer to include new elements
Shrink When Violated - If adding a new element makes its frequency exceed k, move the left pointer forward, decrementing frequencies, until the window becomes valid again
Track Maximum - After each valid window adjustment, compute the current window length and update the global maximum

Let's implement this solution in PHP: 2958. Length of Longest Subarray With at Most K Frequency

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maxSubarrayLength(array $nums, int $k): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxSubarrayLength([1,2,3,1,2,3,1,2], 2) .  "\n";                           // Output: 6
echo maxSubarrayLength([1,2,1,2,1,2,1,2], 1) .  "\n";                           // Output: 2
echo maxSubarrayLength([5,5,5,5,5,5,5], 4) .  "\n";                             // Output: 4
echo maxSubarrayLength([1,2,3,4,5], 1) .  "\n";                                 // Output: 5
echo maxSubarrayLength([1], 1) .  "\n";                                         // Output: 1
echo maxSubarrayLength([1,1,1,1], 4) .  "\n";                                   // Output: 4
echo maxSubarrayLength([1,1,2,2,1,1,3,3,3], 2) .  "\n";                         // Output: 6
echo maxSubarrayLength([1000000000, 1000000000, 1000000000], 2) .  "\n";        // Output: 2
echo maxSubarrayLength([1,2,1,3,2,1,4,3,2,1], 2) .  "\n";                       // Output: 6
echo maxSubarrayLength([1,1,1,1,1], 1) .  "\n";                                 // Output: 1
?>

Explanation:

Initialization: Start with left = 0, empty frequency map, and maxLength = 0
Iteration: For each right from 0 to n-1:
- Add nums[right] to the frequency map, incrementing its count
- Check if the newly added element now appears more than k times
- If violation occurs, enter a while loop:
  - Remove the element at left from the frequency map
  - Decrement its count (or unset if it reaches 0)
  - Increment left by 1
  - Continue until the violating element's frequency is ≤ k
- After ensuring the window is valid, calculate current length: right - left + 1
- Update maxLength with the larger value
Return: Final maxLength as the answer

Complexity Analysis

Time Complexity: O(n) - Each element is added to the window once and removed at most once, giving linear time
Space Complexity: O(n) - In the worst case, the frequency map may store up to n distinct elements

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

MD ARIFUL HAQUE — Tue, 11 Aug 2026 15:51:33 +0000

2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

Difficulty: Easy

Topics: Mid Level, Array, Hash Table, Sorting, Biweekly Contest 121

You are given a 0-indexed array of integers nums.

A prefix nums[0..i] is sequential if, for all 1 <= j <= i, nums[j] = nums[j - 1] + 1. In particular, the prefix consisting only of nums[0] is sequential.

Return the smallest integer x missing from nums such that x is greater than or equal to the sum of the longest sequential prefix.

Example 1:

Input: nums = [1,2,3,2,5]
Output: 6
Explanation: The longest sequential prefix of nums is [1,2,3] with a sum of 6. 6 is not in the array, therefore 6 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

Example 2:

Input: nums = [3,4,5,1,12,14,13]
Output: 15
Explanation: The longest sequential prefix of nums is [3,4,5] with a sum of 12. 12, 13, and 14 belong to the array while 15 does not. Therefore, 15 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

Example 3:

Input: nums = [5]
Output: 6

Example 4:

Input: nums = [2,3,4,5]
Output: 14

Example 5:

Input: nums = [10,11,12,20,21]
Output: 33

Example 6:

Input: nums = [1,2,4,3]
Output: 5

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 50

Hint:

To find the longest sequential prefix, iterate from left to right. For a fixed i, if nums[i] != nums[i - 1] + 1 then the longest sequential prefix ends at i - 1.

Solution:

We compute the longest prefix where each element is exactly one more than the previous. We sum that prefix. Then, starting from that sum, we keep incrementing until we find a number not present in the array, which is our answer.

Approach

Step 1 – Find longest sequential prefix
- Start with the first element as the sum and prefix length as 1.
- Iterate from index 1 onward while nums[i] == nums[i-1] + 1; add to sum and extend length.
- Stop at the first break, as the problem asks for the longest sequential prefix.
Step 2 – Find the smallest missing integer ≥ sum
- Store all array values in a hash set for O(1) lookups.
- Initialize candidate = sum.
- While candidate exists in the set, increment candidate.
- Return the first candidate not in the set.

Let's implement this solution in PHP: 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function missingInteger(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo missingInteger([1,2,3,2,5]) .  "\n";               // Output: 6
echo missingInteger([3,4,5,1,12,14,13]) .  "\n";        // Output: 15
echo missingInteger([5]) .  "\n";                       // Output: 6
echo missingInteger([2,3,4,5]) .  "\n";                 // Output: 14
echo missingInteger([10,11,12,20,21]) .  "\n";          // Output: 33
echo missingInteger([1,2,4,3]) .  "\n";                 // Output: 5
?>

Explanation:

Prefix extraction
- The prefix must start at index 0 because it is defined as nums[0..i].
- We only extend while the consecutive difference is exactly 1.
- Once the condition fails, we break – no need to check further because a longer sequential prefix cannot exist after a break.
Missing integer search
- Since we need the smallest missing integer greater than or equal to the sum, we begin checking from exactly that sum.
- Using a hash set (from array_flip) makes membership tests constant time.
- We increment until we find a value absent from the array – that value is guaranteed to be the answer.
Edge cases
- If the array is length 1, the sum is nums[0] and we check from there.
- If the sum itself is missing, we return it immediately.
- All numbers are positive and ≤ 50, so the loop will terminate quickly.

Complexity Analysis

Time complexity: O(n)
- O(n) to find the prefix sum (at most one pass).
- O(n) to build the hash set.
- The while loop increments at most (max(nums) - sum + 1) times, but in worst case with all numbers from sum to max present, it could go up to 50 – still O(50), constant relative ton ≤ 50. So overall O(n).
Space complexity: O(n) - We use a hash set of size up to n.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1510. Stone Game IV

MD ARIFUL HAQUE — Mon, 10 Aug 2026 17:32:35 +0000

1510. Stone Game IV

Difficulty: Hard

Topics: Senior Staff, Math, Dynamic Programming, Minimax, Game Theory, Nim Game, Sprague–Grundy Theorem, Zero-Sum Game, Biweekly Contest 30

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 → 1 → 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 → 0).

Example 4:

Input: n = 3
Output: true

Example 5:

Input: n = 5
Output: true

Example 6:

Input: n = 6
Output: true

Example 7:

Input: n = 7
Output: true

Example 8:

Input: n = 8
Output: true

Example 9:

Input: n = 9
Output: true

Example 10:

Input: n = 10
Output: true

Example 11:

Input: n = 11
Output: true

Example 12:

Input: n = 12
Output: true

Example 13:

Input: n = 13
Output: true

Example 14:

Input: n = 14
Output: true

Constraints:

1 <= n <= 10⁵

Hint:

Use dynamic programming to keep track of winning and losing states. Given some number of stones, Alice can win if she can force Bob onto a losing state.

Solution:

We implement a dynamic programming solution to determine if Alice can win the stone game where players can only remove perfect square numbers of stones. The solution uses bottom-up DP to evaluate winning/losing states, where a state is winning if there exists any move that leads to a losing state for the opponent. This approach efficiently handles the constraint n ≤ 10⁵ by computing each state only once.

Approach

• Dynamic Programming State Definition: dp[i] represents whether the current player can force a win with i stones remaining
• Base Case: dp[0] = false (no stones means current player loses)
• Transition: For each state i, try removing all possible perfect squares (1², 2², 3², ..., k²) where k² ≤ i
• Winning Condition: If any move j² leads to a losing state dp[i - j²] == false, then dp[i] = true
• Losing Condition: If all possible moves lead to winning states for the opponent, then dp[i] = false
• Optimization: Break early when a winning move is found to save computation

Let's implement this solution in PHP: 1510. Stone Game IV

<?php
/**
 * @param Integer $n
 * @return Boolean
 */
function winnerSquareGame(int $n): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo winnerSquareGame(1) .  "\n";   // Output: true
echo winnerSquareGame(2) .  "\n";   // Output: false
echo winnerSquareGame(4) .  "\n";   // Output: true
echo winnerSquareGame(3) .  "\n";   // Output: true
echo winnerSquareGame(5) .  "\n";   // Output: true
echo winnerSquareGame(6) .  "\n";   // Output: true
echo winnerSquareGame(7) .  "\n";   // Output: true
echo winnerSquareGame(8) .  "\n";   // Output: true
echo winnerSquareGame(9) .  "\n";   // Output: true
echo winnerSquareGame(10) .  "\n";  // Output: true
echo winnerSquareGame(11) .  "\n";  // Output: true
echo winnerSquareGame(12) .  "\n";  // Output: true
echo winnerSquareGame(13) .  "\n";  // Output: true
echo winnerSquareGame(14) .  "\n";  // Output: true
?>

Explanation:

• Game Theory Foundation: This is an impartial combinatorial game where both players have the same moves available from any state
• Optimal Play: A player always chooses a move that guarantees eventual victory if one exists
• State Evaluation: With i stones, the current player can remove any perfect square ≤ i, leaving i - square stones
• Recursive Relationship: The current player wins if they can move to any losing state; otherwise they lose
• Bottom-up Computation: Starting from 0 stones up to n, we can determine all states' outcomes
• Perfect Square Generation: Generate squares incrementally using j * j until exceeding current stone count
• Memory Efficiency: Only need O(n) space for the DP array

Complexity Analysis

• Time Complexity: O(n√n) - For each state up to n, we try all perfect squares up to √i, resulting in approximately n√n operations
• Space Complexity: O(n) - We maintain a DP array of size n+1 to store boolean values
• Optimization Potential: The early break when finding a winning move reduces practical runtime significantly

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3302. Find the Lexicographically Smallest Valid Sequence

MD ARIFUL HAQUE — Sat, 08 Aug 2026 16:59:51 +0000

3302. Find the Lexicographically Smallest Valid Sequence

Difficulty: Medium

Topics: Staff, Two Pointers, String, Dynamic Programming, Greedy, Biweekly Contest 140

You are given two strings word1 and word2.

A string x is called almost equal to y if you can change at most one character in x to make it identical to y.

A sequence of indices seq is called valid if:

The indices are sorted in ascending order.
Concatenating the characters at these indices in word1 in the same order results in a string that is almost equal to word2.

Return an array of size word2.length representing the lexicographically smallest¹ valid sequence of indices. If no such sequence of indices exists, return an empty array.

Note that the answer must represent the lexicographically smallest array, not the corresponding string formed by those indices.

Example 1:

Input: word1 = "vbcca", word2 = "abc"
Output: [0,1,2]
Explanation:
- The lexicographically smallest valid sequence of indices is [0, 1, 2]:
- Change word1[0] to 'a'.
- word1[1] is already 'b'.
- word1[2] is already 'c'.

Example 2:

Input: word1 = "bacdc", word2 = "abc"
Output: [1,2,4]
Explanation:
- The lexicographically smallest valid sequence of indices is [1, 2, 4]:
- word1[1] is already 'a'.
- Change word1[2] to 'b'.
- word1[4] is already 'c'.

Example 3:

Input: word1 = "aaaaaa", word2 = "aaabc"
Output: []
Explanation: There is no valid sequence of indices.

Example 4:

Input: word1 = "abc", word2 = "ab"
Output: [0,1]

Example 5:

Input: word1 = "ab", word2 = "a"
Output: [0]

Example 6:

Input: word1 = "ab", word2 = "c"
Output: [0]

Example 7:

Input: word1 = "ab", word2 = "d"
Output: [0]

Example 8:

Input: word1 = "abc", word2 = "ac"
Output: [0,2]

Example 9:

Input: word1 = "abc", word2 = "bd"
Output: [1,2]

Example 10:

Input: word1 = "xyz", word2 = "abc"
Output: []

Example 11:

Input: word1 = "aaaa", word2 = "aa"
Output: [0,1]

Example 12:

Input: word1 = "bbbb", word2 = "bb"
Output: [0,1]

Constraints:

1 <= word2.length < word1.length <= 3 * 10⁵
word1 and word2 consist only of lowercase English letters.

Hint:

Let dp[i] be the longest suffix of word2 that exists as a subsequence of suffix of the substring of word1 starting at index i.
If dp[i + 1] < m and word1[i] == word2[m - dp[i + 1] - 1],dp[i] = dp[i + 1] + 1. Otherwise, dp[i] = dp[i + 1].
For each index i, greedily select characters using the dp array to know whether a solution exists.

Solution:

We present a greedy two‑phase algorithm that constructs the lexicographically smallest valid index sequence for matching word2 as a subsequence of word1 with at most one character change. The algorithm first precomputes the latest possible match positions for each character of word2 from the right (last array), then scans word1 left‑to‑right, greedily taking matches whenever possible, and allowing exactly one substitution only when it can still lead to a complete solution.

Approach

Precompute suffix last‑occurrence (last)
- Traverse word1 from right to left and word2 from right to left.
- For each character of word2 (starting from the last), record the rightmost index in word1 where it can be matched.
- This array tells us for each position j in word2, the latest index in word1 where word2[j] can appear as a subsequence suffix.
Greedy left‑to‑right selection
- Maintain a pointer j for the current position in word2.
- Maintain a flag canSkip (initialized true) indicating we still have the one allowed change.
- Iterate i from 0 to n-1:
  - If j == m, we have matched all characters, break.
  - If word1[i] == word2[j], take this index (exact match), advance j.
  - Else if we have not used the change yet (canSkip) and it is safe to change (either j is the last character of word2, or i is before the latest possible match for the rest of word2 starting at j+1), then we use the change: set ans[j] = i, mark canSkip = false, advance j.
- After the loop, if j == m, return the answer; otherwise return empty array.
Why it yields the lexicographically smallest sequence
- By scanning from left to right and taking the earliest possible index for each position (exact match or the allowed change), we minimise each element of the resulting array in turn.
- The safety check using last ensures that using a change at the current position does not prevent a complete match for the remaining suffix.

Let's implement this solution in PHP: 3302. Find the Lexicographically Smallest Valid Sequence

<?php
/**
 * @param String $word1
 * @param String $word2
 * @return Integer[]
 */
function validSequence(string $word1, string $word2): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo validSequence("vbcca", "abc") .  "\n";             // Output: [0,1,2]
echo validSequence("bacdc", "abc") .  "\n";             // Output: [1,2,4]
echo validSequence("aaaaaa", "aaabc") .  "\n";          // Output: []
echo validSequence("abc", "ab") .  "\n";                // Output: [0, 1]
echo validSequence("ab", "a") .  "\n";                  // Output: [0]
echo validSequence("ab", "c") .  "\n";                  // Output: [0]
echo validSequence("ab", "d") .  "\n";                  // Output: [0]
echo validSequence("abc", "ac") .  "\n";                // Output: [0, 2]
echo validSequence("abc", "bd") .  "\n";                // Output: [1, 2]
echo validSequence("xyz", "abc") .  "\n";               // Output: []
echo validSequence("aaaa", "aa") .  "\n";               // Output: [0, 1]
echo validSequence("bbbb", "bb") .  "\n";               // Output: [0, 1]
?>

Explanation:

Step 1 – Build last array:
- last[j] stores the rightmost index in word1 that can serve as the start of a subsequence matching word2[j..m-1].
- This is computed by scanning word1 from the end, matching backwards from the end of word2.
Step 2 – Greedy matching with one change:
- For each index i in word1, we try to match the current needed character word2[j].
- If characters equal, we immediately take i – this is always safe and gives the smallest possible index.
- If they differ, we may use our one allowed substitution if:
  - We haven't already used it (canSkip == true).
  - We can still complete the rest of word2 after this change. This is guaranteed if either j is the last character (no more characters needed) or i < last[j+1] (meaning there exists a valid subsequence for the remainder starting after i).
- Using the change at the earliest possible i minimises the current index.
Step 3 – Termination check:
- If we successfully match all characters of word2, we return ans.
- Otherwise, no valid sequence exists, return [].

Complexity Analysis

Time Complexity: O(n + m)
- One pass to build last (O(n)).
- One pass for greedy selection (O(n)).
- All operations are constant time per character.
Space Complexity: O(m) for the last array and the answer array.
- (The answer is required output, so it counts as output space; last is the only auxiliary structure.)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Lexicographically Smaller: An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. If the first min(a.length, b.length) elements do not differ, then the shorter array is the lexicographically smaller one. ↩

3348. Smallest Divisible Digit Product II

MD ARIFUL HAQUE — Fri, 07 Aug 2026 15:23:54 +0000

3348. Smallest Divisible Digit Product II

Difficulty: Hard

Topics: Principal, Math, String, Backtracking, Greedy, Number Theory, Biweekly Contest 143

You are given a string num which represents a positive integer, and an integer t.

A number is called zero-free if none of its digits are 0.

Return a string representing the smallest zero-free number greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return "-1".

Example 1:

Input: num = "1234", t = 256
Output: "1488"
Explanation: The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.

Example 2:

Input: num = "12355", t = 50
Output: "12355"
Explanation: 12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.

Example 3:

Input: num = "11111", t = 26
Output: "-1"
Explanation: No number greater than 11111 has the product of its digits divisible by 26.

Example 4:

Input: num = "99", t = 81
Output: "99"

Example 5:

Input: num = "987", t = 2
Output: "1112"

Example 6:

Input: num = "123", t = 7
Output: "1117"

Example 7:

Input: num = "555", t = 125
Output: "555"

Example 8:

Input: num = "1", t = 1
Output: "1"

Example 9:

Input: num = "1000", t = 2
Output: "1112"

Example 10:

Input: num = "999", t = 100000000000000
Output: "4555555555555558888"

Constraints:

2 <= num.length <= 2 * 10⁵
num consists only of digits in the range ['0', '9'].
num does not contain leading zeros.
1 <= t <= 10¹⁴

Hint:

t should only have 2, 3, 5 and 7 as prime factors.
Find the shortest suffix that must be changed.
Try to form the string greedily.

Solution:

We implemented a greedy backtracking solution that finds the smallest zero‑free number ≥ given num whose digit product is divisible by t. The algorithm first factors t into its prime components (only 2,3,5,7 are relevant), then attempts to preserve as much of the prefix as possible while adjusting the suffix. If no same‑length number works, it constructs the shortest possible longer number using the most compact digit‑factor representation.

Approach

Factorize t into prime exponents for 2,3,5,7. If any other prime factor exists, return "-1".
Compute the shortest digit‑multiset (using digits 2‑9) that satisfies the required prime‑factor counts using a custom getFactorCount method that optimally groups factors into digits (e.g., three 2s → 8, two 3s → 9).
If the minimal required digit count exceeds the length of num, directly return the constructed number padded with leading 1s.
Scan from right to left to find the earliest position where increasing the digit can still allow the suffix to satisfy the remaining factor requirements.
For each candidate larger digit at that position, check if the leftover factor demand can be filled within the available suffix length using our compact digit‑factor mapping.
If a valid position is found, build the result: prefix unchanged, larger digit, then 1s (which don’t affect product), then the compact factor‑fulfilling digits.
If no same‑length solution exists, return a number of length len(num)+1 consisting of leading 1s followed by the minimal factor‑fulfilling digits.

Let's implement this solution in PHP: 3348. Smallest Divisible Digit Product II

<?php
/**
 * @param string $num
 * @param int $t
 * @return string
 */
function smallestNumber(string $num, int $t): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param int $t
 * @return array
 */
function getPrimeCount(int $t): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param string $num
 * @param array $factorCounts
 * @return int[]
 */
function getPrimeCountFromString(string $num, array $factorCounts): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param array $count
 * @return int[]
 */
function getFactorCount(array $count): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param array $factors
 * @return string
 */
function constructNumber(array $factors): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param array $a
 * @param array $b
 * @return bool
 */
function isSubset(array $a, array $b): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param array $a
 * @param array $b
 * @return array
 */
function subtract(array $a, array $b): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo smallestNumber("1234", 256) .  "\n";                           // Output: "1488"
echo smallestNumber("12355", 50) .  "\n";                           // Output: "12355"
echo smallestNumber("11111", 26) .  "\n";                           // Output: "-1"
echo smallestNumber("99", 81) .  "\n";                              // Output: "99"
echo smallestNumber("987", 2) .  "\n";                              // Output: "1112"
echo smallestNumber("123", 7) .  "\n";                              // Output: "1117"
echo smallestNumber("555", 125) .  "\n";                            // Output: "555"
echo smallestNumber("1", 1) .  "\n";                                // Output: "1"
echo smallestNumber("1000", 2) .  "\n";                             // Output: "1112"
echo smallestNumber("999", 100000000000000) .  "\n";                // Output: "4555555555555558888"
?>

Explanation:

Prime‑only validation: Since digits 1‑9 only contribute factors 2,3,5,7, any t with other prime factors is impossible.
Digit‑factor mapping: Pre‑compute prime‑factor vectors for each digit 0‑9 (0 and 1 contribute none). For 0, any product becomes 0, but the problem requires zero‑free numbers, so we actively avoid digit 0.
Compact factor grouping: getFactorCount translates required prime exponents into the fewest number of digits (preferring larger digits like 8,9,6 to minimize digit count). This is crucial for fitting within length constraints and constructing the smallest numeric string.
Prefix preservation: The algorithm attempts to keep the longest possible prefix of num unchanged. It tracks the cumulative factors of the prefix (primeCountPrefix). When considering a change at position i, it subtracts the current digit’s factors and tries all larger digits.
Feasibility check: For a candidate larger digit, we compute the remaining factor demand for the suffix. If that demand can be met within the remaining positions (including optional 1s), we construct the result greedily – 1s are added first (they are smallest and don’t affect product), followed by the compact factor digits sorted ascending.
Fallback to longer length: If no valid same‑length number exists, the minimal longer number is formed by as many leading 1s as possible (to keep the number small) plus the minimal factor‑fulfilling digits in ascending order.

Complexity Analysis

Time: O(n * 10 * 8) = O(n), where n = length of num. For each position we test at most 9 larger digits, and each test performs constant‑time operations on the fixed‑size prime‑factor arrays (4 primes). Constructing the result also takes O(n).
Space: O(n) for the output string; the factor arrays are constant‑size (4 or 8 entries).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3345. Smallest Divisible Digit Product I

MD ARIFUL HAQUE — Thu, 06 Aug 2026 16:11:35 +0000

3345. Smallest Divisible Digit Product I

Difficulty: Easy

Topics: Mid Level, Math, Enumeration, Biweekly Contest 143

You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.

Example 1:

Input: n = 10, t = 2
Output: 10
Explanation: The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.

Example 2:

Input: n = 15, t = 3
Output: 16
Explanation: The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.

Example 3:

Input: n = 15, t = 3
Output: 16

Example 4:

Input: n = 1, t = 1
Output: 1

Example 5:

Input: n = 25, t = 5
Output: 25

Example 6:

Input: n = 99, t = 9
Output: 99

Example 7:

Input: n = 100, t = 7
Output: 100

Constraints:

1 <= n <= 100
1 <= t <= 10

Hint:

You have to check at most 10 numbers.
Apply a brute-force approach by checking each possible number.

Solution:

We approached the problem using a brute-force enumeration strategy, leveraging the constraint that n ≤ 100 and the guarantee that a valid answer will be found within at most 10 iterations. By incrementally checking each number starting from n, we compute the product of its digits and test divisibility by t until we find the smallest valid number.

Approach

Start from n and check each integer sequentially.
For each candidate number, compute the product of its digits:
- Initialize product = 1.
- Extract digits one by one using modulo and integer division.
- Multiply each digit into product.
- If product becomes 0, break early (since the final product is 0, which is divisible by any t).
Check if product % t == 0; if true, return the current number.
If not, increment the number and repeat.
Stop when the condition is met (guaranteed within a few steps due to constraints).

Let's implement this solution in PHP: 3345. Smallest Divisible Digit Product I

<?php
/**
 * @param Integer $n
 * @param Integer $t
 * @return Integer
 */
function smallestNumber(int $n, int $t): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo smallestNumber(10, 2) .  "\n";         // Output: 10
echo smallestNumber(15, 3) .  "\n";         // Output: 16
echo smallestNumber(1, 1) .  "\n";          // Output: 1
echo smallestNumber(9, 10) .  "\n";         // Output: 10
echo smallestNumber(99, 9) .  "\n";         // Output: 99
echo smallestNumber(100, 7) .  "\n";        // Output: 100
?>

Explanation:

Why at most 10 numbers? The hint assures us that checking a small range of numbers is sufficient. This is because digit products change rapidly and 0 appears frequently, making divisibility easy to achieve.
Early exit optimization If any digit is 0, the entire product becomes 0. Since 0 is divisible by any t (because 0 % t == 0), we can immediately return the number when we encounter a 0 digit during the product calculation. This avoids unnecessary multiplication.
Brute-force is acceptable With n up to 100, even if we had to check more numbers, it would still be trivial. However, the problem guarantees quick termination.
Integer division We use intdiv($temp, 10) to strip the last digit, ensuring clean integer arithmetic.
Product reset For each new number, we reset product = 1 to start fresh.

Complexity Analysis

Time Complexity: O(k * d) where k is the number of iterations (≤ 10) and d is the number of digits (≤ 3 for n ≤ 100). In practice, this is constant time.
Space Complexity: O(1) — only a few integer variables are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3310. Remove Methods From Project

MD ARIFUL HAQUE — Wed, 05 Aug 2026 16:57:02 +0000

3310. Remove Methods From Project

Difficulty: Medium

Topics: Staff, Depth-First Search, Breadth-First Search, Graph Theory, Weekly Contest 418

You are maintaining a project that has n methods numbered from 0 to n - 1.

You are given two integers n and k, and a 2D integer array invocations, where invocations[i] = [aᵢ, bᵢ] indicates that method aᵢ invokes method bᵢ.

There is a known bug in method k. Method k, along with any method invoked by it, either directly or indirectly, are considered suspicious, and we aim to remove them.

A group of methods can only be removed if no method outside the group invokes any methods within it.

Return an array containing all the remaining methods after removing all the suspicious methods. You may return the answer in any order. If it is not possible to remove all the suspicious methods, none should be removed.

Example 1:

Input: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
Output: [0,1,2,3]
Explanation:

Method 2 and method 1 are suspicious, but they are directly invoked by methods 3 and 0, which are not suspicious. We return all elements without removing anything.

Example 2:

Input: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]
Output: [3,4]
Explanation:

Methods 0, 1, and 2 are suspicious, and they are not directly invoked by any other method. We can remove them.

Example 3:

Input: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]
Output: []
Explanation:

All methods are suspicious. We can remove them.

Example 4:

Input: n = 3, k = 0, invocations = []
Output: [1,2]

Example 5:

Input: n = 2, k = 1, invocations = [[0,1]]
Output: [0,1]

Example 6:

Input: n = 6, k = 2, invocations = [[0,1],[2,3],[3,4],[5,5]]
Output: [0,1,5]

Constraints:

1 <= n <= 10⁵
0 <= k <= n - 1
0 <= invocations.length <= 2 * 10⁵
invocations[i] == [aᵢ, bᵢ]
0 <= aᵢ, bᵢ <= n - 1
aᵢ != bᵢ
invocations[i] != invocations[j]

Hint:

Use DFS from node k.
Mark all the nodes visited from node k, and then check if they can be visited from the other nodes.

Solution:

We have implemented a solution that identifies and removes suspicious methods (those reachable from the buggy method k via direct or indirect invocations) while ensuring that no external method invokes any method within the suspicious group. If such an external invocation exists, we preserve all methods; otherwise, we return only the non-suspicious methods. Our approach uses a breadth-first search to mark suspicious methods and a single pass over the invocation list to validate the removal condition.

Approach

Build adjacency list: Represent the invocation graph using an adjacency list where each node points to the methods it directly invokes.
Identify suspicious methods: Perform a BFS (or DFS) starting from method k to mark all methods reachable from it as suspicious.
Validate removal condition: Iterate through all invocations. If any non-suspicious method invokes a suspicious method, removal is invalid.
Return result: If invalid, return all methods (0 to n-1). Otherwise, return all methods not marked as suspicious.

Let's implement this solution in PHP: 3310. Remove Methods From Project

<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @param Integer[][] $invocations
 * @return Integer[]
 */
function remainingMethods(int $n, int $k, array $invocations): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo remainingMethods(4, 1, [[1,2],[0,1],[3,2]]) .  "\n";               // Output: [0,1,2,3]
echo remainingMethods(5, 0, [[1,2],[0,2],[0,1],[3,4]]) .  "\n";         // Output: [3,4]
echo remainingMethods(3, 2, [[1,2],[0,1],[2,0]]) .  "\n";               // Output: []
echo remainingMethods(3, 0, []) .  "\n";                                // Output: [1,2]
echo remainingMethods(2, 1, [[0,1]]) .  "\n";                           // Output: [0,1]
echo remainingMethods(6, 2, [[0,1],[2,3],[3,4],[5,5]]) .  "\n";         // Output: [0,1,5]
?>

Explanation:

Graph construction: We create an array of lists where graph[a] contains all b such that a invokes b. This allows efficient traversal from any method.
Suspicious marking via BFS: Starting from k, we traverse all reachable nodes using a queue. Every visited node is marked true in the suspicious array. This captures the exact set of methods that are bug-affected.
Removal condition check: We examine every invocation [a, b].
- If a is not suspicious but b is suspicious, then an external method invokes a suspicious one.
- According to the problem, such a scenario prevents us from removing the suspicious group, so we return all methods unchanged.
Result construction: When removal is permissible, we iterate through all n methods and collect those that are not suspicious. These are the methods that remain after removal.
Edge cases handled:
- No invocations → BFS only visits k, and if no external invokes k, all other methods remain.
- All methods suspicious → result will be empty (valid removal).
- Methods with cycles → BFS handles cycles using the visited check.

Complexity Analysis

Time Complexity: O(n + m)
- Building adjacency list: O(m) where m = invocations.length.
- BFS traversal: O(n + m) in the worst case (visits all nodes and edges).
- Validation pass: O(m).
- Overall linear with respect to the input size.
Space Complexity: O(n + m)
- Adjacency list stores all edges: O(m).
- suspicious array and queue store up to n elements: O(n).
- Result array stores up to n elements: O(n).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3731. Find Missing Elements

MD ARIFUL HAQUE — Tue, 04 Aug 2026 15:51:47 +0000

3731. Find Missing Elements

Difficulty: Easy

Topics: Mid Level, Array, Hash Table, Sorting, Weekly Contest 474

You are given an integer array nums consisting of unique integers.

Originally, nums contained every integer within a certain range. However, some integers might have gone missing from the array.

The smallest and largest integers of the original range are still present in nums.

Return a sorted list of all the missing integers in this range. If no integers are missing, return an empty list.

Example 1:

Input: nums = [1,4,2,5]
Output: [3]
Explanation: The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. Among these, only 3 is missing.

Example 2:

Input: nums = [7,8,6,9]
Output: []
Explanation: The smallest integer is 6 and the largest is 9, so the full range is [6,7,8,9]. All integers are already present, so no integer is missing.

Example 3:

Input: nums = [5,1]
Output: [2,3,4]
Explanation: The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. The missing integers are 2, 3, and 4.

Example 4:

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

Example 5:

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

Example 6:

Input: nums = [1,2,4,5]
Output: [3]

Example 7:

Input: nums = [10,7,9,8]
Output: []

Example 8:

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

Constraints:

2 <= nums.length <= 100
1 <= nums[i] <= 100

Hint:

First, find the maximum and minimum elements in the array.
Then, iterate over all the integers in the range [min, max] and check if they are in the array.
If not, add them to the array, and return the sorted array at the end.

Solution:

We implement an efficient solution to find missing integers in a given range by leveraging array hashing for O(1) lookups. Our approach identifies the minimum and maximum values from the input array to define the complete range, then iterates through that range to identify any missing numbers using a hash map for fast membership testing.

Approach

Use PHP's built-in min() and max() functions to find the smallest and largest values in the input array
Create a lookup table using array_flip() which maps each value to its index, enabling O(1) membership checks
Iterate through all integers from min to max inclusive
For each integer, check if it exists in the flipped array using isset()
Collect any integers not present in the original array into the result array
Return the collected missing numbers (they will naturally be sorted since we iterate in ascending order)

Let's implement this solution in PHP: 3731. Find Missing Elements

<?php
/**
 * @param Integer[] $nums
 * @return Integer[]
 */
function findMissingElements(array $nums): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo findMissingElements([1,4,2,5]) .  "\n";            // Output: [3]
echo findMissingElements([7,8,6,9]) .  "\n";            // Output: []
echo findMissingElements([5,1]) .  "\n";                // Output: [2,3,4]
echo findMissingElements([1,10]) .  "\n";               // Output: [2,3,4,5,6,7,8,9]
echo findMissingElements([2,3]) .  "\n";                // Output: []
echo findMissingElements([1,2,4,5]) .  "\n";            // Output: [3]
echo findMissingElements([10,7,9,8]) .  "\n";           // Output: []
echo findMissingElements([2,5]) .  "\n";                // Output: [3,4]
?>

Explanation:

Range Definition: The original range is bounded by the minimum and maximum values still present in nums, as guaranteed by the problem statement
Lookup Optimization: Converting the array to a hash map (via array_flip) allows constant-time existence checks instead of O(n) linear searches
Iteration Pattern: We loop from $min to $max inclusive, ensuring we check every possible value in the range
Missing Detection: For each value $i, we check if it exists as a key in the flipped array; if not, it's missing
Sorted Output: Since we iterate in ascending order from min to max, we collect missing numbers in sorted order without needing additional sorting

Complexity Analysis

Time Complexity: O(n + range) where n is the length of the input array and range is (max - min + 1). We spend O(n) to flip the array and O(range) to scan through the range. In the worst case, range ≤ 100 (given constraints), making this effectively O(n + 100)
Space Complexity: O(n) for the flipped array lookup table, plus O(range) for the result array in the worst case

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1406. Stone Game III

MD ARIFUL HAQUE — Mon, 03 Aug 2026 14:04:00 +0000

1406. Stone Game III

Difficulty: Hard

Topics: Principal, Array, Math, Dynamic Programming, Minimax, Game Theory, Zero-Sum Game, Weekly Contest 183

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.

The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob play optimally.

Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they will end the game with the same score.

Example 1:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2:

Input: stoneValue = [1,2,3,-9]
Output: "Alice"
Explanation:
- Alice must choose all the three piles at the first move to win and leave Bob with negative score.
- If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
- If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
- Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3:

Input: stoneValue = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

Example 4:

Input: stoneValue = [1]
Output: "Alice"

Example 5:

Input: stoneValue = [-1,-2,-3]
Output: "Bob"

Example 6:

Input: stoneValue = [0,0,0]
Output: "Tie"

Example 7:

Input: stoneValue = [1000,-1000,1000]
Output: "Alice"

Example 8:

Input: stoneValue = [10, -20, 30, -40, 50]
Output: "Alice"

Example 9:

Input: stoneValue = [-5, -5, -5, -5, -5]
Output: "Bob"

Example 10:

Input: stoneValue = [1,2,3,4,5,6,7,8,9,10]
Output: "Alice"

Constraints:

1 <= stoneValue.length <= 5 * 10⁴
-1000 <= stoneValue[i] <= 1000

Hint:

The game can be mapped to minmax game. Alice tries to maximize the total score and Bob tries to minimize it.
Use dynamic programming to simulate the game. If the total score was 0 the game is "Tie", and if it has positive value then "Alice" wins, otherwise "Bob" wins.

Solution:

We use a dynamic programming (DP) approach to model the minimax game. dp[i] represents the maximum relative score difference (current player's total − opponent's total) that the current player can achieve from index i onward.

Approach

We define dp[i] as the best advantage (score difference) the player whose turn it is can obtain from pile i to the end.
Work backwards from the last pile to the first.
At each position i, the current player can take 1, 2, or 3 stones.
If they take k stones, their gain is sum of those stones, and the opponent will then get dp[i+k] advantage from the remaining piles.
So the net difference for the current player becomes: sum − dp[i+k].
We take the maximum over all valid k values (1 to 3).
After filling dp[0], the game result depends on its sign:
- > 0 → Alice wins
- < 0 → Bob wins
- == 0 → Tie

Let's implement this solution in PHP: 1406. Stone Game III

<?php
/**
 * @param Integer[] $stoneValue
 * @return String
 */
function stoneGameIII(array $stoneValue): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo stoneGameIII([1, 2, 3, 7]) . "\n";                 // Output: "Bob"
echo stoneGameIII([1, 2, 3, -9]) . "\n";                // Output: "Alice"
echo stoneGameIII([1, 2, 3, 6]) . "\n";                 // Output: "Tie"
echo stoneGameIII([1]) . "\n";                          // Output: "Alice"
echo stoneGameIII([-1,-2,-3]) . "\n";                   // Output: "Bob"
echo stoneGameIII([0,0,0]) . "\n";                      // Output: "Tie"
echo stoneGameIII([1000,-1000,1000]) . "\n";            // Output: "Alice"
echo stoneGameIII([10, -20, 30, -40, 50]) . "\n";       // Output: "Alice"
echo stoneGameIII([-5, -5, -5, -5, -5]) . "\n";         // Output: "Bob"
echo stoneGameIII([1,2,3,4,5,6,7,8,9,10]) . "\n";       // Output: "Alice"
?>

Explanation:

Base case: dp[n] = 0, because with no stones left, the advantage is 0.
Transition:
- At index i, initialize dp[i] to a very small number.
- For k = 1, 2, 3 (if valid), compute sum of k stones starting at i.
- Then compute candidate: sum − dp[i+k].
- Keep the maximum candidate.
dp[i] essentially stores the best score difference (current player's future total minus opponent's future total) from this state.
At i = 0, Alice is the current player, so:
- dp[0] > 0 → Alice's total > Bob's total → Alice wins.
- dp[0] < 0 → Bob wins.
- dp[0] == 0 → Tie.

Complexity Analysis

Time Complexity: O(n), We iterate through the array once and for each index, try at most 3 moves.
Space Complexity: O(n), We use an array dp of size n + 1.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub