DEV Community: MD ARIFUL HAQUE

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

3963. Create Grid With Exactly One Path

MD ARIFUL HAQUE — Tue, 27 Oct 2026 18:09:13 +0000

3963. Create Grid With Exactly One Path

Difficulty: Easy

Topics: Mid Level, Biweekly Contest 185

You are given two integers m and n, representing the number of rows and columns of a grid.

Construct any m x n grid consisting only of the characters '.' and '#', where:

'.' represents a free cell.
'#' represents an obstacle cell.

A valid path is a sequence of free cells that:

Starts at the top-left cell (0, 0).
Ends at the bottom-right cell (m - 1, n - 1).
Moves only:
- Right, from (i, j) to (i, j + 1), or
- Down, from (i, j) to (i + 1, j).

Return any grid such that there is exactly one valid path from the top-left cell to the bottom-right cell.

Example 1:

Input: m = 2, n = 3
Output: ["..#","#.."]
- Explanation:
- The only valid path is: (0,0) → (0,1) → (1,1) → (1,2)

Example 2:

Input: m = 3, n = 3
Output: ["..#","#..","##."]
- Explanation:
- The only valid path is: (0,0) → (0,1) → (1,1) → (1,2) → (2,2)

Example 3:

Input: m = 1, n = 4
Output: ["...."]
- Explanation: The only valid path is: (0,0) → (0,1) → (0,2) → (0,3)

Example 4:

Input: m = 4, n = 1
Output: [".",".",".","."]
- Explanation: Single column; the only valid path is: (0,0) → (1,0) → (2,0) → (3,0)

Example 5:

Input: m = 1, n = 1
Output: ["."]
- Explanation: Minimal grid; the only valid path is: (0,0)

Example 6:

Input: m = 2, n = 2
Output: [".#",".."]
- Explanation: Smallest 2D case; the only valid path is: (0,0) → (1,0) → (1,1)

Example 7:

Input: m = 25, n = 25
Output: Top row all '.', rightmost column all '.', every other cell '#'
- Explanation: The only valid path is: go right 24 times along the top row, then down 24 times along the rightmost column — (0,0) → (0,1) → … → (0,24) → (1,24) → … → (24,24). Demonstrates the maximum constraint.

Example 8:

Input: m = 5, n = 2
Output: [".#",".#",".#",".#",".."]
- Explanation: Narrow grid (2 columns); the top-right cell (0,1) is blocked, so the only valid path is: (0,0) → (1,0) → (2,0) → (3,0) → (4,0) → (4,1)

Constraints:

1 <= m, n <= 25

Hint:

It is enough to leave one simple route made of free cells and block every other cell.
There are many routes to choose from. What is the simplest one you can think of?
One possible route: Go right while possible, then go down till you reach the destination.

Similar Questions:

3988. Create Grid With Exactly K Paths I

Solution:

