DEV Community: MD ARIFUL HAQUE

2747. Count Zero Request Servers

MD ARIFUL HAQUE — Fri, 06 Nov 2026 20:13:19 +0000

2747. Count Zero Request Servers

Difficulty: Medium

Topics: Staff, Array, Hash Table, Sliding Window, Sorting, Biweekly Contest 107

You are given an integer n denoting the total number of servers and a 2D 0-indexed integer array logs, where logs[i] = [server_id, time] denotes that the server with id server_id received a request at time time.

You are also given an integer x and a 0-indexed integer array queries.

Return a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].

Note that the time intervals are inclusive.

Example 1:

Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
Explanation:
- For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests.
- For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.

Example 2:

Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
Output: [0,1]
Explanation:
- For queries[0]: All servers get at least one request in the duration of [1, 3].
- For queries[1]: Only server with id 3 gets no request in the duration [2,4]. Example 3:
Input: n = 1, logs = [[1,1]], x = 1, queries = [2]
Output: [0]

Example 4:

Input: n = 1, logs = [[1,1]], x = 1, queries = [100]
Output: [1]

Example 5:

Input: n = 4, logs = [[1,10]], x = 5, queries = [10]
Output: [3]

Example 6:

Input: n = 3, logs = [[1,1],[2,2],[3,3]], x = 10, queries = [100]
Output: [3]

Example 7:

Input: n = 3, logs = [[1,1],[2,2],[3,3]], x = 1, queries = [1,2,3]
Output: [2,1,1]

Example 8:

Input: n = 5, logs = [[1,5],[1,5],[2,5]], x = 3, queries = [5]
Output: [3]

Example 9:

Input: n = 2, logs = [[1,1],[2,2]], x = 5, queries = [1,2,3,4,5]
Output: [1,0,0,0,0]

Example 10:

Input: n = 3, logs = [[1,1],[2,1],[3,1]], x = 2, queries = [1,2,3,4]
Output: [0,0,0,3]

Example 11:

Input: n = 10, logs = [[1,1],[1,1000000]], x = 1, queries = [1,1000000]
Output: [9,9]

Example 12:

Input: n = 100000, logs = [[i,i] for i in 1..100000], x = 1, queries = [1,2,...,100000]
Output: [99999, 99998, 99998, ..., 99998]

Constraints:

1 <= n <= 10⁵
1 <= logs.length <= 10⁵
1 <= queries.length <= 10⁵
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10⁶
1 <= x <= 10⁵
x < queries[i] <= 10⁶

Hint:

Can we use sorting and two-pointer approach here?
Sort the queries array and logs array based on time in increasing order.
For every window of size x, use sliding window and two-pointer approach to find the answer to the queries.

Solution:

We solve this problem by using a sliding window with sorting and two-pointer technique. Since queries may arrive out of order, we first sort both the logs and queries by time. For each query in ascending order, we maintain a sliding window [query - x, query] that contains only those log entries whose timestamps fall within this range. A frequency map (freq) tracks how many requests each server has within the window, and activeServers counts the number of distinct servers that have received at least one request in the window. The answer for each query is n - activeServers (total servers minus active servers). Because the window moves monotonically forward with sorted queries, each log entry is added once and removed once, giving near-linear performance.

Approach

Sort the logs by time — so we can process them in chronological order as the window moves forward.
Sort the queries by value while keeping original indices — because the window must expand/shrink monotonically; we store [queryValue, originalIndex] pairs.
Use two pointers left and right over the sorted logs:
- right pointer adds logs whose time <= query (i.e., inside the upper bound of the window).
- left pointer removes logs whose time < query - x (i.e., outside the lower bound of the window).
Maintain a frequency array freq[serverId] and an activeServers counter:
- When a server's frequency changes from 0 → 1, increment activeServers.
- When it changes from 1 → 0, decrement activeServers.
Record the result for each query as n - activeServers in the corresponding original index.

Let's implement this solution in PHP: 2747. Count Zero Request Servers

<?php
/**
 * @param Integer $n
 * @param Integer[][] $logs
 * @param Integer $x
 * @param Integer[] $queries
 * @return Integer[]
 */
