DEV Community: MD ARIFUL HAQUE

3903. Smallest Stable Index I

MD ARIFUL HAQUE — Fri, 04 Sep 2026 17:33:02 +0000

3903. Smallest Stable Index I

Difficulty: Easy

Topics: Mid Level, Array, Prefix Sum, Weekly Contest 498

You are given an integer array nums of length n and an integer k.

For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]).

In other words:

max(nums[0..i]) is the largest value among the elements from index 0 to index i.
min(nums[i..n - 1]) is the smallest value among the elements from index i to index n - 1.

An index i is called stable if its instability score is less than or equal to k.

Return the smallest stable index. If no such index exists, return -1.

Example 1:

Input: nums = [5,0,1,4], k = 3
Output: 3
Explanation:
- At index 0: The maximum in [5] is 5, and the minimum in [5, 0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
- At index 1: The maximum in [5, 0] is 5, and the minimum in [0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
- At index 2: The maximum in [5, 0, 1] is 5, and the minimum in [1, 4] is 1, so the instability score is 5 - 1 = 4.
- At index 3: The maximum in [5, 0, 1, 4] is 5, and the minimum in [4] is 4, so the instability score is 5 - 4 = 1.
- This is the first index with an instability score less than or equal to k = 3. Thus, the answer is 3.

Example 2:

Input: nums = [3,2,1], k = 1
Output: -1
Explanation:
- At index 0, the instability score is 3 - 1 = 2.
- At index 1, the instability score is 3 - 1 = 2.
- At index 2, the instability score is 3 - 1 = 2.
- None of these values is less than or equal to k = 1, so the answer is -1.

Example 3:

Input: nums = [0], k = 0
Output: 0
Explanation: At index 0, the instability score is 0 - 0 = 0, which is less than or equal to k = 0. Therefore, the answer is 0.

Example 4:

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

Example 5:

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

Example 6:

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

Example 7:

Input: nums = [100], k = 50
Output: 0

Example 8:

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

Constraints:

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

Hint:

Simulate as described

Solution:

We solve the problem by precomputing prefix maximums and suffix minimums for the given array, then scanning from left to right to find the first index where the instability score (max(0..i) - min(i..n-1)) is ≤ k. This allows us to evaluate each index in constant time after an O(n) preprocessing step.

Approach

Precompute a prefixMax array where prefixMax[i] = maximum value in nums[0..i].
Precompute a suffixMin array where suffixMin[i] = minimum value in nums[i..n-1].
Iterate over all indices from 0 to n-1.
For each index i, compute the instability score as prefixMax[i] - suffixMin[i].
Return the first index where this score ≤ k. If none, return -1.

Let's implement this solution in PHP: 3903. Smallest Stable Index I

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

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

Explanation:

Prefix maximums are built left-to-right: prefixMax[i] = max(prefixMax[i-1], nums[i]).
Suffix minimums are built right-to-left: suffixMin[i] = min(suffixMin[i+1], nums[i]).
Instability score for index i is simply the difference between the precomputed prefix max and suffix min at that index.
Since we process indices in increasing order, the first one satisfying the condition is the smallest stable index.
This method handles all edge cases, including single‑element arrays and negative results, without needing nested loops.

Complexity Analysis

Time Complexity: O(n) – we do three linear passes (prefix, suffix, and scanning) over the array.
Space Complexity: O(n) – we store two auxiliary arrays of size n for prefix max and suffix min.

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

3876. Construct Uniform Parity Array II

MD ARIFUL HAQUE — Thu, 03 Sep 2026 18:03:28 +0000

3876. Construct Uniform Parity Array II

Difficulty: Medium

Topics: Senior, Array, Math, Weekly Contest 494

You are given an array nums1 of n distinct integers.

You want to construct another array nums2 of length n such that the elements in nums2 are either all odd or all even.

For each index i, you must choose exactly one of the following (in any order):

nums2[i] = nums1[i]
nums2[i] = nums1[i] - nums1[j], for an index j != i, such that nums1[i] - nums1[j] >= 1

Return true if it is possible to construct such an array, otherwise return false.

Example 1:

Input: nums1 = [1,4,7]
Output: true
Explanation:
- Set nums2[0] = nums1[0] = 1.
- Set nums2[1] = nums1[1] - nums1[0] = 4 - 1 = 3.
- Set nums2[2] = nums1[2] = 7.
- nums2 = [1, 3, 7], and all elements are odd. Thus, the answer is true.

Example 2:

Input: nums1 = [2,3]
Output: false
Explanation: It is not possible to construct nums2 such that all elements have the same parity. Thus, the answer is false.

Example 3:

Input: nums1 = [4,6]
Output: true
Explanation:
- Set nums2[0] = nums1[0] = 4.
- Set nums2[1] = nums1[1] = 6.
- nums2 = [4, 6], and all elements are even. Thus, the answer is true.

Example 4:

Input: nums1 = [11,16]
Output: true

Example 5:

Input: nums1 = [2,4,6]
Output: true

Example 6:

Input: nums1 = [1,3,5]
Output: true

Example 7:

Input: nums1 = [1,2]
Output: true

Example 8:

Input: nums1 = [5,10]
Output: true

Example 9:

Input: nums1 = [8,9]
Output: false

Example 10:

Input: nums1 = [3,6,9]
Output: true

Constraints:

1 <= n == nums1.length <= 10⁵
1 <= nums1[i] <= 10⁹
nums1 consists of distinct integers.

Hint:

Try fixing the parity to either all even or all odd.
Use the smallest odd/even element if a subtraction is needed to match the chosen parity.

Solution:

We solve the problem by checking both possible target parities (all odd or all even) for nums2. For each target parity, we determine whether every element in nums1 can either stay as is (if it already matches the target parity) or be transformed by subtracting the smallest number of the opposite parity, as long as the result remains positive. If either parity works, we return true; otherwise, false.

Approach

Fix target parity: Try to make all elements in nums2 odd, then try to make all even.
Key observation: To change the parity of an element, we must subtract an odd number (since odd – odd = even, even – odd = odd). The best candidate for subtraction is the smallest odd number in nums1, because using a larger odd number would make the result smaller and could go below 1, making it invalid.
Check validity for each parity:
- For all odd: Any even number must be subtracted by the smallest odd number minOdd, and the result must be at least 1.
- For all even: Any odd number must be subtracted by minOdd (an odd number) to become even, and the result must be at least 1.
Special case: If there are no odd numbers, all elements are already even, so all-even is trivially possible.

Let's implement this solution in PHP: 3876. Construct Uniform Parity Array II

<?php
/**
 * @param Integer[] $nums1
 * @return Boolean
 */
function uniformArray(array $nums1): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation:

We first find the minimum odd number in nums1. This is crucial because subtracting any odd number preserves the parity change but the smallest one gives the largest possible result, avoiding negative or zero values.
To check all odd:
- Iterate through nums1.
- If a number is already odd, we can keep it as is.
- If it’s even, we must subtract minOdd. If minOdd doesn’t exist or num - minOdd < 1, this parity fails.
To check all even:
- If no odd numbers exist, all are even → success.
- Otherwise, for each odd number, subtract minOdd; if the result is less than 1, this parity fails.
If either check passes, return true; else false.

Complexity Analysis

Time Complexity: O(n) — We scan the array a constant number of times (to find min odd and to validate each parity).
Space Complexity: O(1) — We use only a few extra variables.

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

3875. Construct Uniform Parity Array I

MD ARIFUL HAQUE — Wed, 02 Sep 2026 17:54:24 +0000

3875. Construct Uniform Parity Array I

Difficulty: Easy

Topics: Mid Level, Array, Math, Weekly Contest 494

You are given an array nums1 of n distinct integers.

You want to construct another array nums2 of length n such that the elements in nums2 are either all odd or all even.

For each index i, you must choose exactly one of the following (in any order):

nums2[i] = nums1[i]
nums2[i] = nums1[i] - nums1[j], for an index j != i

Return true if it is possible to construct such an array, otherwise, return false.

Example 1:

Input: nums1 = [2,3]
Output: true
Explanation:
- Choose nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1.
- Choose nums2[1] = nums1[1] = 3.
- nums2 = [-1, 3], and both elements are odd. Thus, the answer is true.

Example 2:

Input: nums1 = [4,6]
Output: true
Explanation:
- Choose nums2[0] = nums1[0] = 4.
- Choose nums2[1] = nums1[1] = 6.
- nums2 = [4, 6], and all elements are even. Thus, the answer is true.

Example 3:

Input: nums1 = [1, 3, 5]
Output: true

Example 4:

Input: nums1 = [2, 4, 6]
Output: true

Example 5:

Input: nums1 = [1, 2, 3]
Output: true

Example 6:

Input: nums1 = [5]
Output: true

Example 7:

Input: nums1 = [2]
Output: true

Example 8:

Input: nums1 = [1, 4, 7, 10]
Output: true

Example 9:

Input: nums1 = [3, 6, 9, 12]
Output: true

Example 10:

Input: nums1 = [100, 99]
Output: true

Constraints:

1 <= n == nums1.length <= 100
1 <= nums1[i] <= 100
nums1 consists of distinct integers.

Hint:

There is only one possible answer.

Solution:

We have determined that the construction of nums2 is always possible for any valid input array nums1 of distinct integers. The key insight is that we have enough flexibility in choosing either the original value or a difference with another element to force all elements in nums2 to share the same parity. The parity of a difference between two numbers is determined solely by their parity relationship, and since we can choose a different j for each i (or even use the same j for multiple i), we can always achieve uniform parity.

Approach

Observation: The operation nums1[i] - nums1[j] changes the parity of nums2[i] based on the parity of nums1[j]:
- If nums1[i] and nums1[j] have the same parity, their difference is even.
- If they have different parity, their difference is odd.
Base Case: For any i, we can always choose nums2[i] = nums1[i], preserving its original parity.
Strategy: We can choose to make all elements either odd or even by:
- If all numbers are already even, keep them all as even.
- If all numbers are already odd, keep them all as odd.
- If there is a mix of even and odd numbers, we can use differences to flip parity for some elements.
Critical Insight: With at least one even and one odd number in nums1, for any index i:
- If nums1[i] is even, we can make it odd by subtracting an odd number (nums1[j] where nums1[j] is odd).
- If nums1[i] is odd, we can make it even by subtracting an even number (nums1[j] where nums1[j] is even).
- Therefore, we can choose the parity for each element independently, and we can choose all elements to be odd or all to be even.
Edge Cases: When n = 1, there is no j != i, so we must use nums2[0] = nums1[0]. This single element is trivially uniform (both all odd or all even), so the answer is always true.

Let's implement this solution in PHP: 3875. Construct Uniform Parity Array I

<?php
/**
 * @param Integer[] $nums1
 * @return Boolean
 */
function uniformArray($c, $connections, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo uniformArray([2, 3]) .  "\n";              // Output: true
echo uniformArray([4, 6]) .  "\n";              // Output: true
echo uniformArray([1, 3, 5]) .  "\n";           // Output: true
echo uniformArray([2, 4, 6]) .  "\n";           // Output: true
echo uniformArray([1, 2, 3]) .  "\n";           // Output: true
echo uniformArray([5]) .  "\n";                 // Output: true
echo uniformArray([2]) .  "\n";                 // Output: true
echo uniformArray([1, 4, 7, 10]) .  "\n";       // Output: true
echo uniformArray([3, 6, 9, 12]) .  "\n";       // Output: true
echo uniformArray([100, 99]) .  "\n";           // Output: true
?>

Explanation:

Step 1: Check if all elements in nums1 are even → choose nums2[i] = nums1[i] for all i → all even → true.
Step 2: Check if all elements in nums1 are odd → choose nums2[i] = nums1[i] for all i → all odd → true.
Step 3: If there is a mix of even and odd numbers in nums1:
- Let E be an even element and O be an odd element from nums1.
- For any index i:
  - To make nums2[i] even:
    - If nums1[i] is even → use nums2[i] = nums1[i] (even).
    - If nums1[i] is odd → use nums2[i] = nums1[i] - E (odd - even = odd? Wait, odd - even = odd, that's not even). Actually: odd - even = odd, not even. Let's correct:
    - For odd nums1[i], to get even: use nums2[i] = nums1[i] - O? No, odd - odd = even. So use nums2[i] = nums1[i] - O where O is an odd element.
  - To make nums2[i] odd:
    - If nums1[i] is odd → use nums2[i] = nums1[i] (odd).
    - If nums1[i] is even → use nums2[i] = nums1[i] - O (even - odd = odd).
Step 4: Since we can always choose the appropriate operation for each index independently, we can construct nums2 with all elements being either odd or even.
Step 5: Therefore, the answer is always true for all valid inputs.

Complexity Analysis

Time Complexity: O(1) - The solution performs no iterative operations over the array; it simply returns true.
Space Complexity: O(1) - No additional data structures 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

3568. Minimum Moves to Clean the Classroom

MD ARIFUL HAQUE — Tue, 01 Sep 2026 14:59:54 +0000

3568. Minimum Moves to Clean the Classroom

Difficulty: Medium

Topics: Staff, Array, Hash Table, Bit Manipulation, Breadth-First Search, Matrix, Weekly Contest 452

You are given an m x n grid classroom where a student volunteer is tasked with cleaning up litter scattered around the room. Each cell in the grid is one of the following:

'S': Starting position of the student
'L': Litter that must be collected (once collected, the cell becomes empty)
'R': Reset area that restores the student's energy to full capacity, regardless of their current energy level (can be used multiple times)
'X': Obstacle the student cannot pass through
'.': Empty space

You are also given an integer energy, representing the student's maximum energy capacity. The student starts with this energy from the starting position 'S'.

Each move to an adjacent cell (up, down, left, or right) costs 1 unit of energy. If the energy reaches 0, the student can only continue if they are on a reset area 'R', which resets the energy to its maximum capacity energy.

Return the minimum number of moves required to collect all litter items, or -1 if it's impossible.

Example 1:

Input: classroom = ["S.", "XL"], energy = 2
Output: 2
Explanation:
- The student starts at cell (0, 0) with 2 units of energy.
- Since cell (1, 0) contains an obstacle 'X', the student cannot move directly downward.
- A valid sequence of moves to collect all litter is as follows:
- Move 1: From (0, 0) → (0, 1) with 1 unit of energy and 1 unit remaining.
- Move 2: From (0, 1)→ (1, 1) to collect the litter 'L'.
- The student collects all the litter using 2 moves. Thus, the output is 2.

Example 2:

Input: classroom = ["LS", "RL"], energy = 4
Output: 3
Explanation:
- The student starts at cell (0, 1) with 4 units of energy.
- A valid sequence of moves to collect all litter is as follows:
- Move 1: From (0, 1) → (0, 0) to collect the first litter 'L' with 1 unit of energy used and 3 units remaining.
- Move 2: From (0, 0) → (1, 0) to 'R' to reset and restore energy back to 4.
- Move 3: From (1, 0) → (1, 1) to collect the second litter 'L'.
- The student collects all the litter using 3 moves. Thus, the output is 3.

Example 3:

Input: classroom = ["L.S", "RXL"], energy = 3
Output: -1
Explanation: No valid path collects all 'L'.

Example 4:

Input: classroom = ["L", "R", ".", "S", "."], energy = 1
Output: -1

Example 5:

Input: classroom = ["S...................", "....................", "....................", "....................", ".....RL........RR...", "....................", "......L....R..L.....", ".....L..............", ".........L........LL", "....................", "....................", "....................", "........L...........", "....................", "....................", "....................", "....L...............", "....................", ".....R..............", "..............L....."], energy = 20
Output: 71

Example 6:

Input: classroom = ["SL"], energy = 1
Output: 1

Example 7:

Input: classroom = ["S.L", "..R"], energy = 2
Output: 5

Example 8:

Input: classroom = ["SX", "XL"], energy = 5
Output: -1

Example 9:

Input: classroom = ["SRL"], energy = 1
Output: 2

Constraints:

1 <= m == classroom.length <= 20
1 <= n == classroom[i].length <= 20
classroom[i][j] is one of 'S', 'L', 'R', 'X', or '.'
1 <= energy <= 50
There is exactly one 'S' in the grid.
There are at most 10 'L' cells in the grid.

Hint:

Use BFS with states (x, y, mask, e, steps), initializing with (sx, sy, 0, energy, 0), and for each move update e (–1 per step), update mask on 'L', reset e=energy on 'R', and return steps when mask == fullMask.
Maintain a 3D array bestEnergy[x][y][mask] storing the maximum e seen for each (x,y,mask) and skip any new state with e <= bestEnergy[x][y][mask] to prune.

Solution:

We implement a state‑space BFS over (x, y, mask, energy), where mask tracks which litter cells (L) have been collected. The search respects energy constraints, resets on R, and prunes dominated states to keep the problem feasible (≤10 litter, 20×20 grid, energy≤50). The BFS guarantees the first time we visit fullMask yields the minimum number of moves.

Approach

State definition – (x, y, mask, e): position, collected‑litter bitmask, current energy.
Initialisation – start at S with mask=0, e=energy, steps=0.
Transition – for each neighbor not X:
- Compute ne = e - 1. If e == 0, we can only move if currently on R (reset to energy before moving → ne = energy - 1).
- After moving, if the new cell is R, set ne = energy (reset).
- If the new cell is L and not yet in mask, add its bit.
Pruning – maintain bestEnergy[x][y][mask] = maximum energy seen for that state; skip if ne <= bestEnergy[...].
Termination – return steps + 1 when mask == fullMask; if queue empties, return -1.

Let's implement this solution in PHP: 3568. Minimum Moves to Clean the Classroom

<?php
/**
 * @param String[] $classroom
 * @param Integer $energy
 * @return Integer
 */
function minMoves(array $classroom, int $energy): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minMoves(["S.", "XL"], 2) .  "\n";                         // Output: 2
echo minMoves(["LS", "RL"], 4) .  "\n";                         // Output: 3
echo minMoves(["L.S", "RXL"], 3) .  "\n";                       // Output: -1
echo minMoves(["L", "R", ".", "S", "."], 1) .  "\n";            // Output: -1

$classroom = ["S...................", "....................", "....................", "....................", ".....RL........RR...", "....................", "......L....R..L.....", ".....L..............", ".........L........LL", "....................", "....................", "....................", "........L...........", "....................", "....................", "....................", "....L...............", "....................", ".....R..............", "..............L....."];
$energy = 20;
echo minMoves($classroom, $energy) .  "\n";                     // Output: 71
echo minMoves(["SL"], 1) .  "\n";                               // Output: 1
echo minMoves(["S.L", "..R"], 2) .  "\n";                       // Output: 5
echo minMoves(["SX", "XL"], 5) .  "\n";                         // Output: -1
echo minMoves(["SRL"], 1) .  "\n";                              // Output: 2
?>

Explanation:

BFS overstates, not just cells – because energy and collected litter matter, a simple grid BFS is insufficient.
Handling energy zero – the student may only leave an R cell with zero energy; we implement this by checking e == 0 before moving and resetting if standing on R.
Reset on arrival – after moving into R, we immediately refill energy to energy.
Mask for litter – up to 10 litter cells → bitmask fits in 1024 states; efficient memory with bestEnergy[20][20][1024].
Pruning with max energy – if we reach the same (x, y, mask) with lower or equal energy, it is never better than a previous visit with higher energy, so we discard it.
Correctness – BFS explores states in non‑decreasing move count, so the first full‑mask state is optimal. Obstacles and resets are correctly modeled, and all moves are reversible.

Complexity Analysis

Time – O(m * n * 2ᴸ * energy) in worst case, but pruning keeps it near O(m * n * 2ᴸ) because energy is bounded by 50 and dominated states are skipped.
Space – O(m * n * 2ᴸ) for bestEnergy, plus queue overhead.

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

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

MD ARIFUL HAQUE — Mon, 31 Aug 2026 16:54:40 +0000

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

Difficulty: Medium

Topics: Senior, Linked List, Weekly Contest 265

A critical point in a linked list is defined as either a local maxima or a local minima.

A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.

A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.

Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].

Example 1:

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
- The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
- The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
- Both the minimum and maximum distances are between the second and the fifth node.
- Thus, minDistance and maxDistance is 5 - 2 = 3.
- Note that the last node is not considered a local maxima because it does not have a next node.

Example 4:

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

Example 5:

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

Example 6:

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

Example 7:

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

Example 8:

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

Constraints:

The number of nodes in the list is in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Hint:

The maximum distance must be the distance between the first and last critical point.
For each adjacent critical point, calculate the difference and check if it is the minimum distance.

Solution:

We solve this problem by traversing the linked list once, identifying all critical points (local maxima and minima), and tracking their positions. We maintain the first critical point position, the previous critical point position, and calculate the minimum distance between adjacent critical points. The maximum distance is simply the difference between the first and last critical points.

Approach

Single Pass Traversal: Iterate through the linked list while maintaining three pointers: previous, current, and next nodes to evaluate each position
Critical Point Detection: For each node (except first and last), check if it's a local maxima (greater than both neighbors) or local minima (smaller than both neighbors)
Track Positions: Keep track of:
- First critical point index
- Previous critical point index (for calculating minimum distance)
- Current index while traversing
Distance Calculation:
- When a new critical point is found, calculate distance from previous critical point and update minimum distance
- Maximum distance is calculated at the end as the difference between last and first critical points
Edge Case Handling: Return [-1, -1] if fewer than 2 critical points are found

Let's implement this solution in PHP: 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

<?php
/**
 * @param Integer[] $c
 * @param Integer[][] $connections
 * @param Integer[][] $queries
 * @return Integer[]
 */
function nodesBetweenCriticalPoints($c, $connections, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation:

Initialization: We start with $result = [-1, -1] and set $minDistance = PHP_INT_MAX to track the minimum distance between critical points
Three-Pointer Technique: Using $previousNode, $currentNode, and $currentNode->next allows us to check if the current node satisfies the critical point conditions
Critical Point Detection:
- Local minima: $currentNode->val < $previousNode->val && $currentNode->val < $currentNode->next->val
- Local maxima: $currentNode->val > $previousNode->val && $currentNode->val > $currentNode->next->val
Index Tracking: $currentIndex starts at 1 (since head is at position 0) and increments with each node traversal
First Critical Point: When the first critical point is found, we set both $firstCriticalIndex and $previousCriticalIndex to the current index
Subsequent Critical Points: For each new critical point, we calculate the distance from the previous critical point and update $minDistance, then update $previousCriticalIndex
Final Computation: If at least two critical points exist ($minDistance != PHP_INT_MAX), we compute:
- $maxDistance = $previousCriticalIndex - $firstCriticalIndex (distance between first and last critical points)
- Return [$minDistance, $maxDistance]

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the linked list
- We traverse the list exactly once, performing constant-time operations at each node
- No additional passes or nested loops are required
Space Complexity: O(1)
- We only use a few variables to track indices and distances
- No extra data structures are used that scale with 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

2091. Removing Minimum and Maximum From Array

MD ARIFUL HAQUE — Sun, 30 Aug 2026 14:00:19 +0000

2091. Removing Minimum and Maximum From Array

Difficulty: Medium

Topics: Staff, Array, Greedy, Weekly Contest 269

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

There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

Example 1:

Input: nums = [2,10,7,5,4,1,8,6]
Output: 5
Explanation:
- The minimum element in the array is nums[5], which is 1.
- The maximum element in the array is nums[1], which is 10.
- We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
- This results in 2 + 3 = 5 deletions, which is the minimum number possible.

Example 2:

Input: nums = [0,-4,19,1,8,-2,-3,5]
Output: 3
Explanation:
- The minimum element in the array is nums[1], which is -4.
- The maximum element in the array is nums[2], which is 19.
- We can remove both the minimum and maximum by removing 3 elements from the front.
- This results in only 3 deletions, which is the minimum number possible.

Example 3:

Input: nums = [101]
Output: 1
Explanation:
- There is only one element in the array, which makes it both the minimum and maximum element.
- We can remove it with 1 deletion.

Example 4:

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

Example 5:

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

Example 6:

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

Example 7:

Input: nums = [-10, 5, -1, 10]
Output: 4

Example 8:

Input: nums = [100, -100, 0]
Output: 2

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
The integers in nums are distinct.

Hint:

There can only be three scenarios for deletions such that both minimum and maximum elements are removed:
Scenario 1: Both elements are removed by only deleting from the front.
Scenario 2: Both elements are removed by only deleting from the back.
Scenario 3: Delete from the front to remove one of the elements, and delete from the back to remove the other element.
Compare which of the three scenarios results in the minimum number of moves.

Solution:

We analyzed the problem and determined that the optimal strategy always falls into one of three possible deletion scenarios. By identifying the positions of the minimum and maximum elements, we can compute the cost of each scenario and return the smallest.

Approach

Find the indices of the minimum and maximum values in the array.
Since the array contains distinct integers, these indices are unique.
Consider three possible ways to delete both elements:
1. Delete only from the front.
2. Delete only from the back.
3. Delete one from the front and the other from the back.
Compute the number of deletions required for each scenario.
Return the minimum among the three.

Let's implement this solution in PHP: 2091. Removing Minimum and Maximum From Array

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

// Test cases
echo minimumDeletions([2, 10, 7, 5, 4, 1, 8, 6]) .  "\n";           // Output: 5
echo minimumDeletions([0, -4, 19, 1, 8, -2, -3, 5]) .  "\n";        // Output: 3
echo minimumDeletions([101]) .  "\n";                               // Output: 1
echo minimumDeletions([1, 2, 3]) .  "\n";                           // Output: 3
echo minimumDeletions([3, 2, 1]) .  "\n";                           // Output: 3
echo minimumDeletions([5, 1, 4, 2, 3]) .  "\n";                     // Output: 1
echo minimumDeletions([-10, 5, -1, 10]) .  "\n";                    // Output: 4
echo minimumDeletions([100, -100, 0]) .  "\n";                      // Output: 2
?>

Explanation:

Find min and max indices: Traverse the array once to locate the positions of the smallest and largest values.
Order indices: Let left = min(minIdx, maxIdx) and right = max(minIdx, maxIdx) for easier calculations.
Scenario 1 – Delete from front only: The farther element from the front is at max(left, right), so deletions needed = max(left, right) + 1.
Scenario 2 – Delete from back only: The farther element from the back is at min(left, right), so deletions needed = n - min(left, right).
Scenario 3 – Delete one from front and one from back:
- Remove the left element from front: left + 1 deletions.
- Remove the right element from back: n - right deletions.
- Total = (left + 1) + (n - right).
Edge case: If there is only one element, it is both min and max, and we remove it with 1 deletion.

Complexity Analysis

Time Complexity: O(n) — single traversal to find min and max indices.
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

3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

MD ARIFUL HAQUE — Fri, 28 Aug 2026 22:00:07 +0000

3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

Difficulty: Hard

Topics: Senior Staff, Two Pointers, String, Enumeration, Weekly Contest 474

You are given two strings s and target, each of length n, consisting of lowercase English letters.

Return the lexicographically smallest¹ string that is both a palindromic² permutation³ of s and strictly greater than target. If no such permutation exists, return an empty string.

Example 1:

Input: s = "baba", target = "abba"
Output: "baab"
Explanation:
- The palindromic permutations of s (in lexicographical order) are "abba" and "baab".
- The lexicographically smallest permutation that is strictly greater than target is "baab".

Example 2:

Input: s = "baba", target = "bbaa"
Output: ""
Explanation:
- The palindromic permutations of s (in lexicographical order) are "abba" and "baab".
- None of them is lexicographically strictly greater than target. Therefore, the answer is "".

Example 3:

Input: s = "abc", target = "abb"
Output: ""
Explanation: s has no palindromic permutations. Therefore, the answer is "".

Example 4:

Input: s = "aac", target = "abb"
Output: "aca"
Explanation:
- The only palindromic permutation of s is "aca".
- "aca" is strictly greater than target. Therefore, the answer is "aca".

Example 5:

Input: s = "aa", target = "aa"
Output: ""

Example 6:

Input: s = "aabb", target = "baaa"
Output: "abba"

Example 7:

Input: s = "zzz", target = "zzz"
Output: ""

Example 8:

Input: s = "abba", target = "aaaa"
Output: "abba"

Example 9:

Input: s = "aabbcc", target = "cccccc"
Output: ""

Example 10:

Input: s = "abcba", target = "abcba"
Output: ""

Constraints:

1 <= n == s.length == target.length <= 300
s and target consist of only lowercase English letters.

Hint:

A palindromic permutation exists only if at most one character has an odd count (for odd-length strings) or all counts are even (for even-length strings).
Focus on constructing the first half of the palindrome. The second half is determined by mirroring.
To be lexicographically greater than target, the first half must be greater than or equal to target's first half, with careful handling of the middle character for odd-length strings.
Use a backtracking approach or greedy selection for each position in the first half, trying the smallest available character that can still produce a valid palindrome.
After building the first half, mirror it (and add the middle character if needed) to form the full palindrome and verify it is strictly greater than target.

Solution:

We need to construct the lexicographically smallest palindrome permutation of s that is strictly greater than target. Since palindromes are determined entirely by their first half (plus an optional middle character), we reduce the problem to building the smallest valid first half that yields a full palindrome > target, using a greedy backtracking approach with pruning.

Approach

Verify that s has at least one palindromic permutation (at most one character with odd frequency).
Build a pool of characters available for the first half: each character count divided by 2.
Use backtracking to construct the first half position by position.
At each step, try to match target if possible; otherwise, pick the smallest available character that is greater than target[idx] to make the prefix strictly greater.
Once the first half is complete, mirror it, add the middle character if needed, and check if the resulting palindrome > target.
Return the first valid palindrome found (which will be lexicographically smallest).

Let's implement this solution in PHP: 3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

<?php
/**
 * @param String $s
 * @param String $target
 * @return String
 */
function lexPalindromicPermutation(string $s, string $target): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo lexPalindromicPermutation("baba", "abba") .  "\n";         // Output: "baab"
echo lexPalindromicPermutation("baba", "bbaa") .  "\n";         // Output: ""
echo lexPalindromicPermutation("abc", "abb") .  "\n";           // Output: ""
echo lexPalindromicPermutation("aac", "abb") .  "\n";           // Output: "aca"
echo lexPalindromicPermutation("aa", "aa") .  "\n";             // Output: ""
echo lexPalindromicPermutation("aabb", "baaa") .  "\n";         // Output: "abba"
echo lexPalindromicPermutation("zzz", "zzz") .  "\n";           // Output: ""
echo lexPalindromicPermutation("abba", "aaaa") .  "\n";         // Output: "abba"
echo lexPalindromicPermutation("aabbcc", "cccccc") .  "\n";     // Output: ""
echo lexPalindromicPermutation("abcba", "abcba") .  "\n";       // Output: ""
?>

Explanation:

Validity Check: A palindrome permutation exists iff at most one character has an odd count. If not, return "".
Pool Construction: We only need to permute the first half. For each character, we can use at most count / 2 occurrences.
Backtracking Logic:
- If the prefix is already greater than target's prefix, we simply pick the smallest available character for each remaining position.
- If the prefix is still equal to target's prefix, we first try to place the exact same character as target[idx]. If that fails, we try larger characters in ascending order.
- The recursion stops when the first half is full; then we construct the full palindrome and compare with target.
Lexicographic Minimality: Because we try characters in ascending order and stop at the first successful full palindrome, the result is lexicographically smallest.
Mirroring: For even n, palindrome = firstHalf + reverse(firstHalf). For odd n, palindrome = firstHalf + midChar + reverse(firstHalf).

Complexity Analysis

Time Complexity: O(n * 26⁽ⁿ/²⁾) in worst case, but with pruning it’s much faster. The pool limits choices significantly. For n ≤ 300, backtracking is efficient because the number of distinct characters is fixed (26) and we greedily stop early.
Space Complexity: O(n) for recursion stack and storage of the first half.

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: A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one. ↩
Palindrome: A palindrome is a string that reads the same forward and backward. ↩
Permutation: A permutation is a rearrangement of all the elements of a set. ↩

3720. Lexicographically Smallest Permutation Greater Than Target

MD ARIFUL HAQUE — Thu, 27 Aug 2026 17:52:36 +0000

3720. Lexicographically Smallest Permutation Greater Than Target

Difficulty: Medium

Topics: Staff, Hash Table, String, Greedy, Counting, Enumeration, Weekly Contest 472

You are given two strings s and target, both having length n, consisting of lowercase English letters.

Return the lexicographically smallest permutation¹ of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.

A string a is lexicographically strictly greater than a string b (of the same length) 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.

Example 1:

Input: s = "abc", target = "bba"
Output: "bca"
Explanation:
- The permutations of s (in lexicographical order) are "abc", "acb", "bac", "bca", "cab", and "cba".
- The lexicographically smallest permutation that is strictly greater than target is "bca".

Example 2:

Input: s = "leet", target = "code"
Output: "eelt"
Explanation:
- The permutations of s (in lexicographical order) are "eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", and "tlee".
- The lexicographically smallest permutation that is strictly greater than target is "eelt".

Example 3:

Input: s = "baba", target = "bbaa"
Output: ""
Explanation:
- The permutations of s (in lexicographical order) are "aabb", "abab", "abba", "baab", "baba", and "bbaa".
- None of them is lexicographically strictly greater than target. Therefore, the answer is "".

Example 4:

Input: s = "ab", target = "ab"
Output: "ba"

Example 5:

Input: s = "aab", target = "aba"
Output: "baa"

Example 6:

Input: s = "z", target = "a"
Output: "z"

Example 7:

Input: s = "cba", target = "cba"
Output: ""

Example 8:

Input: s = "aaa", target = "aab"
Output: ""

Example 9:

Input: s = "xyz", target = "abc"
Output: "xyz"

Example 10:

Input: s = "aabc", target = "abac"
Output: "abac"

Constraints:

1 <= s.length == target.length <= 300
s and target consist of only lowercase English letters.

Hint:

Maintain frequency counts of s.
Walk left-to-right; if equal to target[i] is possible, take it and continue.
If not, try the smallest letter strictly greater than target[i].
If neither, backtrack left to the most recent index where you matched target and try to bump there.

Solution:

We implement a greedy backtracking algorithm that constructs the lexicographically smallest permutation of s greater than target by first matching target from left to right as much as possible, then finding the rightmost position where we can place a larger character, and finally filling the remaining positions with the smallest available characters in ascending order.

Approach

Frequency Counting – Count occurrences of each character in s to track available letters.
Greedy Match – Iterate through target and consume matching characters from the frequency pool as long as possible.
Backtracking – Starting from the last matched position backward, restore consumed characters and attempt to place a character strictly larger than target[i].
Construction – Once a larger character is placed, fill the rest of the string with the remaining characters in ascending order to ensure lexicographic minimality.
Fallback – If no divergence point yields a valid permutation, return an empty string.

Let's implement this solution in PHP: 3720. Lexicographically Smallest Permutation Greater Than Target

<?php
/**
 * @param String $s
 * @param String $target
 * @return String
 */
function lexGreaterPermutation(string $s, string $target): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo lexGreaterPermutation("abc", "bba") .  "\n";       // Output: "bca"
echo lexGreaterPermutation("leet", "code") .  "\n";     // Output: "eelt"
echo lexGreaterPermutation("baba", "bbaa") .  "\n";     // Output: ""
echo lexGreaterPermutation("ab", "ab") .  "\n";         // Output: "ba"
echo lexGreaterPermutation("aab", "aba") .  "\n";       // Output: "baa"
echo lexGreaterPermutation("z", "a") .  "\n";           // Output: "z"
echo lexGreaterPermutation("cba", "cba") .  "\n";       // Output: ""
echo lexGreaterPermutation("aaa", "aab") .  "\n";       // Output: ""
echo lexGreaterPermutation("xyz", "abc") .  "\n";       // Output: "xyz"
echo lexGreaterPermutation("aabc", "abac") .  "\n";     // Output: "abac"
?>

Explanation:

Step 1 – Frequency Array: We create an array cnt[26] to store how many of each letter are available from s.
Step 2 – Longest Prefix Match: We walk through target from left to right. For each target[i], if we have that character available, we consume it and increase match_len. If not, we stop – this gives us the longest prefix of target that can be formed using characters from s.
Step 3 – Backtrack to Find Divergence: We iterate i from match_len down to 0.
- If i < match_len, we restore the character target[i] back into the pool (because we're undoing that match).
- Then, we try to find a character c > target[i] that is still available.
- The first such c found (smallest possible) gives us the optimal divergence point.
Step 4 – Build the Result
- The prefix is target[0..i-1] (already matched and fixed).
- The divergence character is c (the smallest greater letter available).
- The suffix is constructed by appending all remaining characters from the frequency array in ascending order – this guarantees the smallest possible continuation.
Edge Cases: If we exhaust all backtracking positions without finding a larger character, no permutation exists, so we return "".

Complexity Analysis

Time Complexity: O(n * 26) = O(n)
- Matching phase: O(n)
- Backtracking phase: at most n iterations, each scanning up to 26 characters → O(26n)
- Suffix construction: O(26 + n)
- Overall linear in n with a constant factor of 26.
Space Complexity: O(n)
- Frequency array: O(26)
- Prefix and suffix strings: O(n)
- Overall linear space relative to input length.

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

Permutation: A permutation is a rearrangement of all the characters of a string. ↩

2904. Shortest and Lexicographically Smallest Beautiful String

MD ARIFUL HAQUE — Wed, 26 Aug 2026 17:19:35 +0000

2904. Shortest and Lexicographically Smallest Beautiful String

Difficulty: Medium

Topics: Senior, String, Sliding Window, Weekly Contest 367

You are given a binary string s and a positive integer k.

A substring of s is beautiful if the number of 1's in it is exactly k.

Let len be the length of the shortest beautiful substring.

Return the lexicographically smallest beautiful substring of string s with length equal to len. If s doesn't contain a beautiful substring, return an empty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Example 1:

Input: s = "100011001", k = 3
Output: "11001"
Explanation:
- There are 7 beautiful substrings in this example:
- The substring "100011001".
- The substring "100011001".
- The substring "100011001".
- The substring "100011001".
- The substring "100011001".
- The substring "100011001".
- The substring "100011001".
- The length of the shortest beautiful substring is 5.
- The lexicographically smallest beautiful substring with length 5 is the substring "11001".

Example 2:

Input: s = "1011", k = 2
Output: "11"
Explanation:
- There are 3 beautiful substrings in this example:
- The substring "1011".
- The substring "1011".
- The substring "1011".
- The length of the shortest beautiful substring is 2.
- The lexicographically smallest beautiful substring with length 2 is the substring "11".

Example 3:

Input: s = "000", k = 1
Output: ""
Explanation: There are no beautiful substrings in this example.

Example 4:

Input: s = "111", k = 3
Output: "111"

Example 5:

Input: s = "01010", k = 1
Output: "1"

Example 6:

Input: s = "10101", k = 2
Output: "101"

Example 7:

Input: s = "1111", k = 2
Output: "11"

Example 8:

Input: s = "1001", k = 4
Output: ""

Constraints:

1 <= s.length <= 100
1 <= k <= s.length

Hint:

Notice that if we consider that index i is the leftmost index of a beautiful substring, it has only one candidate j, such that s[i:j] is beautiful and shortest too.
We can iterate over all possibilities of leftmost index i take s[i:j] and compare with the shortest and the lexicographically smallest beautiful string we could get before index i.

Solution:

We solve the problem by iterating through all possible starting positions in the string, extending each substring until we find exactly k ones, which gives us the shortest beautiful substring starting at that position. We then track the global minimum length and lexicographically smallest among substrings of that minimum length, ensuring an efficient and correct solution.

Approach

Brute force with early termination: For each starting index i, we extend the substring to the right, counting ones until we either exceed k (break) or reach exactly k ones.
Candidate selection: When we reach exactly k ones, the current substring is the shortest beautiful substring starting at i (since extending further would only increase length unnecessarily).
Global comparison: We compare this candidate with our best result so far—preferring shorter length first, and for equal lengths, the lexicographically smaller string.
Edge case handling: If no beautiful substring is found (less than k ones total), return an empty string.

Let's implement this solution in PHP: 2904. Shortest and Lexicographically Smallest Beautiful String

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

// Test cases
echo shortestBeautifulSubstring("100011001", 3) . "\n";     // Output: "11001"
echo shortestBeautifulSubstring("10110", 3) . "\n";         // Output: "110"
echo shortestBeautifulSubstring("000", 1) . "\n";           // Output: ""
echo shortestBeautifulSubstring("111", 3) . "\n";           // Output: "111"
echo shortestBeautifulSubstring("01010", 1) . "\n";         // Output: "1"
echo shortestBeautifulSubstring("10101", 2) . "\n";         // Output: "101"
echo shortestBeautifulSubstring("1111", 2) . "\n";          // Output: "11"
echo shortestBeautifulSubstring("1001", 4) . "\n";          // Output: ""
?>

Explanation:

Sliding window concept: We don't use a traditional sliding window, but rather a nested loop where the inner loop stops as soon as the condition is met, making it efficient for each start position.
Why break after finding k ones: For a fixed start i, the first time we reach k ones gives the shortest length possible. Any longer substring starting at i would be longer and thus not needed for shortest-length consideration.
Lexicographical comparison: PHP's string comparison (<) works lexicographically, so we can directly compare substrings of the same length.
Time complexity optimization: The inner loop breaks early, and the total operations are bounded by the number of substrings considered (at most n² in worst case, but with pruning).

Complexity Analysis

Time Complexity: O(n²) in the worst case, where n is the length of s. Although we have nested loops, the inner loop terminates early when k ones are found or exceeded. In a string with sparse ones, it may scan more, but with n ≤ 100, this is acceptable.
Space Complexity: O(n) for storing the substring and the result, or O(1) if we consider only the output string length.

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

3718. Smallest Missing Multiple of K

MD ARIFUL HAQUE — Tue, 25 Aug 2026 18:15:39 +0000

3718. Smallest Missing Multiple of K

Difficulty: Easy

Topics: Mid Level, Array, Hash Table, Weekly Contest 472

Given an integer array nums and an integer k, return the smallest positive multiple of k that is missing from nums.

A multiple of k is any positive integer divisible by k.

Example 1:

Input: nums = [8,2,3,4,6], k = 2
Output: 10
Explanation: The multiples of k = 2 are 2, 4, 6, 8, 10, 12... and the smallest multiple missing from nums is 10.

Example 2:

Input: nums = [1,4,7,10,15], k = 5
Output: 5
Explanation: The multiples of k = 5 are 5, 10, 15, 20... and the smallest multiple missing from nums is 5.

Example 3:

Input: nums = [2,4,6,8,10], k = 2
Output: 12

Example 4:

Input: nums = [5,10,15,20], k = 5
Output: 25

Example 5:

Input: nums = [3,6,9,12,15], k = 3
Output: 18

Example 6:

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

Example 7:

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

Example 8:

Input: nums = [1,4,7,10,15], k = 5
Output: 5

Constraints:

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

Hint:

Add the values in nums to a hash set
Iterate through the positive multiples of k and return the first one not in the hash set

Solution:

We solve the problem by first storing all array elements in a hash set for O(1) lookups. We then iterate upward through positive multiples of k starting from k itself, and return the first multiple that is not present in the set. This ensures the smallest missing multiple is found efficiently.

Approach

Use a hash set – Convert the array into a hash set (via array_flip) to quickly check membership.
Start from the first positive multiple – Begin checking from k (the smallest positive multiple of k).
Increment by k – Move to the next multiple (+= k) until we find one not in the set.
Return the missing multiple – The first missing multiple encountered is the answer.

Let's implement this solution in PHP: 3718. Smallest Missing Multiple of K

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

// Test cases
echo missingMultiple([8,2,3,4,6], 2) .  "\n";               // Output: 10
echo missingMultiple([1,4,7,10,15], 5) .  "\n";             // Output: 5
echo missingMultiple([2,4,6,8,10], 2) .  "\n";              // Output: 12
echo missingMultiple([5,10,15,20], 5) .  "\n";              // Output: 25
echo missingMultiple([3,6,9,12,15], 3) .  "\n";             // Output: 18
echo missingMultiple([1,2,3,4,5,6,7,8,9,10], 1) .  "\n";    // Output: 11
echo missingMultiple([100], 1) .  "\n";                     // Output: 2
echo missingMultiple([1,2,3], 4) .  "\n";                   // Output: 4
?>

Explanation:

Step 1: $set = array_flip($nums); – This creates a hash map where keys are the array values, enabling constant-time existence checks.
Step 2: $multiple = $k; – We start with the smallest positive multiple of k.
Step 3: while (isset($set[$multiple])) { $multiple += $k; } – Keep advancing to the next multiple while the current one exists in the set.
Step 4: Once the loop exits, $multiple is the smallest multiple of k not present in nums, so we return it.

Complexity Analysis

Time Complexity: O(n + m) where n is the number of elements in nums (to build the set) and m is the number of multiples we check until we find a missing one. In the worst case, m could be up to the largest multiple present plus k, but since constraints are small (≤100), this is effectively constant.
Space Complexity: O(n) – for the hash set storing up to n unique values.

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

1872. Stone Game VIII

MD ARIFUL HAQUE — Mon, 24 Aug 2026 15:29:26 +0000

1872. Stone Game VIII

Difficulty: Hard

Topics: Senior Staff, Array, Math, Dynamic Programming, Minimax, Prefix Sum, Game Theory, Zero-Sum Game, Weekly Contest 242

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

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones' values to the player's score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is to minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the iᵗʰ stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on the left. stones = [-3].
- The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a stone of value 13 on the left. stones = [13].
- The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her score and places a stone of value -22 on the left. stones = [-22].
- The difference between their scores is (-22) - 0 = -22.

Example 4:

Input: stones = [1,2,3,4]
Output: 10

Example 5:

Input: stones = [-1,-2,-3,-4]
Output: -10

Example 6:

Input: stones = [5,0,-5,10]
Output: 10

Example 7:

Input: stones = [100, -100]
Output: 0

Example 8:

Input: stones = [-5, -3]
Output: -8

Example 9:

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

Example 10:

Input: stones = [100, -50]
Output: 50

Constraints:

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

Hint:

Let's note that the only thing that matters is how many stones were removed so we can maintain dp[numberOfRemovedStones]
dp[x] = max(sum of all elements up to y - dp[y]) for all y > x

Solution:

We present a dynamic programming solution that computes the optimal score difference in Stone Game VIII. By leveraging prefix sums and a backward DP state, we efficiently determine the maximum difference Alice can guarantee, given optimal play from both players. The solution runs in O(n) time and O(n) space, making it feasible for n up to 1e5.

Approach

The game state after any move is completely determined by the current leftmost stone’s value, which is the prefix sum up to some index i.
We define dp[i] as the maximum score difference the current player can achieve when the game starts with a single stone of value prefix[i] (i.e., the first i+1 original stones have been merged).
If only two stones remain (i.e., i = n-2), the current player must take both, so dp[n-2] = prefix[n-1].
For i < n-2, the current player can either:
- Take all remaining stones immediately (score = prefix[n-1]), or
- Take x stones (where x > 1) and leave the opponent with a state starting at prefix[i+1], with the opponent's optimal difference being dp[i+1]. The current player’s difference then becomes prefix[i+1] - dp[i+1].
We maximize over these two choices, which reduces to dp[i] = max(dp[i+1], prefix[i+1] - dp[i+1]).
We compute dp from right to left and return dp[0].

Let's implement this solution in PHP: 1872. Stone Game VIII

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

// Test cases
echo stoneGameVIII([-1,2,-3,4,-5]) .  "\n";             // Output: 5
echo stoneGameVIII([7,-6,5,10,5,-2,-6]) .  "\n";        // Output: 13
echo stoneGameVIII([-10,-12]) .  "\n";                  // Output: -22
echo stoneGameVIII([1,2,3,4]) .  "\n";                  // Output: 10
echo stoneGameVIII([-1,-2,-3,-4]) .  "\n";              // Output: -10
echo stoneGameVIII([5,0,-5,10]) .  "\n";                // Output: 10
echo stoneGameVIII([100, -100]) .  "\n";                // Output: 0
echo stoneGameVIII([-5, -3]) .  "\n";                   // Output: -8
echo stoneGameVIII([3, -1, 2, -4, 5]) .  "\n";          // Output: 5
echo stoneGameVIII([100, -50]) .  "\n";                 // Output: 50
?>

Explanation:

Prefix sums are precomputed so that prefix[i] equals the sum of the first i+1 stones. This represents the value of the merged stone after removing the first i+1 stones.
DP state definition is crucial: dp[i] is the best score difference for the player whose turn it is, assuming the row starts with one stone whose value is prefix[i].
Base case: When i = n-2, there are exactly two stones (the merged stone of value prefix[n-2] and the last original stone stones[n-1]). The only legal move is to remove both, so the difference is prefix[n-1] - 0 = prefix[n-1].
Recurrence: For i < n-2, the current player has two options:
1. Take all: remove all remaining stones, get prefix[n-1] directly.
2. Take some but not all: remove x > 1 stones, which corresponds to moving to state i+1. The current player gains prefix[i+1], and then the opponent will get dp[i+1] from the new state, so the net difference is prefix[i+1] - dp[i+1].
Since dp[i+1] already represents optimal play from the next state, we only need to choose the maximum between dp[i+1] and prefix[i+1] - dp[i+1].
We iterate backwards from n-3 down to 0 because dp[i] depends only on dp[i+1] and prefix[i+1].
Finally, dp[0] gives the answer, as the game initially starts with a row of n stones, equivalent to a single stone of value prefix[0] = stones[0] after removing 0 stones – but since the first move must remove at least 2 stones, our recurrence correctly handles that.

Complexity Analysis

Time complexity: O(n) – we compute prefix sums in one pass, then fill the DP array in a second pass.
Space complexity: O(n) – we store prefix sums and the DP array. This can be optimized to O(1) extra space by keeping only the last DP value, but O(n) is acceptable given constraints.

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

1927. Sum Game

MD ARIFUL HAQUE — Sun, 23 Aug 2026 14:54:20 +0000

1927. Sum Game

Difficulty: Medium

Topics: Staff, Math, String, Greedy, Game Theory, Biweekly Contest 56

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

You are given a string num of even length consisting of digits and '?' characters. On each turn, a player will do the following if there is still at least one '?' in num:

Choose an index i wherenum[i] == '?'.
Replace num[i] with any digit between '0' and '9'.

The game ends when there are no more '?' characters in num.

For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal.

For example, if the game ended with num = "243801", then Bob wins because 2+4+3 = 8+0+1. If the game ended with num = "243803", then Alice wins because 2+4+3 != 8+0+3.

Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.

Example 1:

Input: num = "5023"
Output: false
Explanation:
- There are no moves to be made.
- The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.

Example 2:

Input: num = "25??"
Output: true
Explanation: Alice can replace one of the '?'s with '9' and it will be impossible for Bob to make the sums equal.

Example 3:

Input: num = "?3295???"
Output: false
Explanation:
- It can be proven that Bob will always win. One possible outcome is:
  - Alice replaces the first '?' with '9'. num = "93295???".
  - Bob replaces one of the '?' in the right half with '9'. num = "932959??".
  - Alice replaces one of the '?' in the right half with '2'. num = "9329592?".
  - Bob replaces the last '?' in the right half with '7'. num = "93295927".
- Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.

Example 4:

Input: num = "16?5?0592?99852?270?94852?5821?863?303??07956??562578340?36?6281545?8682?867?403158?7311994090401?361520?8?181?8?5?1912??586736786656018??4147039?37??652?13182825323368664640397951??499?747492?7160?618?61888381078443?6215195?526542088744?7???563434803?690?7312353?81190762?7818206558023797??4600?7?2?0726268?3294?84668593?93?4275?86546?046?64703?944?2608860?97887?27387??963980505594569?215?116063214573??89383032613351720611698683?85?6408880?4?1?121921229??7?00??997?7618427?90?691??945??592?5433?563???51?132?70232?11993893??9399628?9884??8238087987892442?968020?052?881788?31956843855?73?3?501796465409700142??90552?594?084687556239093350764??07551???37?46?85?0?11823??087842521862230819711211?98?8?6?343786343474249?901???71?54??397448634???96??75440209987096739?8?09998278??11?203924746???047880944?0?9??312381?29?80667?5?52?7?5850???73?3?80806235573?02?41?605749?46118???1??512????39?51230??411193?0982131497873115360408265208??35?37?2557172941?57?3??9036688122?500?164052?889649284069121?913?5??4?9?983?0?825490?4555594?54429459231994??3?984?934504846?8?1521?196??1653303?916056447?9?36?746665603?581109763292?4?9?55239747???008703538648686868740?3?262?127?667?0027??56465142?1??9524168?1809713?00??5603?818?666?99610?8783004661?6?45?6088079780?9?73929?44807?192158?56?3521396?7???58?9705336?2?6?33?7254236629272543060090974?9?5116??011???2?37?87?860?0?26?984?8168?213757??67623030?744?5827454?387204?04988?1687338660208?6493?0337684854228?94075283086641467477156??26?276376630??1?56579415963?6?98??1562??843?2?3516?99151776?5306?8181234203894?4882459?7765?6815?21??3??489480?8239125848?625?7096?622?6?4?6?265560?0005738?74?1786171851816??38079752007905890?0643124??8?6??40206?262?21?2473282183985?938?3488?51883?12??8??251?7540453?1?97291177797304474?5?33?932491??9139?01?830?785?9041?497236260938474555400?6?0150115?2170987731414??8?8?707188?77982?758154303??66?67?8?140?26?0?420?52?517?273382?5??20182?7?802?235?0042509175051542?01?7027307?0919?1141168760538?925?2795???7018?6?455815710776?160237?362198081905?757844?4626?3591?3?915?9?77389101?1?81779?39728096?0460080?5?87?80010?117??9395??12167450??3475531078328?1?25?27755167?067?5742?518733799?67588366725789?18?48?430?85907156?70?163?0364?01?9292?969?87030825?178?5??16465544?1347?461?297457?393630?277??71?0??6999?8?747??5154642642177694236??702541?036008?2?9773?98?17908498?6180?606634316?02802?130448915?01509?711?713?72321??18404??24???6362427???423??3?0????515347?911221?6?95??8??9?7909?3781544427?28????8??57?81?315?24665077513???6?51?813133?2?132?0886?79686?97612991289?303?5??646??1?63???6186156452?698?90040???08831?930389?204?2?1007?9?2205007474?976?095?92??5??17?06????5948?79?066737?2?788?3103980?582???82?2??2?4042?56766214?204?89?0?66682845161?789649?50?2764247348?036321?2245?27527930?34??79025???809502116?9540666?0561?57?0245??78008409?73?1??4??0236277?360?67094605394349650?78?2?57140960?30119?3??35?03??4486965?619570997001?7628??874079502996746151?62652120?12?44981?89846?80?21112208813233967125?9?5???312?1490983265?53?41?9?78304186230218093?20120603?1707?896555302767?7394?61684?89?3042?4871615019?7?865157?0?1?61632296?9?2509929281?138719249?756?434896??0?335011073?8?14455?02694?5181?5?15?74705689?2423?0??81??4?7512?44?09074123?91060?9193776?769?7?729?908627?56?831342875433?1638????068647?817977041271257?1??46????2179137?69799986?6118?5703?21?5906?363924?7674581?628304971828293?999?84?51?19227639363?4?67?12?2930126488061?060?7?41?69040805533?2?553??0?86?08?5480??7060645692071577493241620355960???579?6?3184095649?138542?774416430006?35120392"
Output: true

Example 5:

Input: num = "1?2"
Output: invalid length, not even

Example 6:

Input: num = "????"
Output: true

Example 7:

Input: num = "0000"
Output: false

Example 8:

Input: num = "9?9?"
Output: true

Example 9:

Input: num = "??99"
Output: false

Example 10:

Input: num = "123456"
Output: false

Example 11:

Input: num = "??????????"
Output: true

Constraints:

2 <= num.length <= 10⁵
num.length is even.
num consists of only digits and '?'.

Hint:

Bob can always make the total sum of both sides equal in mod 9.
Why does the difference between the number of question marks on the left and right side matter?

Solution:

We analyze the game as a zero-sum optimization where each side has a sum we want to make unequal (Alice) or equal (Bob). By treating unknown digits as having an expected value of 4.5 when replaced optimally, we can reduce the game to comparing fixed sums and the number of question marks on each half.

Approach

Compute the difference between the sum of known digits in the left half and the right half.
Count the number of question marks in each half.
On each turn, a player can choose a '?' and set it to any digit 0–9.
Since each '?' can be thought of as contributing an average of 4.5 in optimal play, the game outcome depends on:
- The known sum difference.
- The difference in the count of '?' on left vs right side.
If the total possible adjustment range (9 × number of '?') can make the sums equal, Bob can force equality; otherwise Alice can force inequality.

Let's implement this solution in PHP: 1927. Sum Game

<?php
/**
 * @param String $num
 * @return Boolean
 */
function sumGame(string $num): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param String $c
 * @return Float
 */
function getExpectation(string $c): float
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumGame("5023") .  "\n";           // Output: false
echo sumGame("25??") .  "\n";           // Output: true
echo sumGame("?3295???") .  "\n";       // Output: false
$num = "16?5?0592?99852?270?94852?5821?863?303??07956??562578340?36?6281545?8682?867?403158?7311994090401?361520?8?181?8?5?1912??586736786656018??4147039?37??652?13182825323368664640397951??499?747492?7160?618?61888381078443?6215195?526542088744?7???563434803?690?7312353?81190762?7818206558023797??4600?7?2?0726268?3294?84668593?93?4275?86546?046?64703?944?2608860?97887?27387??963980505594569?215?116063214573??89383032613351720611698683?85?6408880?4?1?121921229??7?00??997?7618427?90?691??945??592?5433?563???51?132?70232?11993893??9399628?9884??8238087987892442?968020?052?881788?31956843855?73?3?501796465409700142??90552?594?084687556239093350764??07551???37?46?85?0?11823??087842521862230819711211?98?8?6?343786343474249?901???71?54??397448634???96??75440209987096739?8?09998278??11?203924746???047880944?0?9??312381?29?80667?5?52?7?5850???73?3?80806235573?02?41?605749?46118???1??512????39?51230??411193?0982131497873115360408265208??35?37?2557172941?57?3??9036688122?500?164052?889649284069121?913?5??4?9?983?0?825490?4555594?54429459231994??3?984?934504846?8?1521?196??1653303?916056447?9?36?746665603?581109763292?4?9?55239747???008703538648686868740?3?262?127?667?0027??56465142?1??9524168?1809713?00??5603?818?666?99610?8783004661?6?45?6088079780?9?73929?44807?192158?56?3521396?7???58?9705336?2?6?33?7254236629272543060090974?9?5116??011???2?37?87?860?0?26?984?8168?213757??67623030?744?5827454?387204?04988?1687338660208?6493?0337684854228?94075283086641467477156??26?276376630??1?56579415963?6?98??1562??843?2?3516?99151776?5306?8181234203894?4882459?7765?6815?21??3??489480?8239125848?625?7096?622?6?4?6?265560?0005738?74?1786171851816??38079752007905890?0643124??8?6??40206?262?21?2473282183985?938?3488?51883?12??8??251?7540453?1?97291177797304474?5?33?932491??9139?01?830?785?9041?497236260938474555400?6?0150115?2170987731414??8?8?707188?77982?758154303??66?67?8?140?26?0?420?52?517?273382?5??20182?7?802?235?0042509175051542?01?7027307?0919?1141168760538?925?2795???7018?6?455815710776?160237?362198081905?757844?4626?3591?3?915?9?77389101?1?81779?39728096?0460080?5?87?80010?117??9395??12167450??3475531078328?1?25?27755167?067?5742?518733799?67588366725789?18?48?430?85907156?70?163?0364?01?9292?969?87030825?178?5??16465544?1347?461?297457?393630?277??71?0??6999?8?747??5154642642177694236??702541?036008?2?9773?98?17908498?6180?606634316?02802?130448915?01509?711?713?72321??18404??24???6362427???423??3?0????515347?911221?6?95??8??9?7909?3781544427?28????8??57?81?315?24665077513???6?51?813133?2?132?0886?79686?97612991289?303?5??646??1?63???6186156452?698?90040???08831?930389?204?2?1007?9?2205007474?976?095?92??5??17?06????5948?79?066737?2?788?3103980?582???82?2??2?4042?56766214?204?89?0?66682845161?789649?50?2764247348?036321?2245?27527930?34??79025???809502116?9540666?0561?57?0245??78008409?73?1??4??0236277?360?67094605394349650?78?2?57140960?30119?3??35?03??4486965?619570997001?7628??874079502996746151?62652120?12?44981?89846?80?21112208813233967125?9?5???312?1490983265?53?41?9?78304186230218093?20120603?1707?896555302767?7394?61684?89?3042?4871615019?7?865157?0?1?61632296?9?2509929281?138719249?756?434896??0?335011073?8?14455?02694?5181?5?15?74705689?2423?0??81??4?7512?44?09074123?91060?9193776?769?7?729?908627?56?831342875433?1638????068647?817977041271257?1??46????2179137?69799986?6118?5703?21?5906?363924?7674581?628304971828293?999?84?51?19227639363?4?67?12?2930126488061?060?7?41?69040805533?2?553??0?86?08?5480??7060645692071577493241620355960???579?6?3184095649?138542?774416430006?35120392";
echo sumGame($num) .  "\n";             // Output: true
echo sumGame("1?2") .  "\n";            // Output: invalid length, not even
echo sumGame("????") .  "\n";           // Output: true
echo sumGame("0000") .  "\n";           // Output: false
echo sumGame("9?9?") .  "\n";           // Output: true
echo sumGame("??99") .  "\n";           // Output: false
echo sumGame("123456") .  "\n";         // Output: false
echo sumGame("??????????") .  "\n";     // Output: true
?>

Explanation:

Let leftSum = sum of known digits in the left half, rightSum = sum of known digits in right half.
Let leftQ = number of '?' in left half, rightQ = number of '?' in right half.
Define diff = leftSum - rightSum.
Each '?' can be replaced by a digit 0–9, which changes the sum difference by some value between -9 and +9 per '?'.
Bob wants to make final diff = 0.
The maximum possible adjustment Bob can make is by using the question marks to close the gap. Since Alice moves first and plays optimally to keep diff ≠ 0, the key insight:
- If leftQ == rightQ, only the known sum diff matters.
- If leftQ != rightQ, the player who moves last on the side with more '?' can decide the outcome.
With optimal play, the game reduces to:
- If diff == 0 and leftQ == rightQ, Bob wins (false).
- Else if the difference between question marks is even and diff can be offset by 9 × (difference in '?') / 2, Bob can force equality.
However, using the expectation method (each '?' → 4.5) simplifies the check:
- Compute expectedDiff = leftSum - rightSum + 4.5 * (leftQ - rightQ).
- If expectedDiff == 0, Bob can force a draw; else Alice can force inequality.

Complexity Analysis

Time: O(n) – single pass through the string.
Space: O(1) – only a few integer variables.

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