We construct an m × n grid where exactly one valid path exists by keeping only the top row and the rightmost column as free cells (.) and blocking every other cell (#). This forces a single path: traverse right along the top row to the top-right corner, then down the rightmost column to the bottom-right corner. Since every other route is walled off, exactly one valid path remains.

Approach

Choose the simplest route: Go right as far as possible (top row), then down to the destination (rightmost column) — exactly as suggested by Hint #3.
Free cells on this route only: Cells (0, j) for all j and (i, n-1) for all i are ..
Block everything else: Any cell with i > 0 and j < n-1 becomes #.
Handle degenerate cases automatically: For m = 1 or n = 1, the "top row" or "rightmost column" covers the entire grid, so the row/column is naturally all . — still exactly one path.
No overlap issue: The top row and rightmost column intersect at (0, n-1), which is . either way, so no conflict.

Let's implement this solution in PHP: 3963. Create Grid With Exactly One Path

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

// Test cases
echo json_encode(createGrid(2, 3)) . "\n"; // Output: ["..#","#.."]
echo json_encode(createGrid(3, 3)) . "\n"; // Output: ["..#","#..","##."]
echo json_encode(createGrid(1, 4)) . "\n"; // Output: ["...."]
echo json_encode(createGrid(4, 1)) . "\n"; // Output: [".",".",".","."]
echo json_encode(createGrid(1, 1)) . "\n"; // Output: ["."]
echo json_encode(createGrid(2, 2)) . "\n"; // Output: [".#",".."]
echo json_encode(createGrid(5, 2)) . "\n"; // Output: [".#",".#",".#",".#",".."]
// For (25, 25), the output is a long array; use json_encode to print it.
echo json_encode(createGrid(25, 25)) . "\n"; // Output: [".........................", ".#.......................#", ...] (full grid)
?>

Explanation:

Path construction: The unique path is (0,0) → (0,1) → … → (0,n-1) → (1,n-1) → … → (m-1,n-1).
Why no other path exists:
- To leave the top row downward, you must be at column n-1 (only free cells below the top row are in the rightmost column).
- Any step down before reaching column n-1 lands on a # cell.
- Once on the rightmost column, you cannot move left (only right/down moves allowed), so you must go straight down.
Uniqueness: There is exactly one sequence of right/down moves that stays on free cells — so exactly one valid path.
Reachability: Both start (0,0) and end (m-1,n-1) lie on this route; (0,0) is in the top row and (m-1,n-1) is in the rightmost column, so both are ..
Edge cases: m = 1 → single row all . (one path). n = 1 → single column all . (one path).

Complexity Analysis

Time Complexity: O(m × n) — we visit each cell once to decide its character.
Space Complexity: O(m × n) — storing the output grid of m strings, each of length n (excluding output space, the auxiliary space is O(1)).

Contact Links

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

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

LinkedIn
GitHub

3619. Count Islands With Total Value Divisible by K

MD ARIFUL HAQUE — Mon, 26 Oct 2026 17:59:25 +0000

3619. Count Islands With Total Value Divisible by K

Difficulty: Medium

Topics: Senior, Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix, Biweekly Contest 161

You are given an m x n matrix grid and a positive integer k. An island is a group of positive integers (representing land) that are 4-directionally connected (horizontally or vertically).

The total value of an island is the sum of the values of all cells in the island.

Return the number of islands with a total value divisible by k.

Example 1:

Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5
Output: 2
Explanation: The grid contains four islands. The islands highlighted in blue have a total value that is divisible by 5, while the islands highlighted in red do not.

Example 2:

Input: grid = [[3,0,3,0],[0,3,0,3],[3,0,3,0]], k = 3
Output: 6
Explanation: The grid contains six islands, each with a total value that is divisible by 3.

Example 3:

Input: grid = [[1]], k = 1
Output: 1
Explanation: There is one island with total value 1, which is divisible by 1.

Example 4:

Input: grid = [[1]], k = 2
Output: 0
Explanation: There is one island with total value 1, which is not divisible by 2.

Example 5:

Input: grid = [[0]], k = 5
Output: 0
Explanation: The grid contains only water, so there are no islands.

Example 6:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], k = 9
Output: 1
Explanation: The grid contains one island with total value 9, which is divisible by 9.

Example 7:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], k = 5
Output: 0
Explanation: The grid contains one island with total value 9, which is not divisible by 5.

Example 8:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]], k = 1
Output: 4
Explanation: The grid contains four islands, each with total value 1. Since every value is divisible by 1, all four islands count.

Example 9:

Input: grid = [[1000000]], k = 1000000
Output: 1
Explanation: There is one island with total value 1000000, which is divisible by 1000000.

Example 10:

Input: grid = [[2,2,0,0],[2,0,0,0],[0,0,4,4],[0,0,4,0]], k = 2
Output: 2
Explanation: The grid contains two islands with total values 6 and 12. Both are divisible by 2.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁶
1 <= k <= 10⁶

Hint:

Use a BFS/DFS to find connected components.

Similar Questions:

200. Number of Islands

Solution:

We implemented an iterative Depth-First Search (DFS) using an explicit stack to traverse the grid and discover all 4-directionally connected islands of positive integers. For each island we accumulate its total value, then check whether that sum is divisible by k. We mutate the input grid in place (setting visited cells to 0) to avoid a separate visited array, keeping memory usage minimal. The final answer is the count of islands whose total value passes the divisibility check.

Approach

Iterate over every cell in the m × n grid using nested loops.
Skip any cell whose value is <= 0 (water or already visited).
When a positive cell is found, treat it as the seed of a new island:
- Initialize the island's running sum with the seed's value.
- Mark the seed as visited by setting it to 0.
- Push the seed onto a stack for DFS traversal.
While the stack is non-empty:
- Pop the current cell.
- Inspect all four orthogonal neighbors (up, down, left, right).
- For each in-bounds neighbor with a positive value:
- Add its value to the island sum.
- Mark it visited by setting it to 0.
- Push it onto the stack.
After the stack drains, the island is fully explored:
- If sum % k == 0, increment the answer counter.
Return the final count.

Let's implement this solution in PHP: 3619. Count Islands With Total Value Divisible by K

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

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

Explanation:

In-place marking — Setting visited cells to 0 reuses the existing grid as the visited set, saving O(m·n) auxiliary space for a boolean matrix.
Iterative DFS with explicit stack — Avoids PHP recursion depth limits that can be hit on large connected islands (up to 10⁵ cells).
Positive-only check — grid[r][c] <= 0 covers both water cells (value 0) and already-visited land cells (now 0), so it doubles as the "should we explore?" and "already seen?" check.
Ordering of operations — We add the value to sum before zeroing it out, so we never lose the contribution of a cell.
Divisibility test — Because k can be up to 10⁶ and values up to 10⁶ across 10⁵ cells, integer overflow could occur in fixed-width languages, but PHP integers are 64-bit on modern platforms, so sum % k is safe.
Four-direction traversal — The $directions array encodes (down, up, right, left); only orthogonal neighbors count as connected, matching the problem's 4-directional definition.

Complexity Analysis

Time Complexity: O(m · n) — each cell is pushed onto the stack and popped at most once, and each pop examines exactly 4 neighbors.
Space Complexity: O(m · n) worst case — the explicit stack may hold up to O(m · n) cells for a single large connected island (e.g., a fully land-filled grid). No additional visited array is allocated.

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

1254. Number of Closed Islands

MD ARIFUL HAQUE — Sun, 25 Oct 2026 19:36:38 +0000

1254. Number of Closed Islands

Difficulty: Medium

Topics: Staff, Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix, Weekly Contest 162

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Example 6:

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

Example 7:

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

Example 8:

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

Constraints:

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

Hint:

Exclude connected group of 0s on the corners because they are not closed island.
Return number of connected component of 0s on the grid.

Solution:

We solve the problem by first eliminating every 0-land component that touches the grid boundary, since those cannot be closed islands. After that, every remaining connected component of 0s is fully surrounded by water (1s), so we count those components with another flood fill. The implementation uses iterative DFS with an explicit stack to avoid recursion depth issues.

Approach

Treat 0 as land and 1 as water.
Any land connected to the boundary is not closed, because it is not fully surrounded by water.
Flood-fill all boundary-connected 0s and mark them as water/visited.
Traverse the remaining grid.
Each unvisited 0 starts a new closed island.
Flood-fill that component and increment the closed island count.
Return the count.

Let's implement this solution in PHP: 1254. Number of Closed Islands

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

/**
 * @param array $grid
 * @param int $row
 * @param int $col
 * @return void
 */