function countServers(int $n, array $logs, int $x, array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countServers(3, [[1,3],[2,6],[1,5]], 5, [10,11]) .  "\n";                      // Output: [1, 2]
echo countServers(3, [[2,4],[2,1],[1,2],[3,1]], 2, [3,4]) .  "\n";                  // Output: [0, 1]
echo countServers(1, [[1,1]], 1, [2]) .  "\n";                                      // Output: [0]
echo countServers(1, [[1,1]], 1, [100]) .  "\n";                                    // Output: [1]
echo countServers(4, [[1,10]], 5, [10]) .  "\n";                                    // Output: [3]
echo countServers(3, [[1,1],[2,2],[3,3]], 10, [100]) .  "\n";                       // Output: [0]
echo countServers(3, [[1,1],[2,2],[3,3]], 1, [1,2,3]) .  "\n";                      // Output: [2, 2, 2]
echo countServers(5, [[1,5],[1,5],[2,5]], 3, [5]) .  "\n";                          // Output: [3]
echo countServers(2, [[1,1],[2,2]], 5, [1,2,3,4,5]) .  "\n";                        // Output: [1, 0, 0, 0, 0]
echo countServers(3, [[1,1],[2,1],[3,1]], 2, [1,2,3,4]) .  "\n";                    // Output: [0, 0, 3, 3]
echo countServers(10, [[1,1],[1,1000000]], 1, [1,1000000]) .  "\n";                 // Output: [9, 9]

// Stress test case (max constraints)
$logs = array_map(fn($i) => [$i, $i], range(1, 100000));
$queries = range(1, 100000);
echo countServers(100000, $logs, 1, $queries) .  "\n";                              // Output: Array of 100000 elements, each 99999
?>

Explanation

Sorting logs: Logs are given unsorted; sorting them ensures we can add them to the window as right advances and remove them as left advances without ever needing to look back.
Sorting queries with indices: Since queries come in arbitrary order, we need to answer them in ascending order for the sliding window to only move forward (not backward). We map each answer back to the original query position at the end.
Window expansion (right pointer): For a given query q, we include every log with time <= q. This builds the right edge of the window [q - x, q].
Window contraction (left pointer): We then evict every log with time < q - x, keeping the window inclusive on both sides. Since q is non-decreasing across sorted queries, left never needs to move backward.
activeServers counter: Rather than recounting distinct servers each time, we update this counter incrementally:
- When a log for server s is added and freq[s] goes from 0 → 1, that server becomes "active".
- When a log for server s is removed and freq[s] goes from 1 → 0, that server becomes "inactive".
Answer computation: The number of servers that received zero requests in the window is simply n - activeServers.
Edge cases handled:
- Duplicate log entries for the same server at different times are handled by counting in freq.
- Multiple logs for the same server at the same time are also handled naturally.
- The window is inclusive on both ends, matching the problem statement.

Complexity Analysis

Time Complexity: O(L log L + Q log Q + L + Q) where:
- L = logs.length, Q = queries.length.
- Sorting logs: O(L log L).
- Sorting queries: O(Q log Q).
- Two-pointer sweep over logs: O(L) total (each log is added once and removed at most once).
- Processing queries: O(Q).
- Overall: O(L log L + Q log Q).
Space Complexity: O(n + Q + L) due to:
- freq array of size n + 1.
- sortedQueries array of size Q.
- ans array of size Q.
- Sorting overhead for logs (in place) and sortedQueries.

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

1385. Find the Distance Value Between Two Arrays

MD ARIFUL HAQUE — Thu, 05 Nov 2026 18:21:08 +0000

1385. Find the Distance Value Between Two Arrays

Difficulty: Easy

Topics: Mid Level, Array, Two Pointers, Binary Search, Sorting, Biweekly Contest 22

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elementsarr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation:
- For arr1[0]=4 we have:

      |4-10|=6 > d=2
      |4-9|=5 > d=2
      |4-1|=3 > d=2
      |4-8|=4 > d=2

For arr1[1]=5 we have:

      |5-10|=5 > d=2
      |5-9|=4 > d=2
      |5-1|=4 > d=2
      |5-8|=3 > d=2

For arr1[2]=8 we have:

      |8-10|=2 <= d=2
      |8-9|=1 <= d=2
      |8-1|=7 > d=2
      |8-8|=0 <= d=2

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

Example 4:

Input: arr1 = [1], arr2 = [1], d = 0
Output: 0

Example 5:

Input: arr1 = [1], arr2 = [2], d = 1
Output: 0

Example 6:

Input: arr1 = [1], arr2 = [5], d = 1
Output: 1

Example 7:

Input: arr1 = [10,20], arr2 = [1,2,3], d = 3
Output: 2

Example 8:

Input: arr1 = [-1000], arr2 = [1000], d = 100
Output: 1

Example 9:

Input: arr1 = [0,5,10], arr2 = [0,5,10], d = 0
Output: 0

Constraints:

1 <= arr1.length, arr2.length <= 500
-1000 <= arr1[i], arr2[j] <= 1000
0 <= d <= 100

Hint:

Sort 'arr2' and use binary search to get the closest element for each 'arr1[i]', it gives a time complexity of O(nlogn).

Solution:

We solve this by sorting arr2 once and, for each element in arr1, using binary search to find its insertion position. The only elements in arr2 that could possibly satisfy |arr1[i] - arr2[j]| <= d are the closest ones on either side of arr1[i] (the predecessor and successor). If neither of those two neighbors is within distance d, then no element in arr2 is, so we count arr1[i] toward the distance value.

Approach

Sort arr2 in ascending order so we can binary search it.
Iterate over every value x in arr1.
For each x, binary search arr2 for the first index pos where arr2[pos] >= x (the lower bound).
Only two candidates can be "closest" to x:
- arr2[pos] — the smallest element >= x (right neighbor).
- arr2[pos - 1] — the largest element < x (left neighbor).
If the absolute difference between x and both candidates is > d, increment the distance value.
Return the total count.

Let's implement this solution in PHP: 1385. Find the Distance Value Between Two Arrays

<?php
/**
 * @param Integer[] $arr1
 * @param Integer[] $arr2
 * @param Integer $d
 * @return Integer
 */
function findTheDistanceValue(array $arr1, array $arr2, int $d): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation

Why only two neighbors matter: After sorting, elements are monotonic. If x is between arr2[k-1] and arr2[k], then every element to the left is at least as far as arr2[k-1], and every element to the right is at least as far as arr2[k]. So checking the two bracketing values is sufficient.
Binary search for lower bound: The loop narrows left/right until pos points to the first element >= x. If no such element exists, pos == n (meaning x is larger than all of arr2).
Right-side check: If pos < n, we test abs(x - arr2[pos]) <= d. If it fails, x is invalid immediately.
Left-side check: If still valid and pos > 0, we test abs(x - arr2[pos - 1]) <= d. If that also fails, x is valid.
Counting: Only when neither neighbor triggers the condition does distanceValue increase — this matches the definition exactly.

Complexity Analysis

Time: O(m log m + n log m) where n = arr1.length, m = arr2.length — O(m log m) to sort arr2, and O(log m) binary search per arr1 element.
Space: O(1) extra space (excluding the input; sort in PHP is in-place / O(log m) stack).

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

My Hacktoberfest 2026 Experience

MD ARIFUL HAQUE — Wed, 04 Nov 2026 18:44:01 +0000

My Hacktoberfest 2026 Experience

Hacktoberfest 2026 was an inspiring and productive experience for me. This October, I focused on building practical open-source AI projects, experimenting with locally running open-weight models, and exploring how AI can make everyday development and business workflows easier.

What did you make?

I worked on several open-source AI projects:

Slow and Steady AI: An offline-first AI productivity assistant combining LazyMate AI and SellerMate AI.
LazyMate AI: A local AI assistant designed to help users organize tasks, meeting notes, and daily productivity.
SellerMate AI: An AI-powered assistant for generating Bangla and English e-commerce product descriptions, SEO content, and Facebook marketing captions.
GhostFrame AI Studio: An experimental Laravel-based AI studio integrating local AI, Ollama, project automation, Playwright, and FFmpeg for automated project demonstrations.

What did you try or learn?

I explored Ollama and open-weight AI models to build applications that can run locally without depending entirely on external AI APIs.

I also gained practical experience with Docker Compose, Laravel, automated testing, Playwright, FFmpeg, and integrating AI into real-world development workflows.

One of my biggest takeaways was understanding how open-source AI can give developers more control over their data, infrastructure, model selection, and deployment costs.

What got in your way?

The biggest challenges were environment configuration, Docker networking, model resource requirements, dependency compatibility, and integrating multiple technologies into a reliable workflow.

Debugging Laravel testing issues and connecting locally hosted AI services also required considerable time and experimentation.

However, these challenges helped me improve my troubleshooting and system integration skills.

What would you keep for next year?

I would keep the open-source AI challenges, hands-on project building, community collaboration, and opportunities to experiment with emerging technologies.

I particularly enjoyed the freedom to build practical projects around real-world problems rather than simply following tutorials.

What would you change for next year?

I would love to see more beginner-friendly technical workshops, longer project-building periods, clearer submission guidelines, more opportunities for project collaboration, and additional recognition for projects that demonstrate real-world usability.

Final thoughts

Hacktoberfest 2026 reminded me that open source is more than writing code. It is about sharing knowledge, solving problems together, experimenting with new ideas, and making technology accessible to everyone.

Thank you to the DEV community, organizers, partners, and everyone who contributed to making Hacktoberfest 2026 a meaningful experience.

I'm looking forward to building more useful open-source projects and contributing even more next year!

3505. Minimum Operations to Make Elements Within K Subarrays Equal

MD ARIFUL HAQUE — Wed, 04 Nov 2026 18:20:11 +0000

3505. Minimum Operations to Make Elements Within K Subarrays Equal

Difficulty: Hard

Topics: Principal, Array, Hash Table, Math, Dynamic Programming, Sliding Window, Heap (Priority Queue), Weekly Contest 443

You are given an integer array nums and two integers, x and k. You can perform the following operation any number of times (including zero):

Increase or decrease any element of nums by 1.

Return the minimum number of operations needed to have at least k non-overlapping subarrays¹ of size exactly x in nums, where all elements within each subarray are equal.

Example 1:

Input: nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
Output: 8
Explanation:
- Use 3 operations to add 3 to nums[1] and use 2 operations to subtract 2 from nums[3]. The resulting array is [5, 1, 1, 1, 7, 3, 6, 4, -1].
- Use 1 operation to add 1 to nums[5] and use 2 operations to subtract 2 from nums[6]. The resulting array is [5, 1, 1, 1, 7, 4, 4, 4, -1].
- Now, all elements within each subarray [1, 1, 1] (from indices 1 to 3) and [4, 4, 4] (from indices 5 to 7) are equal. Since 8 total operations were used, 8 is the output.

Example 2:

Input: nums = [9,-2,-2,-2,1,5], x = 2, k = 2
Output: 3
Explanation:
- Use 3 operations to subtract 3 from nums[4]. The resulting array is [9, -2, -2, -2, -2, 5].
- Now, all elements within each subarray [-2, -2] (from indices 1 to 2) and [-2, -2] (from indices 3 to 4) are equal. Since 3 operations were used, 3 is the output. Example 3:
Input: nums = [1,1,1,1,1], x = 2, k = 2
Output: 0

Example 4:

Input: nums = [-5,-5,-5,-5,-5], x = 2, k = 2
Output: 0

Example 5:

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

Example 6:

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

Example 7:

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

Example 8:

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

Example 9:

Input: nums = [-1000000,1000000,-1000000,1000000], x = 2, k = 2
Output: 4000000

Example 10:

Input: nums = [0,0,0,100,100,0,0,0], x = 3, k = 2
Output: 0

Example 11:

Input: nums = [10,-10,10,-10,10,-10], x = 2, k = 3
Output: 60

Example 12:

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

Constraints:

2 <= nums.length <= 10⁵
-10⁶ <= nums[i] <= 10⁶
2 <= x <= nums.length
1 <= k <= 15
2 <= k * x <= nums.length

Hint:

Making every element of an x-sized window equal to its median is optimal.
Precalculate this for each window.

Similar Questions:

Solution:

We solve this problem by first precomputing the minimum cost to make every x-sized window uniform (using the median as target), then applying a prefix DP to select k non-overlapping windows with minimum total cost. Window costs are computed in O(log n) per position using two Fenwick trees (BITs) — one for counts, one for sums — over coordinate-compressed values, enabling efficient sliding-window median and cost queries.

Approach

Coordinate compress all nums values so BIT indices are bounded by m ≤ n.
Two Fenwick trees (bitCount, bitSum) maintain the multiset of values inside the current window of size x.
Initial window fill: insert the first x elements into both BITs.
Sliding window: for each start index 0 … n-x, do:
- Find the lower median ((x+1)/2-th smallest) via BIT kth query.
- Compute sum |aᵢ − median| using prefix count/sum at the median rank.
- Slide: remove nums[start], insert nums[start+x], updating both BITs and the running window sum.
DP for window selection: prev[i] = min cost using chosen-1 windows among first i elements.
- Transition: cur[i] = min(cur[i-1], prev[i-x] + cost[i-x]).
- Iterate chosen = 1…k, return prev[n].

Let's implement this solution in PHP: 3505. Minimum Operations to Make Elements Within K Subarrays Equal

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

/**
 * @param $bitCount
 * @param $bitSum
 * @param $idx
 * @param $deltaCount
 * @param $deltaSum
 * @param $m
 * @return void
 */
function add(&$bitCount, &$bitSum, $idx, $deltaCount, $deltaSum, $m): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $bitCount
 * @param $k
 * @param $m
 * @param $highestPower
 * @return int|mixed
 */
function kth($bitCount, $k, $m, $highestPower): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minOperations([5,-2,1,3,7,3,6,4,-1], 3, 2) . "\n";               // Output: 8
echo minOperations([9,-2,-2,-2,1,5], 2, 2) . "\n";                    // Output: 3
echo minOperations([1,1,1,1,1], 2, 2) . "\n";                         // Output: 0
echo minOperations([-5,-5,-5,-5,-5], 2, 2) . "\n";                    // Output: 0
echo minOperations([1,2,3,4], 2, 2) . "\n";                           // Output: 2
echo minOperations([5,1,3], 3, 1) . "\n";                             // Output: 4
echo minOperations([3,1,2,4,5,6], 2, 3) . "\n";                       // Output: 5
echo minOperations([1,2,3,4,5,6,7,8], 4, 2) . "\n";                   // Output: 8
echo minOperations([-1000000,1000000,-1000000,1000000], 2, 2) . "\n"; // Output: 4000000
echo minOperations([0,0,0,100,100,0,0,0], 3, 2) . "\n";               // Output: 0
echo minOperations([10,-10,10,-10,10,-10], 2, 3) . "\n";              // Output: 60
echo minOperations([1,1,2,2,3,3,4,4], 4, 2) . "\n";                   // Output: 4
?>

Explanation

Why median? For a fixed window, sum |aᵢ − m| is minimized at the median (hint 1). Any even-sized window can use the lower median without loss.
Why BIT? We need the median and the count/sum split around it in O(log n) while sliding. Two BITs give count and sum for the rank query, and prefix sums up to the median let us split the window into left/right halves.
Cost formula:
- cost = median * cntLE − sumLE + (windowSum − sumLE) − median * (x − cntLE)
- First half: elements ≤ median — sum of (median − aᵢ).
- Second half: elements > median — sum of (aᵢ − median).
Non-overlap enforcement in DP: Placing a window ending at i−1 (starting at i−x) consumes exactly those x slots, so prev[i−x] uses positions before the window starts — guaranteeing non-overlap by construction.
"At least k" vs "exactly k": Since each window cost is non-negative, min over exactly k equals min over ≥ k. The constraint k*x ≤ n guarantees feasibility.
Lower median handling for even x: Using the lower median still yields the minimum L1 cost, so medianRank = (x+1)/2 is correct for both odd and even window sizes.

Complexity Analysis

• Time Complexity:

Coordinate compression: O(n log n)
Initial window fill: O(x log n)
Sliding window (n − x + 1 steps, each O(log n)): O(n log n)
DP: O(k · n) ≤ O(15 · 10⁵)
Total: O(n log n + nk) • Space Complexity:
bitCount, bitSum arrays of size m + 1: O(n)
vals, map, nums, prev, cur, cost: O(n)
Total: 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

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

3736. Minimum Moves to Equal Array Elements III

MD ARIFUL HAQUE — Tue, 03 Nov 2026 19:11:59 +0000

3736. Minimum Moves to Equal Array Elements III

Difficulty: Easy

Topics: Mid Level, Array, Math, Biweekly Contest 169

You are given an integer array nums.

In one move, you may increase the value of any single element nums[i] by 1.

Return the minimum total number of moves required so that all elements in nums become equal.

Example 1:

Input: nums = [2,1,3]
Output: 3
Explanation:
- To make all elements equal:
  - Increase nums[0] = 2 by 1 to make it 3.
  - Increase nums[1] = 1 by 1 to make it 2.
  - Increase nums[1] = 2 by 1 to make it 3.
- Now, all elements of nums are equal to 3. The minimum total moves is 3.

Example 2:

Input: nums = [4,4,5]
Output: 2
Explanation:
- To make all elements equal:
  - Increase nums[0] = 4 by 1 to make it 5.
  - Increase nums[1] = 4 by 1 to make it 5.
- Now, all elements of nums are equal to 5. The minimum total moves is 2.

Example 3:

Input: nums = [1]
Output: 0

Example 4:

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

Example 5:

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

Example 6:

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

Example 7:

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

Constraints:

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

Hint:

To make all numbers equal, they must all reach at least the maximum value in the array.

Solution:

We need to find the minimum number of increment operations required to make all elements in nums equal. Since only increments are allowed, every element must be raised to the current maximum value in the array. The answer is the sum of differences between the maximum value and each element.

Approach

Find the maximum value in the array using max($nums).
Initialize a moves counter to 0.
Iterate through each element in nums.
For each element, add max - element to moves.
Return the total moves.

Let's implement this solution in PHP: 3736. Minimum Moves to Equal Array Elements III

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

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

Explanation

Increasing any element can only raise its value, never lower it.
Therefore, the smallest valid common target is the maximum element in the array.
If we chose any larger target, we would perform unnecessary extra moves.
For each number num, the required moves to reach max is exactly max - num.
Summing these differences gives the minimum total moves.

Complexity Analysis

Time Complexity: O(n), where n is the length of nums. We traverse the array once to find the maximum and once to compute the total moves.
Space Complexity: O(1), since only a few scalar 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

462. Minimum Moves to Equal Array Elements II

MD ARIFUL HAQUE — Mon, 02 Nov 2026 17:00:19 +0000

462. Minimum Moves to Equal Array Elements II

Difficulty: Medium

Topics: Principal, Array, Math, Sorting

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

Example 3:

Input: nums = [1]
Output: 0

Example 4:

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

Example 5:

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

Example 6:

Input: nums = [-5,-1,3]
Output: 8

Example 7:

Input: nums = [1,2,10]
Output: 9

Example 8:

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

Example 9:

Input: nums = [-1000000000, 1000000000]
Output: 2000000000

Example 10:

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

Constraints:

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

Hint:

A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Similar Questions:

Solution:

We solve this by converting all elements to the median of the array. The median minimizes the total absolute distance, so the minimum moves equal the sum of absolute differences between each element and the median. Sorting lets us find the median efficiently.

Approach

Sort nums in ascending order.
Choose the median element.
- For odd n, it is the exact middle element.
- For even n, any value between the two middle elements is optimal; using nums[intdiv($n, 2)] works.
Iterate through the sorted array and accumulate abs($num - $median).
Return the total accumulated moves.

Let's implement this solution in PHP: 462. Minimum Moves to Equal Array Elements II

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

// Test cases
echo minMoves2([1,2,3]) . "\n";            // Output: 2
echo minMoves2([1,10,2,9]) . "\n";         // Output: 16
echo minMoves2([1]) . "\n";                // Output: 0
echo minMoves2([1,1,1]) . "\n";            // Output: 0
echo minMoves2([0,0,10,10]) . "\n";        // Output: 20
echo minMoves2([-5,-1,3]) . "\n";          // Output: 8
echo minMoves2([1,2,10]) . "\n";           // Output: 9
?>

Explanation

Making all elements equal to some value x costs:
- sum(abs(nums[i] - x))
This cost is minimized when x is the median.
Sorting places the median at index intdiv(n, 2).
Summing absolute differences from the median gives the minimum number of increment/decrement operations.
The provided PHP implementation correctly follows this logic.

Complexity Analysis

Time Complexity: O(n log n) due to sorting, followed by an O(n) scan.
Space Complexity: O(1) auxiliary space, excluding the internal space used by the sorting implementation.

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

453. Minimum Moves to Equal Array Elements

MD ARIFUL HAQUE — Sun, 01 Nov 2026 18:17:15 +0000

453. Minimum Moves to Equal Array Elements

Difficulty: Medium

Topics: Junior, Array, Math

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

Example 2:

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

Example 3:

Input: nums = [5]
Output: 0

Example 4:

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

Example 5:

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

Example 6:

Input: nums = [5,5,10]
Output: 5

Example 7:

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

Example 8:

Input: nums = [-1000000000, 1000000000]
Output: 2000000000

Constraints:

n == nums.length
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
The answer is guaranteed to fit in a 32-bit integer.

Similar Questions:

Solution:

We can solve this by recognizing that incrementing n - 1 elements is equivalent to decrementing exactly one element. Therefore, the minimum moves needed to make all elements equal is the total amount required to reduce every element to the array minimum.

Approach

Find the minimum value in nums.
For each element, calculate how far it is above the minimum.
Sum all those differences.
Return the sum as the minimum number of moves.

Let's implement this solution in PHP: 453. Minimum Moves to Equal Array Elements

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

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

Explanation:

In one move, incrementing n - 1 elements by 1 is mathematically equivalent to decrementing the remaining one element by 1.
To make all elements equal using only this operation, the final target value must be the current minimum element.
Any element larger than the minimum must be reduced by nums[i] - min(nums) moves.
Summing these differences gives the total minimum moves.
The provided PHP solution correctly implements this logic using min($nums) and a single loop.

Complexity Analysis

Time Complexity: O(n), where n is the length of nums. We scan the array once to find the minimum and once to sum differences.
Space Complexity: O(1), since only a few scalar 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

GhostFrame AI Studio: Turn Any Local Project into a Silent Demo with Ollama, Playwright and FFmpeg

MD ARIFUL HAQUE — Sun, 01 Nov 2026 10:35:41 +0000

What it does

GhostFrame AI Studio is a local-first tool for creating repeatable browser demos of projects you own. It combines an existing Ollama model for demo planning, Playwright for browser automation, FFmpeg for silent MP4 conversion, and Python/Pillow for PNG and GIF assets. A small PHP dashboard controls the workflow, while Docker Compose keeps the worker and dashboard reproducible.

Why open innovation matters

Open-weight models and local tools give developers control over where prompts and demo data are processed. The project can use an Ollama model running on a developer's own machine, while Playwright, FFmpeg and Pillow provide inspectable building blocks. Developers can change the model, scenario selectors and media pipeline rather than depending on a hosted black box.

How to run

Install Docker Desktop and start Ollama.
Pull a model such as qwen3.5:4b in Ollama.
Copy .env.example to .env.
Run docker compose up -d --build.
Open http://localhost:8088.
Start a local demo app, configure TARGET_URL and edit recorder/scenario.json with dummy data.
Run the recording and review output/.

Generated artifacts

Silent H.264 MP4
Browser screenshots
SVG and PNG title card
Animated GIF preview
JSON run manifest

Current limitations

GhostFrame is not a universal recorder. Each application may need a custom scenario with valid selectors. Authentication, CAPTCHA, payment and destructive workflows are intentionally out of scope. The first Docker build needs internet access. Validate the generated assets and do not record real customer information.

3665. Twisted Mirror Path Count

MD ARIFUL HAQUE — Sat, 31 Oct 2026 17:19:06 +0000

3665. Twisted Mirror Path Count

Difficulty: Medium

Topics: Staff, Array, Dynamic Programming, Matrix, Biweekly Contest 164

Given an m x n binary grid grid where:

grid[i][j] == 0 represents an empty cell, and
grid[i][j] == 1 represents a mirror.

A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). It can move only right or down. If the robot attempts to move into a mirror cell, it is reflected before entering that cell:

If it tries to move right into a mirror, it is turned down and moved into the cell directly below the mirror.
If it tries to move down into a mirror, it is turned right and moved into the cell directly to the right of the mirror.

If this reflection would cause the robot to move outside the grid boundaries, the path is considered invalid and should not be counted.

Return the number of unique valid paths from (0, 0) to (m - 1, n - 1).

Since the answer may be very large, return it modulo 10⁹ + 7.

Note: If a reflection moves the robot into a mirror cell, the robot is immediately reflected again based on the direction it used to enter that mirror: if it entered while moving right, it will be turned down; if it entered while moving down, it will be turned right. This process will continue until either the last cell is reached, the robot moves out of bounds or the robot moves to a non-mirror cell.

Example 1:

Input: grid = [[0,1,0],[0,0,1],[1,0,0]]
Output: 5
Explanation:

Number	Full Path
1	(0, 0) → (0, 1) [M] → (1, 1) → (1, 2) [M] → (2, 2)
2	(0, 0) → (0, 1) [M] → (1, 1) → (2, 1) → (2, 2)
3	(0, 0) → (1, 0) → (1, 1) → (1, 2) [M] → (2, 2)
4	(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2)
5	(0, 0) → (1, 0) → (2, 0) [M] → (2, 1) → (2, 2)