function floodFill(array &$grid, int $row, int $col): void {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo closedIsland([[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]) .  "\n";                                 // Output: 2
echo closedIsland([[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]) .  "\n";                                                                                       // Output: 1
echo closedIsland([[1,1,1,1,1,1,1], [1,0,0,0,0,0,1], [1,0,1,1,1,0,1], [1,0,1,0,1,0,1], [1,0,1,1,1,0,1], [1,0,0,0,0,0,1], [1,1,1,1,1,1,1]]) .  "\n";     // Output: 2
echo closedIsland([[0]]) .  "\n";                                                                                                                       // Output: 0
echo closedIsland([[1]]) .  "\n";                                                                                                                       // Output: 0
echo closedIsland([[1,1,1],[1,0,1],[1,1,1]]) .  "\n";                                                                                                   // Output: 1
echo closedIsland([[1,1,1],[1,1,1],[1,1,1]]) .  "\n";                                                                                                   // Output: 0
echo closedIsland([[0,0,0],[0,0,0],[0,0,0]]) .  "\n";                                                                                                   // Output: 0
?>

Explanation:

Let m = count(grid) and n = count(grid[0]).
Check the first row and last row:
- If a cell is 0, flood-fill its entire connected component and mark it visited.
Check the first column and last column:
- If a cell is 0, flood-fill its entire connected component and mark it visited.
After removing boundary-connected land, scan all cells:
- If grid[i][j] === 0, it is a closed island.
- Increment the answer.
- Flood-fill this island so it is not counted again.
The flood fill uses a stack and processes 4-directional neighbors:
- Up, down, left, right.
- Marks each visited land cell as 1.

Complexity Analysis

Time Complexity: O(m * n)
- Each cell is visited at most a constant number of times during boundary flood fills and counting.
Space Complexity: O(m * n) in the worst case
- The iterative stack may contain O(m * n) cells.
- The input grid is modified in place.

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

Two Small Agents, One Local Model: LazyMate + SellerMate for Slow and Steady 🦥

MD ARIFUL HAQUE — Sat, 24 Oct 2026 21:39:56 +0000

Two Small Agents, One Local Model: LazyMate + SellerMate for Slow and Steady 🦥

This is a submission for the Hacktoberfest Open-Source AI Challenge Week 3: Slow and Steady

I like tools that save time without asking me to hand over every note, draft, or business detail to a remote service. For the Slow and Steady challenge, I combined two practical assistants into one local-first project: LazyMate AI for everyday productivity and SellerMate AI for Bangla e-commerce listings.

The goal isn't to make an agent that does everything. It's to make a few tedious tasks easier, keep the human in control, and let the user decide where their data goes.

What I Built

LazyMate AI helps with:

Summarizing long notes into concise takeaways
Turning rough notes into actionable checklists
Rewriting drafts for clarity
Previewing file-organization moves before applying them

SellerMate AI turns seller-provided product facts into:

Product titles and short/full descriptions
SEO meta descriptions and keywords
Social captions
Bangla, English, or bilingual copy

SellerMate is deliberately a drafting assistant, not a source of truth. It should never invent a warranty, certification, specification, or performance claim. The seller must verify every detail before publishing.

Demo

Add a screenshot, short recording, or DevRelay session link here before publishing.

Code

Repository: add your public GitHub URL before publishing

How I Built It

Both apps use a shared local Ollama runtime and a configurable open-weight model (default: qwen2.5:3b). After the Docker images, dependencies, and model weights are downloaded, inference can run without a hosted AI API.

Architecture

Browser
  ├── LazyMate UI/API (:8080) ──┐
  └── SellerMate UI (:8081)     ├── Ollama (:11434, internal)
         └── SellerMate API     ┘

Docker Compose runs both applications and a single Ollama service. Host ports bind to loopback rather than all network interfaces. Model weights are stored in a Docker volume, not bundled in the source ZIP.

Run it

Requirements: Docker Desktop or Docker Engine with Compose v2, internet for the first download, and enough disk/RAM for the model.

cp .env.example .env
docker compose up -d --build
docker compose exec ollama ollama pull qwen2.5:3b

Then visit:

LazyMate: http://localhost:8080
SellerMate: http://localhost:8081

On Windows PowerShell, use Copy-Item .env.example .env instead of cp. After the images and model are cached, disconnect from the internet and restart the services to test offline operation. See the README for troubleshooting and reproducible test commands.

Safety is part of the product

Automation should reduce busywork, not create a new cleanup job. LazyMate's file organizer uses a preview-first approach and confines intended operations to a dedicated workspace. SellerMate generates drafts that need human review. The services bind to localhost by default; don't expose them publicly without adding authentication, TLS, and a threat-model review.

Local inference is not a magic privacy shield: malware, compromised hosts, unsafe plugins, and careless file permissions can still expose data. Likewise, a language model can produce incorrect output. Review the result before acting on it.

Testing and limitations

The repository includes unit/API tests, smoke-test guidance, and CI workflows. Packaging checks are not a substitute for a full deployment test: run the Docker stack on your own machine, verify both interfaces, test file operations with copied samples, and confirm inference while offline. A real model response and browser-level integration should be captured before claiming those checks passed.

The model weights are not included in the ZIP because they are large and have separate terms. The first setup needs internet access. Offline operation begins only after the images and model are present locally.

What I'd improve next

Add an explicit local document index with transparent file selection
Add import/export formats for SellerMate listings
Build an evaluation set for Bangla fluency and factual consistency
Add a visible "facts supplied vs. claims generated" review panel
Publish real demo screenshots and CI results alongside the source

Why Does Open Innovation Matter?

That matters in three ways:

Data stays closer to its owner. Notes, drafts, and product details can remain on the user's computer rather than being sent to a third-party inference endpoint.
The model is replaceable. A user can choose a different compatible model after checking its capabilities and license.
Costs are more predictable. Local inference avoids per-request hosted API charges, although hardware, electricity, storage, and setup time still have costs.

Open-weight doesn't mean every component is automatically open source, perfectly private, or free of restrictions. The model and each dependency have their own terms. Check the exact model card and notices before redistributing weights or using a model commercially.

My Agent Session

Optional — embed a DevRelay session using the agent_session tag here if available.

The Lazy Payoff

This is a fresh build, so real-world time savings haven't been measured yet. The intended payoff: LazyMate takes the first pass at notes and file clutter, and SellerMate takes the first pass at product copy — replacing the blank-page tax on routine tasks. I'll update this section with actual usage data once the demo has been run against real notes and listings.

Prize Categories

List the partner categories you're entering here, or remove this section.

Build slowly. Keep it local. Review before you ship. 🦥

Two Small Agents, One Local Model: LazyMate + SellerMate for Slow and Steady

MD ARIFUL HAQUE — Sat, 24 Oct 2026 21:36:25 +0000

Two Small Agents, One Local Model: LazyMate + SellerMate for Slow and Steady 🦥

The goal isn't to make an agent that does everything. It's to make a few tedious tasks easier, keep the human in control, and let the user decide where their data goes.

What it does

LazyMate AI helps with:

Summarizing long notes into concise takeaways
Turning rough notes into actionable checklists
Rewriting drafts for clarity
Previewing file-organization moves before applying them

SellerMate AI turns seller-provided product facts into:

Product titles and short/full descriptions
SEO meta descriptions and keywords
Social captions
Bangla, English, or bilingual copy

Why open models matter here

That matters in three ways:

Data stays closer to its owner. Notes, drafts, and product details can remain on the user's computer rather than being sent to a third-party inference endpoint.
The model is replaceable. A user can choose a different compatible model after checking its capabilities and license.
Costs are more predictable. Local inference avoids per-request hosted API charges, although hardware, electricity, storage, and setup time still have costs.

Architecture

Browser
  ├── LazyMate UI/API (:8080) ──┐
  └── SellerMate UI (:8081)     ├── Ollama (:11434, internal)
         └── SellerMate API     ┘

Run it

Requirements: Docker Desktop or Docker Engine with Compose v2, internet for the first download, and enough disk/RAM for the model.

cp .env.example .env
docker compose up -d --build
docker compose exec ollama ollama pull qwen2.5:3b

Then visit:

LazyMate: http://localhost:8080
SellerMate: http://localhost:8081

Safety is part of the product

Testing and limitations

What I'd improve next

Add an explicit local document index with transparent file selection
Add import/export formats for SellerMate listings
Build an evaluation set for Bangla fluency and factual consistency
Add a visible “facts supplied vs. claims generated” review panel
Publish real demo screenshots and CI results alongside the source

Why this fits Slow and Steady

A little automation can remove repeated effort without removing choice. LazyMate takes the first pass at notes and file clutter. SellerMate takes the first pass at product copy. Open-weight inference makes both adaptable and usable without a per-request cloud dependency, while preview and review steps keep the person in charge.

Repository: add your public GitHub URL before publishing

Demo: add a screenshot, short recording, or DevRelay session if available

Build slowly. Keep it local. Review before you ship. 🦥

2409. Count Days Spent Together

MD ARIFUL HAQUE — Sat, 24 Oct 2026 18:59:04 +0000

2409. Count Days Spent Together

Difficulty: Easy

Topics: Mid Level, Math, String, Biweekly Contest 87

Alice and Bob are traveling to Rome for separate business meetings.

You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.

Return the total number of days that Alice and Bob are in Rome together.

You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].

Example 1:

Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
Output: 3
Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.

Example 2:

Input: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
Output: 0
Explanation: There is no day when Alice and Bob are in Rome together, so we return 0.

Example 3:

Input: arriveAlice = "01-01", leaveAlice = "12-31", arriveBob = "01-01", leaveBob = "12-31"
Output: 365
Explanation: Both Alice and Bob are in Rome for the entire non-leap year (days 1–365), so they are together on all 365 days.

Example 4:

Input: arriveAlice = "01-15", leaveAlice = "01-20", arriveBob = "01-15", leaveBob = "01-20"
Output: 6
Explanation: Both stays are identical, covering days 15–20 inclusive (January 15th through 20th). The overlap length is 20 − 15 + 1 = 6.

Example 5:

Input: arriveAlice = "01-01", leaveAlice = "01-10", arriveBob = "01-10", leaveBob = "01-20"
Output: 1
Explanation: Alice is in Rome on days 1–10 and Bob on days 10–20. They overlap only on day 10 (January 10th), which is inclusive for both, so the answer is 1.

Example 6:

Input: arriveAlice = "02-01", leaveAlice = "03-01", arriveBob = "02-15", leaveBob = "02-20"
Output: 6
Explanation: Alice is in Rome on days 32–60 (February 1 – March 1) and Bob on days 46–51 (February 15–20). Bob's entire stay lies inside Alice's, so the overlap is days 46–51 = February 15th through 20th, i.e. 6 days.

Example 7:

Input: arriveAlice = "01-01", leaveAlice = "01-05", arriveBob = "01-06", leaveBob = "01-10"
Output: 0
Explanation: Alice leaves on day 5 and Bob arrives on day 6. Although the stays are adjacent, they share no common day, so the answer is 0.

Example 8:

Input: arriveAlice = "12-01", leaveAlice = "12-31", arriveBob = "12-31", leaveBob = "12-31"
Output: 1
Explanation: Alice is in Rome from day 335 to day 365, and Bob is there only on day 365 (December 31st). They overlap on that single final day of the year, so the answer is 1.

Example 9:

Input: arriveAlice = "06-15", leaveAlice = "06-20", arriveBob = "03-01", leaveBob = "06-15"
Output: 1
Explanation: Alice arrives on day 166 (June 15) and leaves on day 171 (June 20); Bob's stay ends on day 166 (June 15). Their intervals touch only at day 166, so they are together for exactly 1 day.

Example 10:

Input: arriveAlice = "04-01", leaveAlice = "04-30", arriveBob = "05-01", leaveBob = "05-31"
Output: 0
Explanation: Alice's stay covers April (days 91–120) and Bob's covers May (days 121–151). The intervals are consecutive but non-overlapping, so no day is shared and the answer is 0.

Constraints:

All dates are provided in the format "MM-DD".
Alice and Bob's arrival dates are earlier than or equal to their leaving dates.
The given dates are valid dates of a non-leap year.

Hint:

For a given day, determine if Alice or Bob or both are in Rome.
Brute force all 365 days for both Alice and Bob.

Similar Questions:

Solution:

We convert each date string ("MM-DD") into a day-of-year number (1–365) using a prefix-sum of the standard non-leap-year month lengths. Then, treating each person's stay as a closed interval [start, end], we compute the intersection of Alice's and Bob's intervals. The overlap length is min(endA, endB) - max(startA, startB) + 1, clamped at 0 when the intervals don't intersect.

Approach

Define $daysInMonth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] (non-leap year).
Write a helper $toDayOfYear($date) that:
- Parses MM and DD from the 5-char string.
- Sums all full months before MM and adds DD.
Convert all four input dates to absolute day-of-year integers:
- aliceStart, aliceEnd, bobStart, bobEnd.
Compute the overlap window:
- overlapStart = max(aliceStart, bobStart)
- overlapEnd = min(aliceEnd, bobEnd)
Return max(0, overlapEnd - overlapStart + 1) — the +1 accounts for inclusive endpoints.

Let's implement this solution in PHP: 2409. Count Days Spent Together

<?php
/**
 * @param String $arriveAlice
 * @param String $leaveAlice
 * @param String $arriveBob
 * @param String $leaveBob
 * @return Integer
 */
function countDaysTogether(string $arriveAlice, string $leaveAlice, string $arriveBob, string $leaveBob): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countDaysTogether("08-15", "08-18", "08-16", "08-19") . "\n"; // Output: 3
echo countDaysTogether("10-01", "10-31", "11-01", "12-31") . "\n"; // Output: 0
echo countDaysTogether("01-01", "12-31", "01-01", "12-31") . "\n"; // Output: 365
echo countDaysTogether("01-15", "01-20", "01-15", "01-20") . "\n"; // Output: 6
echo countDaysTogether("01-01", "01-10", "01-10", "01-20") . "\n"; // Output: 1
echo countDaysTogether("02-01", "03-01", "02-15", "02-20") . "\n"; // Output: 6
echo countDaysTogether("01-01", "01-05", "01-06", "01-10") . "\n"; // Output: 0
echo countDaysTogether("12-01", "12-31", "12-31", "12-31") . "\n"; // Output: 1
echo countDaysTogether("06-15", "06-20", "03-01", "06-15") . "\n"; // Output: 1
echo countDaysTogether("04-01", "04-30", "05-01", "05-31") . "\n"; // Output: 0
?>

Explanation:

Date normalization: Comparing "MM-DD" strings lexicographically is unreliable across boundaries (e.g., "12-31" vs "01-01"), so we flatten each date into a single integer day-of-year. Since the year is fixed and non-leap, no leap-day adjustment is needed.
Interval intersection: Two inclusive intervals [a₁, a₂] and [b₁, b₂] overlap on [max(a₁,b₁), min(a₂,b₂)].
Length of overlap: Inclusive count is end - start + 1 (e.g., Aug 16 → Aug 18 = 18 − 16 + 1 = 3 days).
No-overlap case: If the intervals are disjoint, min(endA,endB) < max(startA,startB), so the difference is negative; max(0, …) correctly returns 0.

Complexity Analysis

Time Complexity: O(1) — constant work: one loop over at most 12 months per date, four dates total.
Space Complexity: O(1) — fixed 12-element array plus a few scalar 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