[M] indicates the robot attempted to enter a mirror cell and instead reflected.

Example 2:

Input: grid = [[0,0],[0,0]]
Output: 2
Explanation:

Number	Full Path
1	(0, 0) → (0, 1) → (1, 1)
2	(0, 0) → (1, 0) → (1, 1)

Example 3:

Input: grid = [[0,1,1],[1,1,0]]
Output: 1
Explanation:

Number	Full Path
1	(0, 0) → (0, 1) [M] → (1, 1) [M] → (1, 2)

(0, 0) → (1, 0) [M] → (1, 1) [M] → (2, 1) goes out of bounds, so it is invalid.

Example 3:

Input: grid = [[0,1,1],[1,1,0]]
Output: 1

Example 4:

Input: grid = [[0,0],[0,0]]
Output: 2

Example 5:

Input: grid = [[0,0,0],[0,0,0]]
Output: 3

Example 6:

Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 6

Example 7:

Input: grid = [[0,1],[0,0]]
Output: 2

Example 8:

Input: grid = [[0,0],[1,0]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 500
grid[i][j] is either 0 or 1.
grid[0][0] == grid[m - 1][n - 1] == 0

Hint:

Precompute, for each cell and each move (right/down), where you actually land if there’s a mirror next—store these "jump" targets in a go[i][j][0/1] table.
Let dp[i][j] = number of ways to reach (i,j); set dp[0][0] = 1, then scan cells in row‑major order and for each dp[i][j] > 0 add dp[i][j] into dp[x][y] for both precomputed moves.
Always take additions modulo 10⁹+7, and skip any jump target that falls outside the grid.

Solution:

We precompute, for every mirror cell, where the robot finally lands when entering that mirror from the right/down direction. Then we scan the grid in row-major order and propagate path counts from each reachable empty cell using the precomputed jump targets. All additions are taken modulo 10⁹ + 7.

Approach

Flatten the m x n grid into an array of size m * n for faster indexing.
Precompute two tables:
- rightEnter[idx]: final landing cell if the robot enters mirror idx while moving right.
- downEnter[idx]: final landing cell if the robot enters mirror idx while moving down.
Process mirrors from bottom-right to top-left because each mirror’s landing depends only on the cell below it or to its right.
Use -1 to represent an invalid landing that goes outside the grid.
Run DP in row-major order:
- dp[0] = 1.
- For each reachable empty cell, try moving right and down.
- If the next cell is empty, land there directly.
- If the next cell is a mirror, use the corresponding precomputed landing table.
- Skip invalid -1 targets.
Return dp[m*n - 1] % MOD.

Let's implement this solution in PHP: 3665. Twisted Mirror Path Count

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

// Test cases
echo uniquePaths([[0,1,0],[0,0,1],[1,0,0]]) . "\n";     // Output: 5
echo uniquePaths([[0,0],[0,0]]) . "\n";                 // Output: 2
echo uniquePaths([[0,1,1],[1,1,0]]) . "\n";             // Output: 1
echo uniquePaths([[0,0],[0,0]]) . "\n";                 // Output: 2
echo uniquePaths([[0,0,0],[0,0,0]]) . "\n";             // Output: 3
echo uniquePaths([[0,0,0],[0,0,0],[0,0,0]]) . "\n";     // Output: 6
echo uniquePaths([[0,1],[0,0]]) . "\n";                 // Output: 2
echo uniquePaths([[0,0],[1,0]]) . "\n";                 // Output: 2 (corrected from table's 1)
?>

Explanation

A mirror never appears as a normal DP state because the robot is reflected before entering it; mirror cells are only used during jump precomputation.
For a mirror at (i, j):
- Entering from the left while moving right sends the robot down to (i+1, j).
- If (i+1, j) is also a mirror, the robot immediately reflects again using downEnter[(i+1, j)].
- Entering from above while moving down sends the robot right to (i, j+1).
- If (i, j+1) is also a mirror, the robot immediately reflects again using rightEnter[(i, j+1)].
DP transitions:
- Move right from (i, j):
- If (i, j+1) is empty, target is (i, j+1).
- If (i, j+1) is a mirror, target is rightEnter[(i, j+1)].
- Move down from (i, j):
- If (i+1, j) is empty, target is (i+1, j).
- If (i+1, j) is a mirror, target is downEnter[(i+1, j)].
Row-major order is valid because every move or reflection chain ultimately moves to a later row or later column, never to an earlier cell.
Modulo addition is safe because both dp[target] and ways are less than MOD, so one subtraction is enough after addition.

Complexity Analysis

Time Complexity: O(m * n)
- Precomputation visits each cell once.
- DP visits each cell once and performs constant work per direction.
Space Complexity: O(m * n)
- dp array of size m * n.
- rightEnter and downEnter arrays each of size m * 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

3970. Shortest Path With At Most K Consecutive Identical Characters

MD ARIFUL HAQUE — Fri, 30 Oct 2026 17:03:39 +0000

3970. Shortest Path With At Most K Consecutive Identical Characters

Difficulty: Medium

Topics: Staff, String, Graph Theory, Heap (Priority Queue), Shortest Path, Weekly Contest 507

You are given an integer n representing the number of nodes in a directed weighted graph, numbered from 0 to n - 1. This is represented by a 2D integer array edges, where edges[i] = [uᵢ, vᵢ, wᵢ] represents a directed edge from node uᵢ to node vᵢ with weight wᵢ.

You are also given a string labels of length n, where labels[i] is the character assigned to node i, and an integer k.

Return the minimum total edge weight of a path from node 0 to node n - 1 such that the concatenation of the labels of the nodes along the path contains at most k consecutive identical characters. If no valid path exists, return -1.

Example 1:

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 1
Output: 3
Explanation:
- The optimal valid path from node 0 to node 2 is as follows:
  - Use edges[2] = [0, 2, 3] to reach node 2 with a weight wᵢ = 3.
- The corresponding concatenation of labels is "ab", which satisfies at most k = 1 consecutive identical characters. Thus, the answer is 3.

Example 2:

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 2
Output: 2
Explanation:
- The optimal valid path from node 0 to node 2 is as follows:
  - Use edges[0] = [0, 1, 1] to reach node 1 with weight wᵢ = 1.
  - Use edges[1] = [1, 2, 1] to reach node 2 with weight wᵢ = 1.
- The corresponding concatenation of labels is "aab", which satisfies at most k = 2 consecutive identical characters. Thus, the answer is 2.

Example 3:

Input: n = 3, edges = [[0,1,1],[1,2,1]], labels = "aaa", k = 2
Output: -1
Explanation: There is no valid path from node 0 to node 2 that satisfies at most k = 2 consecutive identical characters. Thus, the answer is -1.
Example 4:
Input: n = 1, edges = [], labels = "a", k = 1
Output: 0

Example 5:

Input: n = 2, edges = [[0,1,5]], labels = "ab", k = 1
Output: 5

Example 6:

Input: n = 2, edges = [[0,1,5]], labels = "aa", k = 1
Output: -1

Example 7:

Input: n = 2, edges = [[0,1,5]], labels = "aa", k = 2
Output: 5

Example 8:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,10]], labels = "aabb", k = 2
Output: 3

Example 9:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,10]], labels = "aaab", k = 2
Output: 10

Example 10:

Input: n = 3, edges = [[0,1,1]], labels = "abc", k = 1
Output: -1

Example 11:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1]], labels = "aaaaa", k = 5
Output: 4

Example 12:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1]], labels = "aaaaa", k = 4
Output: -1

Example 13:

Input: n = 3, edges = [[0,1,2],[1,2,2],[0,2,5]], labels = "aba", k = 1
Output: 4

Example 14:

Input: n = 6, edges = [[0,1,1],[1,2,1],[2,5,1],[0,3,1],[3,4,1],[4,5,1]], labels = "aaabbb", k = 3
Output: 3

Example 15:

Input: n = 6, edges = [[0,1,1],[1,2,1],[2,5,1],[0,3,1],[3,4,1],[4,5,1]], labels = "aaaaaa", k = 3
Output: -1

Example 16:

Input: n = 3, edges = [[0,1,100],[1,2,1],[0,2,50]], labels = "abc", k = 50
Output: 50

Example 17:

Input: n = 2, edges = [[0,1,10000]], labels = "aa", k = 50
Output: 10000

Constraints:

1 <= n == labels.length <= 5 * 10⁴
0 <= edges.length <= 5 * 10⁴
edges[i] == [uᵢ, vᵢ, wᵢ]
0 <= uᵢ, vᵢ <= n - 1
uᵢ != vᵢ
1 <= wᵢ <= 10⁴
labels consists of lowercase English letters
1 <= k <= 50

Hint:

The validity of a path depends not only on the current node, but also on how many consecutive times the current node’s label has appeared at the end of the path.
Use Dijkstra on states (node, count), where count is the current consecutive run length of labels[node].
When moving from node u to node v, the next count becomes count + 1 if labels[u] == labels[v], otherwise it becomes 1. Ignore transitions where the next count exceeds k.
The answer is the minimum distance among all states ending at node n - 1.

Solution:

We solve this problem by modeling it as a shortest path on an expanded state graph and applying Dijkstra's algorithm. Since a node alone is not enough to determine validity (we also need to know how many identical characters are currently at the end of the path), we expand each node into k states (node, consecutiveCount) where consecutiveCount ∈ [1, k] represents the current run-length of the label of node. We encode the state as a single integer node * k + (count - 1) to keep storage compact, then run Dijkstra starting from (0, 1) with distance 0. When relaxing an edge u → v, the new run-length becomes count + 1 if labels[u] == labels[v] (invalid if it exceeds k), otherwise it resets to 1. As soon as we pop a state whose node is n - 1 from the min-heap, its distance is the optimal answer.

Approach

State expansion: Instead of tracking only the current node, track (node, runLength) where runLength is the number of consecutive trailing characters equal to labels[node].
State encoding: state = node * k + (runLength - 1), giving n * k ≤ 5·10⁴ · 50 = 2.5·10⁶ states.
Dijkstra initialization: Distance array of size n * k set to INF; the start state (0, 1) has distance 0. Push (state=0, dist=0) into the min-heap.
Relaxation rule: For an edge u → v with weight w:
- If labels[v] == labels[u], nextRun = run + 1; skip if nextRun > k.
- Otherwise nextRun = 1.
- Candidate nextDist = d + w; relax if smaller than dist[nextState].
Early termination: Because Dijkstra pops states in non-decreasing distance order, the first time we pop a state where node == n - 1, that distance is optimal — return it immediately.
Custom binary min-heap: Implemented with two SplFixedArrays (heapState, heapDist) sized k · |edges| + 2 for performance and memory efficiency in PHP.
Stale entry handling: Skip popped entries whose recorded distance no longer matches dist[state] (lazy deletion).
Failure case: If the heap empties before reaching node n - 1, return -1.

Let's implement this solution in PHP: 3970. Shortest Path With At Most K Consecutive Identical Characters

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param String $labels
 * @param Integer $k
 * @return Integer
 */
function shortestPath(int $n, array $edges, string $labels, int $k): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo shortestPath(3, [[0,1,1],[1,2,1],[0,2,3]], "aab", 1) . "\n";                                // Output: 3
echo shortestPath(3, [[0,1,1],[1,2,1],[0,2,3]], "aab", 2) . "\n";                                // Output: 2
echo shortestPath(3, [[0,1,1],[1,2,1]], "aaa", 2) . "\n";                                        // Output: -1
echo shortestPath(1, [], "a", 1) . "\n";                                                         // Output: 0
echo shortestPath(2, [[0,1,5]], "ab", 1) . "\n";                                                 // Output: 5
echo shortestPath(2, [[0,1,5]], "aa", 1) . "\n";                                                 // Output: -1
echo shortestPath(2, [[0,1,5]], "aa", 2) . "\n";                                                 // Output: 5
echo shortestPath(4, [[0,1,1],[1,2,1],[2,3,1],[0,3,10]], "aabb", 2) . "\n";                      // Output: 3
echo shortestPath(4, [[0,1,1],[1,2,1],[2,3,1],[0,3,10]], "aaab", 2) . "\n";                      // Output: 10
echo shortestPath(3, [[0,1,1]], "abc", 1) . "\n";                                                // Output: -1
echo shortestPath(5, [[0,1,1],[1,2,1],[2,3,1],[3,4,1]], "aaaaa", 5) . "\n";                      // Output: 4
echo shortestPath(5, [[0,1,1],[1,2,1],[2,3,1],[3,4,1]], "aaaaa", 4) . "\n";                      // Output: -1
echo shortestPath(3, [[0,1,2],[1,2,2],[0,2,5]], "aba", 1) . "\n";                                // Output: 4
echo shortestPath(6, [[0,1,1],[1,2,1],[2,5,1],[0,3,1],[3,4,1],[4,5,1]], "aaabbb", 3) . "\n";     // Output: 3
echo shortestPath(6, [[0,1,1],[1,2,1],[2,5,1],[0,3,1],[3,4,1],[4,5,1]], "aaaaaa", 3) . "\n";     // Output: -1
echo shortestPath(3, [[0,1,100],[1,2,1],[0,2,50]], "abc", 50) . "\n";                            // Output: 50
echo shortestPath(2, [[0,1,10000]], "aa", 50) . "\n";                                            // Output: 10000
?>

Explanation

Why state matters: The same node can be reached with different trailing run-lengths, and future validity depends on the run-length. Collapsing these into one distance would be incorrect, so we keep a distance per (node, run) pair.
Why Dijkstra works: All edge weights are positive (1 ≤ wᵢ), so the greedy "pop smallest, finalize" property holds for the expanded state graph.
Run-length transition correctness:
- If the next label is the same as the previous node's label, the run continues; exceeding k prunes the transition (this is how Example 3 returns -1 for "aaa" with k = 2).
- Otherwise, the run resets to 1 (only counting the new node's label).
Starting run-length is 1, not 0: The path includes node 0's own label, so a single-node path has a run of 1. This makes the edge case n = 1 return 0 correctly (start state is already n - 1).
Example walkthrough (Example 2): Start (0, 'a', run=1) at dist 0 → relax 0→1 (labels a,a, run=2, dist=1) → relax 1→2 (labels a,b, run=1, dist=2). Pop (2, 1), which is n - 1, return 2.
Example walkthrough (Example 3): Start (0, 'a', run=1) → 0→1 (labels a,a, run=2, dist=1) → 1→2 requires run=3 > k=2, pruned. Heap empties → return -1.

Complexity Analysis

Let N = n, E = |edges|, and K = k.
Number of states: S = N · K.
Number of transitions: Each edge can be relaxed once per state reachable at u, so at most K · E relaxations.
Time Complexity: O((N·K + E·K) · log(N·K)) = O(K · (N + E) · log(N·K)).
- With constraints: ~ 50 · (5·10⁴ + 5·10⁴) · log(2.5·10⁶) ≈ 5·10⁶ · 21 ≈ 10⁸ operations in the worst case, well within limits with the custom heap.
Space Complexity:
- dist array: O(N·K).
- Heap: O(K·E) worst-case entries → O(K·E).
- Adjacency list: O(N + E).
- Total: O(N·K + K·E).

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

3841. Palindromic Path Queries in a Tree

MD ARIFUL HAQUE — Thu, 29 Oct 2026 18:12:58 +0000

3841. Palindromic Path Queries in a Tree

Difficulty: Hard

Topics: Principal, Array, String, Divide and Conquer, Bit Manipulation, Tree, Depth-First Search, Binary Indexed Tree, Segment Tree, Biweekly Contest 176

You are given an undirected tree with n nodes labeled 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [uᵢ, vᵢ] indicates an undirected edge between nodes uᵢ and vᵢ.

You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i.

You are also given a string array queries, where each queries[i] is either:

"update uᵢ c": Change the character at node uᵢ to c. Formally, update s[uᵢ] = c.
"query uᵢ vᵢ": Determine whether the string formed by the characters on the unique path from uᵢ to vᵢ (inclusive) can be rearranged into a palindrome¹.

Return a boolean array answer, where answer[j] is true if the jᵗʰ query of type "query uᵢ vᵢ" can be rearranged into a palindrome, and false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
Output: [true,false]
Explanation:
- "query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true.
- "update 1 b": Update node 1 to 'b', now s = "abc".
- "query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
- Thus, answer = [true, false].

Example 2:

Input: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
Output: [false,false,true]
Explanation:
- "query 1 2: Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false.
- "update 0 b": Update node 0 to 'b', now s = "bbca".
- "query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
- "update 3 a": Update node 3 to 'a', s = "bbca".
- "query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.
- Thus, answer = [false, false, true]. Example 3:
Input: n = 1, edges = [], s = "a", queries = ["query 0 0"]
Output: [true]

Example 4:

Input: n = 2, edges = [[0,1]], s = "aa", queries = ["query 0 1"]
Output: [true]

Example 5:

Input: n = 2, edges = [[0,1]], s = "ab", queries = ["query 0 1"]
Output: [false]

Example 6:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]], s = "abcba", queries = ["query 0 4"]
Output: [true]

Example 7:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]], s = "abcde", queries = ["query 0 4"]
Output: [false]

Example 8:

Input: n = 4, edges = [[0,1],[1,2],[2,3]], s = "aaaa", queries = ["update 1 a","query 0 3"]
Output: [true]

Example 9:

Input: n = 4, edges = [[0,1],[1,2],[2,3]], s = "aaaa", queries = ["update 1 b","update 2 b","query 0 3"]
Output: [true]

Example 10:

Input: n = 4, edges = [[0,1],[1,2],[2,3]], s = "aaaa", queries = ["update 1 b","query 0 3"]
Output: [true]

Example 11:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[0,4]], s = "abcde", queries = ["query 1 2","query 3 4","update 0 a","query 1 2"]
Output: [false,false,false]

Example 12:

Input: n = 6, edges = [[0,1],[1,2],[2,3],[3,4],[4,5]], s = "aabbcc", queries = ["query 0 5","update 3 a","query 0 5"]
Output: [true,false]

Example 13:

Input: n = 3, edges = [[0,1],[1,2]], s = "aba", queries = ["query 0 0","query 1 1","query 0 2"]
Output: [true,true,true]

Example 14:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], s = "abcdefg", queries = ["update 3 a","update 5 a","update 1 a","query 0 6"]
Output: [false]

Example 15:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[2,5]], s = "xyzzyx", queries = ["query 3 4","query 3 5","update 0 x","query 3 5"]
Output: [true,false,true]

Constraints:

1 <= n == s.length <= 5 * 10⁴
edges.length == n - 1
edges[i] = [uᵢ, vᵢ]
0 <= uᵢ, vᵢ <= n - 1
s consists of lowercase English letters.
The input is generated such that edges represents a valid tree.
1 <= queries.length <= 5 * 10⁴
- queries[i] = "update uᵢ c" or
- queries[i] = "query uᵢ vᵢ"
- 0 <= uᵢ, vᵢ <= n - 1
- c is a lowercase English letter.

Hint:

Use heavy light decomposition to break each path query into O(log n) segments.
Represent characters as a 26-bit mask and maintain segment data with XOR. A path can form a palindrome if the resulting mask has at most one bit set.

Solution:

We solve the dynamic palindromic-path query problem on a tree using an Euler-tour representation combined with a Fenwick tree for range-XOR/point-query updates, binary lifting for LCA, and 26-bit integer masks to represent character parities. Each character is encoded as a single bit; a string is rearrangeable into a palindrome iff at most one bit in the XOR mask of its characters is set. By observing that the path u → v mask equals prefix(u) XOR prefix(v) XOR mask[LCA(u,v)], and that the prefix mask at a node changes exactly when a node in the subtree of an updated node is affected, we reduce each update to a subtree-range XOR and each query to two point queries plus an LCA lookup.

Approach

Character encoding as bitmask: Map each letter c to 1 << (ord(c) - 97). The parity of character counts along any path is the XOR of these masks.
Palindrome criterion: A multiset of characters can be rearranged into a palindrome iff at most one character has odd frequency, i.e., the mask has popcount(mask) <= 1, equivalently (mask & (mask - 1)) == 0.
Root-to-node prefix: Define pref[x] = XOR of masks on path root → x. Then for any u, v: pathMask(u,v) = pref[u] XOR pref[v] XOR mask[LCA(u,v)].
Euler tour: Flatten the tree so each node's subtree is a contiguous interval [tin[u], tout[u]]. This lets us model "all descendants of u" as a range.
Fenwick tree with range-XOR / point-query: When node u's mask changes by delta, pref[x] changes iff x is in u's subtree. So apply delta as a range XOR over [tin[u], tout[u]]; a point query pref[x] is then the accumulated XOR at tin[x].
Binary lifting LCA: Precompute up[k][v] for O(log n) ancestor jumps, enabling O(log n) LCA queries.
Offline processing: Parse each query string; if update, compute delta = oldMask XOR newMask (skip if 0) and apply a subtree range XOR; if query, compute pathMask and append the palindrome test result.

Let's implement this solution in PHP: 3841. Palindromic Path Queries in a Tree

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param String $s
 * @param String[] $queries
 * @return Boolean[]
 */
function palindromePath(int $n, array $edges, string $s, array $queries): array
{
    // Build adjacency list.
    $adj = array_fill(0, $n, []);
    foreach ($edges as $e) {
        $u = $e[0];
        $v = $e[1];
        $adj[$u][] = $v;
        $adj[$v][] = $u;
    }

    // Euler tour: tin[u]..tout[u] is the subtree interval of u.
    $parent = array_fill(0, $n, 0);
    $depth = array_fill(0, $n, 0);
    $tin = array_fill(0, $n, 0);
    $tout = array_fill(0, $n, 0);

    $timer = 0;
    $stack = [[0, 0, 0]]; // [node, parent, state], state 0 = enter, 1 = exit
    $parent[0] = 0;

    while (!empty($stack)) {
        $item = array_pop($stack);
        $u = $item[0];
        $p = $item[1];
        $state = $item[2];

        if ($state === 0) {
            $parent[$u] = $p;
            $tin[$u] = $timer++;

            $stack[] = [$u, $p, 1];

            foreach ($adj[$u] as $v) {
                if ($v === $p) continue;
                $depth[$v] = $depth[$u] + 1;
                $parent[$v] = $u;
                $stack[] = [$v, $u, 0];
            }
        } else {
            $tout[$u] = $timer - 1;
        }
    }

    // Binary lifting table for LCA.
    $LOG = 1;
    while ((1 << $LOG) <= $n) {
        $LOG++;
    }

    $up = array_fill(0, $LOG, array_fill(0, $n, 0));
    for ($i = 0; $i < $n; $i++) {
        $up[0][$i] = $parent[$i];
    }

    for ($k = 1; $k < $LOG; $k++) {
        for ($i = 0; $i < $n; $i++) {
            $up[$k][$i] = $up[$k - 1][$up[$k - 1][$i]];
        }
    }

    // Character masks.
    $mask = array_fill(0, $n, 0);
    for ($i = 0; $i < $n; $i++) {
        $mask[$i] = 1 << (ord($s[$i]) - 97);
    }

    /*
     * Fenwick tree for range XOR update and point query.
     *
     * If a node u changes by delta, every root-to-x prefix XOR changes
     * exactly when x is in the subtree of u. So we XOR delta over
     * [tin[u], tout[u]].
     */
    $N = $n + 1;
    $bit = array_fill(0, $N + 1, 0);

    $add = function($i, $val) use (&$bit, $N) {
        while ($i <= $N) {
            $bit[$i] ^= $val;
            $i += $i & -$i;
        }
    };

    $rangeXor = function($l, $r, $val) use ($add) {
        if ($val === 0) return;
        $add($l + 1, $val);
        $add($r + 2, $val);
    };

    $pointQuery = function($idx0) use (&$bit) {
        $i = $idx0 + 1;
        $res = 0;

        while ($i > 0) {
            $res ^= $bit[$i];
            $i -= $i & -$i;
        }

        return $res;
    };

    // Initialize prefix XORs by applying each node's initial mask
    // to its whole subtree.
    for ($i = 0; $i < $n; $i++) {
        $rangeXor($tin[$i], $tout[$i], $mask[$i]);
    }

    // LCA query.
    $lca = function($a, $b) use (&$up, $depth, $LOG) {
        if ($depth[$a] < $depth[$b]) {
            $tmp = $a;
            $a = $b;
            $b = $tmp;
        }

        $diff = $depth[$a] - $depth[$b];

        for ($k = 0; $k < $LOG; $k++) {
            if ($diff & (1 << $k)) {
                $a = $up[$k][$a];
            }
        }

        if ($a === $b) {
            return $a;
        }

        for ($k = $LOG - 1; $k >= 0; $k--) {
            if ($up[$k][$a] !== $up[$k][$b]) {
                $a = $up[$k][$a];
                $b = $up[$k][$b];
            }
        }

        return $up[0][$a];
    };

    $answer = [];

    foreach ($queries as $query) {
        $parts = explode(' ', $query);

        if ($parts[0] === 'update') {
            $u = (int)$parts[1];
            $newMask = 1 << (ord($parts[2]) - 97);

            $delta = $mask[$u] ^ $newMask;

            if ($delta !== 0) {
                $rangeXor($tin[$u], $tout[$u], $delta);
                $mask[$u] = $newMask;
            }
        } else {
            $u = (int)$parts[1];
            $v = (int)$parts[2];

            $w = $lca($u, $v);

            // XOR parity mask on path u -> v.
            $pathMask = $pointQuery($tin[$u])
                ^ $pointQuery($tin[$v])
                ^ $mask[$w];

            // Palindrome possible iff at most one bit is set.
            $answer[] = (($pathMask & ($pathMask - 1)) === 0);
        }
    }

    return $answer;
}

// Test cases
echo palindromePath(3, [[0,1],[1,2]], "aac", ["query 0 2","update 1 b","query 0 2"]) . "\n";                                                // Output: [true,false]
echo palindromePath(4, [[0,1],[0,2],[0,3]], "abca", ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]) . "\n";                // Output: [false,false,true]
echo palindromePath(1, [], "a", ["query 0 0"]) . "\n";                                                                                      // Output: [true]
echo palindromePath(2, [[0,1]], "aa", ["query 0 1"]) . "\n";                                                                                // Output: [true]
echo palindromePath(2, [[0,1]], "ab", ["query 0 1"]) . "\n";                                                                                // Output: [false]
echo palindromePath(5, [[0,1],[1,2],[2,3],[3,4]], "abcba", ["query 0 4"]) . "\n";                                                           // Output: [true]
echo palindromePath(5, [[0,1],[1,2],[2,3],[3,4]], "abcde", ["query 0 4"]) . "\n";                                                           // Output: [false]
echo palindromePath(4, [[0,1],[1,2],[2,3]], "aaaa", ["update 1 a","query 0 3"]) . "\n";                                                     // Output: [true]
echo palindromePath(4, [[0,1],[1,2],[2,3]], "aaaa", ["update 1 b","update 2 b","query 0 3"]) . "\n";                                        // Output: [true]
echo palindromePath(4, [[0,1],[1,2],[2,3]], "aaaa", ["update 1 b","query 0 3"]) . "\n";                                                     // Output: [true]
echo palindromePath(5, [[0,1],[0,2],[0,3],[0,4]], "abcde", ["query 1 2","query 3 4","update 0 a","query 1 2"]) . "\n";                      // Output: [false,false,false]
echo palindromePath(6, [[0,1],[1,2],[2,3],[3,4],[4,5]], "aabbcc", ["query 0 5","update 3 a","query 0 5"]) . "\n";                           // Output: [true,false]
echo palindromePath(3, [[0,1],[1,2]], "aba", ["query 0 0","query 1 1","query 0 2"]) . "\n";                                                 // Output: [true,true,true]
echo palindromePath(7, [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], "abcdefg", ["update 3 a","update 5 a","update 1 a","query 0 6"]) . "\n";      // Output: [false]
echo palindromePath(6, [[0,1],[0,2],[1,3],[1,4],[2,5]], "xyzzyx", ["query 3 4","query 3 5","update 0 x","query 3 5"]) . "\n";               // Output: [true,false,true]
?>

Explanation:

Tree preprocessing:
- Build an adjacency list from edges.
- Perform an iterative DFS producing tin[u], tout[u] (subtree interval), depth[u], and parent[u]. Euler order guarantees tin[u] < tin[v] < tout[v] < tout[u] when u is an ancestor of v.
LCA preprocessing:
- Fill up[0][v] = parent[v] and iteratively up[k][v] = up[k-1][up[k-1][v]] for k = 1..LOG-1.
- LCA procedure: lift the deeper node, then lift both together to the highest differing ancestors, returning the parent of that point.
Fenwick initialization:
- Start with an all-zero bit array; for every node u, perform rangeXor(tin[u], tout[u], mask[u]). After this, the point query at tin[x] equals pref[x] — the XOR of masks from root to x.
Update handling (update u c):
- Compute newMask = 1 << (c - 'a'), delta = mask[u] XOR newMask.
- If delta != 0, do rangeXor(tin[u], tout[u], delta) and set mask[u] = newMask.
- Range XOR is done with two Fenwick point updates (+1 and +2 on the exclusive end) since Fenwick supports prefix XOR for point queries.
Query handling (query u v):
- Find w = LCA(u, v).
- pathMask = pointQuery(tin[u]) XOR pointQuery(tin[v]) XOR mask[w].
- Push ((pathMask & (pathMask - 1)) == 0) into the answer.
Why it works:
- pointQuery(tin[u]) XOR pointQuery(tin[v]) cancels the common root-to-LCA prefix, leaving the XOR of the two LCA → u and LCA → v branches excluding the LCA. XOR-ing mask[w] re-inserts the LCA exactly once, giving the inclusive path mask.

Complexity Analysis

Let n = |s| (number of nodes) and q = |queries|.
Time complexity:
- Tree building + Euler tour: O(n)
- Binary lifting table: O(n log n)
- Fenwick initialization (n range updates): O(n log n)
- Each update: O(log n)
- Each query: O(log n) (LCA) + O(log n) (two point queries)
- Total: O((n + q) · log n)
Space complexity:
- Adjacency list: O(n)
- Euler arrays (tin, tout, parent, depth): O(n)
- Binary lifting table: O(n log n)
- Fenwick tree: O(n)
- Overall: O(n log 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

Palindrome: A palindrome is a string that reads the same forward and backward. ↩

3882. Minimum XOR Path in a Grid

MD ARIFUL HAQUE — Wed, 28 Oct 2026 17:46:03 +0000

3882. Minimum XOR Path in a Grid

Difficulty: Medium

Topics: Staff, Array, Dynamic Programming, Bit Manipulation, Matrix, Biweekly Contest 179

You are given a 2D integer array grid of size m * n.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).

At each step, you may move either right or down.

The cost of a path is defined as the bitwise XOR of all the values in the cells along that path, including the start and end cells.

Return the minimum possible XOR value among all valid paths from (0, 0) to (m - 1, n - 1).

Example 1:

Input: grid = [[1,2],[3,4]]
Output: 6
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 1 XOR 2 XOR 4 = 7
  - (0, 0) → (1, 0) → (1, 1) with XOR: 1 XOR 3 XOR 4 = 6
- The minimum XOR value among all valid paths is 6.

Example 2:

Input: grid = [[6,7],[5,8]]
Output: 9
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 6 XOR 7 XOR 8 = 9
  - (0, 0) → (1, 0) → (1, 1) with XOR: 6 XOR 5 XOR 8 = 11
- The minimum XOR value among all valid paths is 9.

Example 3:

Input: grid = [[2,7,5]]
Output: 0
Explanation:
- There is only one valid path:
  - (0, 0) → (0, 1) → (0, 2) with XOR: 2 XOR 7 XOR 5 = 0
- The minimum XOR value among all valid paths is 0.

Example 4:

Input: grid = [[0]]
Output: 0
Explanation:
- There is only one valid path:
  - (0, 0) with XOR: 0
- The minimum XOR value among all valid paths is 0.

Example 5:

Input: grid = [[5]]
Output: 5
Explanation:
- There is only one valid path:
  - (0, 0) with XOR: 5
- The minimum XOR value among all valid paths is 5.

Example 6:

Input: grid = [[1,1],[1,1]]
Output: 1
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 1 XOR 1 XOR 1 = 1
  - (0, 0) → (1, 0) → (1, 1) with XOR: 1 XOR 1 XOR 1 = 1
- The minimum XOR value among all valid paths is 1.

Example 7:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 1
Explanation:
- There are six valid paths:
  - (0,0)→(0,1)→(0,2)→(1,2)→(2,2) with XOR: 1 XOR 2 XOR 3 XOR 6 XOR 9 = 15
  - (0,0)→(0,1)→(1,1)→(1,2)→(2,2) with XOR: 1 XOR 2 XOR 5 XOR 6 XOR 9 = 9
  - (0,0)→(0,1)→(1,1)→(2,1)→(2,2) with XOR: 1 XOR 2 XOR 5 XOR 8 XOR 9 = 7
  - (0,0)→(1,0)→(1,1)→(1,2)→(2,2) with XOR: 1 XOR 4 XOR 5 XOR 6 XOR 9 = 15
  - (0,0)→(1,0)→(1,1)→(2,1)→(2,2) with XOR: 1 XOR 4 XOR 5 XOR 8 XOR 9 = 1
  - (0,0)→(1,0)→(2,0)→(2,1)→(2,2) with XOR: 1 XOR 4 XOR 7 XOR 8 XOR 9 = 3
- The minimum XOR value among all valid paths is 1.

Example 8:

Input: grid = [[1023,1023],[1023,1023]]
Output: 1023
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 1023 XOR 1023 XOR 1023 = 1023
  - (0, 0) → (1, 0) → (1, 1) with XOR: 1023 XOR 1023 XOR 1023 = 1023
- The minimum XOR value among all valid paths is 1023.

Example 9:

Input: grid = [[0,1],[1,0]]
Output: 1
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 0 XOR 1 XOR 0 = 1
  - (0, 0) → (1, 0) → (1, 1) with XOR: 0 XOR 1 XOR 0 = 1
- The minimum XOR value among all valid paths is 1.

Example 10:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation:
- There are two valid paths:
  - (0, 0) → (0, 1) → (1, 1) with XOR: 1 XOR 0 XOR 1 = 0
  - (0, 0) → (1, 0) → (1, 1) with XOR: 1 XOR 0 XOR 1 = 0
- The minimum XOR value among all valid paths is 0.

Example 11:

Input: grid = [[2,3,1,4]]
Output: 4
Explanation:
- There is only one valid path:
  - (0, 0) → (0, 1) → (0, 2) → (0, 3) with XOR: 2 XOR 3 XOR 1 XOR 4 = 4
- The minimum XOR value among all valid paths is 4.

Example 12:

Input: grid = [[1],[2],[3]]
Output: 0
Explanation:
- There is only one valid path:
  - (0, 0) → (1, 0) → (2, 0) with XOR: 1 XOR 2 XOR 3 = 0
- The minimum XOR value among all valid paths is 0.

Constraints:

1 <= m == grid.length <= 1000
1 <= n == grid[i].length <= 1000
m * n <= 1000
0 <= grid[i][j] <= 1023

Hint:

Use dynamic programming with state dp[i][j][x], where x is a possible XOR value.
dp[i][j][x] indicates whether it is possible to reach cell (i, j) with XOR equal to x.
Transition from the top left cell by updating x ^ grid[i][j], and track all reachable XOR values to find the minimum at the end cell.

Solution:

We implement a dynamic programming solution that tracks all possible XOR values reachable at each cell in the grid. Since the values are bounded by 1023 (10 bits), we can represent the set of reachable XOR values as a bitset of 1024 bits (32 integer words), which makes the union and XOR-shift operations extremely fast. We process the grid row by row using a rolling array of size n, combining reachable XOR sets from the top and left neighbors, then XOR-ing each reachable value with the current cell's value. At the end, we scan the final bitset in increasing order to find the minimum reachable XOR value.

Approach

Represent XOR states as bitsets: Each cell stores a 1024-bit bitset (32 × 32-bit ints). Bit x set means XOR value x is reachable at that cell.
Rolling row DP: Use dp[j] to store the bitset of the cell directly above the current cell (i-1, j), and left to store the bitset of the cell to the left (i, j-1).
Merge top and left: For each cell (except start), OR together the bitsets from top and left into a pre set.
XOR transition: For every set bit x in pre, set bit (x ^ grid[i][j]) in the resulting bitset res.
Base case: At (0, 0), only the value grid[0][0] is reachable.
Answer extraction: After processing the last cell, scan bits 0..1023 in order and return the first one that is set — that is the minimum reachable XOR.

Let's implement this solution in PHP: 3882. Minimum XOR Path in a Grid

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

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

Explanation:

Why bitsets? XOR values are limited to [0, 1023] (since grid[i][j] ≤ 1023, XOR of any number of such values stays under 1024). A boolean array of size 1024 would work, but bitsets reduce memory by ~32× and allow fast OR/iteration.
State definition: dp[j] (before overwrite) = set of XOR values reachable at cell (i-1, j). After processing cell (i, j), dp[j] = set of XOR values reachable at (i, j).
Why left variable? It holds the just-computed result for the previous column in the current row — i.e., reachable XOR values at (i, j-1).
Merge step (pre): A path can arrive at (i, j) from above (i-1, j) or from the left (i, j-1). So the union of their reachable sets gives all pre-XOR values.
Transition step (res): Every pre-value x combined with grid[i][j] via XOR produces the new value x ^ grid[i][j].
Bounds safety: The grid can be 1000 × 1000 cells, but total cells m*n ≤ 1000, so O(m·n·1024/32) work is cheap.

Complexity Analysis

Time Complexity: O(m · n · (1024/32 + 1024))
- For each cell, we OR two 32-int arrays: O(1024/32) = O(32).
- Then we iterate over all 1024 possible XOR values to perform transitions.
- Total: O(m · n · 1024) ≈ O(10^6) operations for m*n = 1000.
Space Complexity: O(n · 1024/32) = O(n · 32) for the rolling DP row, plus O(32) for the left and pre/res buffers. Under constraints (n ≤ 1000), that is about 128 KB.

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