Forem: MD ARIFUL HAQUE

1674. Minimum Moves to Make Array Complementary

MD ARIFUL HAQUE — Wed, 13 May 2026 18:22:18 +0000

1674. Minimum Moves to Make Array Complementary

Difficulty: Medium

Topics: Senior Staff, Array, Hash Table, Prefix Sum, Weekly Contest 217

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation:
- In 1 move, you can change nums to 1,2,2,3.
- nums[0] + nums[3] = 1 + 3 = 4.
- nums[1] + nums[2] = 2 + 2 = 4.
- nums[2] + nums[1] = 2 + 2 = 4.
- nums[3] + nums[0] = 3 + 1 = 4.
- Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

Constraints:

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= limit <= 10⁵
n is even.

Hint:

Given a target sum x, each pair of nums[i] and nums[n-1-i] would either need 0, 1, or 2 modifications.
Can you find the optimal target sum x value such that the sum of modifications is minimized?
Create a difference array to efficiently sum all the modifications.

Solution:

The solution uses a difference array (prefix sum) technique to efficiently compute, for each possible target sum S, the number of moves needed to make all complementary pairs sum to S.

It iterates over each pair (a, b) and updates a range of possible target sums with incremental move counts using constant-time range updates. Finally, it scans through all possible sums to find the minimum moves.

Approach:

Observation for one pair: For a given target sum S, a pair (a, b) needs:
- 0 moves if S == a + b
- 1 move if min(a, b) + 1 ≤ S ≤ max(a, b) + limit and S ≠ a + b
- 2 moves otherwise
Key trick: Instead of checking all S for each pair (which is O(limit²)), we use a difference array to mark where the move count changes.
Range update logic (for a pair (a, b) with lo = min(a, b), hi = max(a, b)):
- From 2 to lo + 1: 2 moves
- From lo + 1 to a + b - 1: 1 move (decrease by 1 from previous)
- At a + b: 0 moves (decrease by 1 again)
- From a + b + 1 to hi + limit: 1 move (increase by 1)
- From hi + limit + 1 to 2*limit: 2 moves (increase by 1 again)
Prefix sum over the diff array gives the move count for each S. Track the minimum value.

Let's implement this solution in PHP: 1674. Minimum Moves to Make Array Complementary

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

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

Explanation:

The diff array is initialized to size 2*limit + 2 to cover all possible sums from 2 to 2*limit.
For each pair (a, b):
- Start with base cost 2 for all sums (diff[2] += 2).
- Decrease by 1 at lo + 1 (1 move zone starts).
- Decrease by 1 at a + b (0 moves at exact sum).
- Increase by 1 at a + b + 1 (1 move zone resumes).
- Increase by 1 at hi + limit + 1 (2 moves zone restarts).
After processing all pairs, compute prefix sums of diff to get total moves for each S.
Find the minimum across all valid sums.

Complexity

Time Complexity: O(n + limit)
- Each pair updates a constant number of positions in diff.
- Prefix sum scan over O(limit).
Space Complexity: O(limit), Difference array of size 2*limit + 2.

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

1655. Minimum Initial Energy to Finish Tasks

MD ARIFUL HAQUE — Tue, 12 May 2026 17:29:23 +0000

1655. Minimum Initial Energy to Finish Tasks

Difficulty: Hard

Topics: Senior Staff, Array, Greedy, Sorting, Weekly Contest 216

You are given an array tasks where tasks[i] = [actuali, minimumi]:

actuali is the actual amount of energy you spend to finish the iᵗʰ task.
minimumi is the minimum amount of energy you require to begin the iᵗʰ task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
- Starting with 8 energy, we finish the tasks in the following order:
  - 3rd task. Now energy = 8 - 4 = 4.
  - 2nd task. Now energy = 4 - 2 = 2.
  - 1st task. Now energy = 2 - 1 = 1.
- Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Example 2:

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation:
- Starting with 32 energy, we finish the tasks in the following order:
  - 1st task. Now energy = 32 - 1 = 31.
  - 2nd task. Now energy = 31 - 2 = 29.
  - 3rd task. Now energy = 29 - 10 = 19.
  - 4th task. Now energy = 19 - 10 = 9.
  - 5th task. Now energy = 9 - 8 = 1.

Example 3:

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27
Explanation:
- Starting with 27 energy, we finish the tasks in the following order:
  - 5th task. Now energy = 27 - 5 = 22.
  - 2nd task. Now energy = 22 - 2 = 20.
  - 3rd task. Now energy = 20 - 3 = 17.
  - 1st task. Now energy = 17 - 1 = 16.
  - 4th task. Now energy = 16 - 4 = 12.
  - 6th task. Now energy = 12 - 6 = 6.

Constraints:

1 <= tasks.length <= 10⁵
1 <= actualᵢ <= minimumᵢ <= 10⁴

Hint:

We can easily figure that the f(x) : does x solve this array is monotonic so binary Search is doable
Figure a sorting pattern

Solution:

The solution determines the minimum initial energy required to complete all tasks in any order, where each task has an actual energy cost and a minimum required energy to start.

It uses greedy sorting by (minimum - actual) in descending order to ensure tasks that are "harder to start" are done earlier, then calculates the needed starting energy.

Approach:

Sorting Strategy Sort tasks by (minimum - actual) in descending order. This prioritizes tasks where the gap between required start energy and actual energy is largest.
Simulation & Energy Tracking Iterate through tasks in sorted order, keeping track of:
- sumActual = total actual energy spent so far
- initial = maximum starting energy needed to reach the current point
Formula Updating For each task (actual, minimum), the energy needed before this task is at least minimum + sumActual. Update initial to the maximum such value across all tasks, then add actual to sumActual.
Result After processing all tasks, initial contains the minimum starting energy.

Let's implement this solution in PHP: 1655. Minimum Initial Energy to Finish Tasks

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

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

Explanation:

Sorting by minimum - actual descending ensures tasks with high minimum requirement relative to actual cost are attempted first. This is optimal because starting with less energy fails for tasks that require a high threshold, so earlier energy "buffer" is more valuable for them.
The greedy choice is proven optimal by exchange arguments (typical for scheduling with constraints).
The formula initial = max(initial, minimum + sumActual) ensures that before doing the current task, we have enough energy to meet its minimum requirement, considering all previous tasks have been done (cost added to sumActual).
No binary search needed because sorting + linear scan directly gives the minimal starting energy.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) extra space (ignoring input storage).
Sorting Comparison: Each comparison is O(1).
Iteration: O(n) after sorting.

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

2553. Separate the Digits in an Array

MD ARIFUL HAQUE — Mon, 11 May 2026 18:01:37 +0000

2553. Separate the Digits in an Array

Difficulty: Easy

Topics: Mid Level, Array, Simulation, Biweekly Contest 97

Given an array of positive integers nums, return an array answer that consists of the digits of each integer in nums after separating them in the same order they appear in nums.

To separate the digits of an integer is to get all the digits it has in the same order.

For example, for the integer 10921, the separation of its digits is [1,0,9,2,1].

Example 1:

Input: nums = [13,25,83,77]
Output: [1,3,2,5,8,3,7,7]
Explanation:
- The separation of 13 is [1,3].
- The separation of 25 is [2,5].
- The separation of 83 is [8,3].
- The separation of 77 is [7,7].
- answer = [1,3,2,5,8,3,7,7]. Note that answer contains the separations in the same order.

Example 2:

Input: nums = [7,1,3,9]
Output: [7,1,3,9]
Explanation:
- The separation of each integer in nums is itself.
- answer = [7,1,3,9].

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁵

Hint:

Convert each number into a list and append that list to the answer.
You can convert the integer into a string to do that easily.

Solution:

The problem requires taking an array of positive integers and returning a new array that contains the individual digits of each number, in the original order of numbers and digits.

The solution uses string conversion to split each number into its digits, then appends those digits to the result array.

Approach:

Iterate through each integer in the input array.
Convert each integer to a string to easily access each character (digit).
Split the string into an array of characters.
Convert each character back to an integer and append it to the result array.
Return the final array of digits.

Let's implement this solution in PHP: 2553. Separate the Digits in an Array

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

// Test cases
print_r(separateDigits([13,25,83,77])) . "\n";          // Output: [1,3,2,5,8,3,7,7]
print_r(separateDigits([7,1,3,9])) . "\n";              // Output: [7,1,3,9]
?>

Explanation:

Step 1: Initialize an empty array $answer to hold the final digits.
Step 2: Loop through each number $num in $nums.
Step 3: Convert $num to a string and split it into individual characters using str_split().
Step 4: Loop through each character in the split array, cast it to an integer, and push it to $answer.
Step 5: After processing all numbers, return $answer.

Complexity

Time Complexity: O(n * m), where n is the number of integers in nums and m is the maximum number of digits in any integer (up to 6 digits since nums[i] ≤ 10⁵).
Space Complexity: O(total digits) for the output array, which is the sum of digits across all numbers in nums.
Efficiency: The approach is optimal because we must output each digit exactly once.

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

2770. Maximum Number of Jumps to Reach the Last Index

MD ARIFUL HAQUE — Sun, 10 May 2026 17:59:19 +0000

2770. Maximum Number of Jumps to Reach the Last Index

Difficulty: Medium

Topics: Senior, Array, Dynamic Programming, Weekly Contest 353

You are given a 0-indexed array nums of n integers and an integer target.

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Example 1:

Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation:
- To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
- It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3.

Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation:
- To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
- It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5.

Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Hint:

Use a dynamic programming approach.
Define a dynamic programming array dp of size n, where dp[i] represents the maximum number of jumps from index 0 to index i.
For each j iterate over all i < j. Set dp[j] = max(dp[j], dp[i] + 1) if -target <= nums[j] - nums[i] <= target.

Solution:

The solution uses dynamic programming to find the maximum number of jumps from index 0 to index n-1 in the array nums, where each jump from i to j must satisfy -target ≤ nums[j] − nums[i] ≤ target.

If the last index is unreachable, return -1. The DP array tracks the maximum jumps possible to reach each index, and the answer is the value stored at the last index.

Approach:

Dynamic Programming Array: Create a dp array of size n where dp[i] stores the maximum number of jumps to reach index i from index 0. Initialize dp[0] = 0 and all others to -inf (or PHP_INT_MIN).
Transition: For each j from 1 to n-1, check all i < j. If the difference between nums[j] and nums[i] is within [-target, target] and dp[i] is not -inf, update dp[j] as max(dp[j], dp[i] + 1).
Result: If dp[n-1] is still -inf, return -1. Otherwise, return dp[n-1].

Let's implement this solution in PHP: 2770. Maximum Number of Jumps to Reach the Last Index

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

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

Explanation:

Initialization: dp[0] = 0 because we start at index 0 with 0 jumps. All other indices are initially unreachable (PHP_INT_MIN).
Outer loop (j): Iterates over each target index j from 1 to n-1 to compute the best way to reach j.
Inner loop (i): Checks all previous indices i from 0 to j-1 to see if a valid jump from i to j exists.
Valid jump condition: -target <= nums[j] - nums[i] <= target ensures the jump is allowed.
State update: If i is reachable (dp[i] != PHP_INT_MIN), then dp[j] = max(dp[j], dp[i] + 1) means we can extend the path ending at i to j with one more jump.
Why this works: The DP ensures that dp[j] always holds the maximum jumps to j because we consider all possible i < j that can jump to j and keep the best value.
Return: If dp[n-1] is still -inf, no sequence exists → return -1. Otherwise, return the computed maximum jumps.

Complexity

Time Complexity: O(n²), because we have two nested loops iterating over n elements each.
Space Complexity: O(n), for the DP array.

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

1914. Cyclically Rotating a Grid

MD ARIFUL HAQUE — Sat, 09 May 2026 14:57:33 +0000

1914. Cyclically Rotating a Grid

Difficulty: Medium

Topics: Senior, Array, Matrix, Simulation, Weekly Contest 247

You are given an m x n integer matrix grid, where m and n are both even integers, and an integer k.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:

Return the matrix after applying k cyclic rotations to it.

Example 1:

Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.

Example 2:

Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.

Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 50
Both m and n are even integers.
1 <= grid[i][j] <= 5000
1 <= k <= 10⁹

Hint:

First, you need to consider each layer separately as an array.
Just cycle this array and then re-assign it.

Solution:

The solution extracts each layer of the matrix into a 1D array, performs a counter-clockwise rotation by k positions (modulo the layer’s length), and then places the rotated values back into the layer in the correct order. This process is repeated for all layers.

Approach:

Since both m and n are even, the number of layers is min(m, n) / 2.
For each layer, extract its elements in counter-clockwise order: top row → right column → bottom row → left column.
Compute effective rotations: rot = k % len(elements).
Rotate the array using array_slice to move the first rot elements to the end (counter-clockwise = shift left).
Place the rotated elements back into the grid in the same traversal order.

Let's implement this solution in PHP: 1914. Cyclically Rotating a Grid

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

// Test cases
echo rotateGrid([[40,10],[30,20]], 1) . "\n";                                           // Output: [[10,20],[40,30]]
echo rotateGrid([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 2) . "\n";            // Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
?>

Explanation:

Layer extraction order matches the rotation direction (counter-clockwise), so rotating the 1D array corresponds to the required layer rotation.
Modulo operation reduces large k (up to 10⁹) to at most the layer’s perimeter length, making the solution efficient.
Traversal for reinsertion mirrors the extraction order to correctly place rotated elements into the grid.
The algorithm works for any even dimensions, with a straightforward way to handle each rectangular concentric layer.

Complexity

Time Complexity: O(m × n)
- Each element is visited a constant number of times (once to extract, once to reinsert).
- Layers are processed independently, and total elements = m × n.
Space Complexity: O(m + n), In each layer, we store its perimeter elements in a temporary array. The largest perimeter is at the outermost layer: 2 × (m + n) - 4, which is O(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

3629. Minimum Jumps to Reach End via Prime Teleportation

MD ARIFUL HAQUE — Fri, 08 May 2026 15:50:33 +0000

3629. Minimum Jumps to Reach End via Prime Teleportation

Difficulty: Medium

Topics: Staff, Array, Hash Table, Math, Breadth-First Search, Number Theory, Weekly Contest 460

You are given an integer array nums of length n.

You start at index 0, and your goal is to reach index n - 1.

From any index i, you may perform one of the following operations:

Adjacent Step: Jump to index i + 1 or i - 1, if the index is within bounds.
Prime Teleportation: If nums[i] is a prime number¹ p, you may instantly jump to any index j != i such that nums[j] % p == 0.

Return the minimum number of jumps required to reach index n - 1.

Example 1:

Input: nums = [1,2,4,6]
Output: 2
Explanation:
- One optimal sequence of jumps is:
- Start at index i = 0. Take an adjacent step to index 1.
- At index i = 1, nums[1] = 2 is a prime number. Therefore, we teleport to index i = 3 as nums[3] = 6 is divisible by 2.
- Thus, the answer is 2.

Example 2:

Input: nums = [2,3,4,7,9]
Output: 2
Explanation:
- One optimal sequence of jumps is:
- Start at index i = 0. Take an adjacent step to index i = 1.
- At index i = 1, nums[1] = 3 is a prime number. Therefore, we teleport to index i = 4 since nums[4] = 9 is divisible by 3.
- Thus, the answer is 2.

Example 3:

Input: nums = [4,6,5,8]
Output: 3
Explanation: Since no teleportation is possible, we move through 0 → 1 → 2 → 3. Thus, the answer is 3.

Constraints:

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

Hint:

Use a breadth-first search.
Precompute prime factors of each nums[i] via a sieve, and build a bucket bucket[p] mapping each prime p to all indices j with nums[j] % p == 0.
During the BFS, when at index i, enqueue its adjacent steps (i+1 and i-1) and all indices in bucket[p] for each prime p dividing nums[i], then clear bucket[p] so each prime's bucket is visited only once.

Solution:

This solution uses Breadth-First Search (BFS) to find the shortest path from index 0 to index n-1 in an array.

Jumps can be either adjacent moves (i+1 or i-1) or prime teleportation — if nums[i] is prime, you can jump to any index j where nums[j] is divisible by that prime.

To optimize, the solution:

Precomputes prime factors of all numbers using a Sieve of Eratosthenes.
Builds a mapping from each prime to indices whose values are divisible by it.
During BFS, when a prime-numbered index is reached, all indices in its bucket are enqueued at once, and the bucket is cleared to avoid repeated processing.

Approach:

BFS for shortest path: Since all jumps have equal cost (1 jump), BFS guarantees minimal steps.
Precomputation with SPF (Smallest Prime Factor):
- A sieve finds the smallest prime factor for all numbers up to max(nums).
- This enables efficient factorization and prime checking.
Bucket mapping:
- For each index i, factorize nums[i] using the SPF array.
- For each distinct prime factor p, add i to bucket[p].
BFS queue state: (index, distance)
Adjacent moves: Always enqueue neighbors if unvisited.
Prime teleportation:
- If nums[i] is prime p, and we haven't visited p before, enqueue all indices in bucket[p] (except current) and clear bucket[p] to prevent re-processing.
Visited tracking:
- visitedIndex for indices.
- visitedPrime for primes to avoid teleporting from the same prime multiple times.

Let's implement this solution in PHP: 3629. Minimum Jumps to Reach End via Prime Teleportation

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

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

Explanation:

Step 1 — Sieve for SPF
- Build spf[x] = smallest prime factor of x for all x up to max(nums).
- This allows quick factorization and prime checking in O(log x).
Step 2 — Build prime-to-indices buckets
- For each nums[i], factorize it using SPF to get unique prime factors.
- For each prime p in factors, append i to bucket[p].
Step 3 — BFS initialization
- Start at index 0 with distance 0, mark visited.
Step 4 — Process each index in BFS
- If current index is target, return distance.
- Enqueue i-1 and i+1 if unvisited.
- If current number is prime p and p not visited before:
  - Enqueue all indices in bucket[p] that are unvisited.
  - Delete bucket[p] to avoid future use (primes are used once).
Step 5 — BFS guarantees minimum steps
- First time we reach target is guaranteed to have minimum jumps.

Complexity

Time Complexity:
- Sieve: O(M log log M) where M = max(nums) ≤ 1e6.
- Bucket building: O(n log M) — each number factorized in O(log M).
- BFS: Each index enqueued once (O(n)), each prime bucket cleared once.
- Overall: O(M log log M + n log M), efficient for constraints.
Space Complexity:
- SPF array: O(M).
- Buckets: O(n + total factors) — each index stored once per distinct prime factor.
- Visited sets: O(n + P) where P is number of primes ≤ M.
- Queue: O(n).
- Overall: O(n + M).

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

Prime: A prime number is a natural number greater than 1 with only two factors, 1 and itself. ↩

3660. Jump Game IX

MD ARIFUL HAQUE — Thu, 07 May 2026 18:27:29 +0000

3660. Jump Game IX

Difficulty: Medium

Topics: Staff, Array, Dynamic Programming, Weekly Contest 464

You are given an integer array nums.

From any index i, you can jump to another index j under the following rules:

Jump to index j where j > i is allowed only if nums[j] < nums[i].
Jump to index j where j < i is allowed only if nums[j] > nums[i].

For each index i, find the maximum value in nums that can be reached by following any sequence of valid jumps starting at i.

Return an array ans where ans[i] is the maximum value reachable starting from index i.

Example 1:

Input: nums = [2,1,3]
Output: [2,2,3]
Explanation:
- For i = 0: No jump increases the value.
- For i = 1: Jump to j = 0 as nums[j] = 2 is greater than nums[i].
- For i = 2: Since nums[2] = 3 is the maximum value in nums, no jump increases the value.
- Thus, ans = [2, 2, 3].

Example 2:

Input: nums = [2,3,1]
Output: [3,3,3]
Explanation:
- For i = 0: Jump forward to j = 2 as nums[j] = 1 is less than nums[i] = 2, then from i = 2 jump to j = 1 as nums[j] = 3 is greater than nums[2].
- For i = 1: Since nums[1] = 3 is the maximum value in nums, no jump increases the value.
- For i = 2: Jump to j = 1 as nums[j] = 3 is greater than nums[2] = 1.
- Thus, ans = [3, 3, 3].

Constraints:

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

Hint:

Think of the array as a directed graph where edges represent valid jumps.
From index i, forward jumps go only to smaller values; backward jumps go only to larger values.
The maximum reachable value from i is the maximum value in the connected component reachable under these jump rules.
You can find connected ranges by looking at prefix maximums and suffix minimums, a cut happens where all values to the left are <= all values to the right.

Solution:

This problem involves a directed graph where each index i can jump to a larger index j if nums[j] < nums[i], or to a smaller index j if nums[j] > nums[i].

The goal is to determine, for each starting index, the maximum value reachable via any sequence of valid jumps.

The solution uses the observation that the array can be partitioned into segments where all values in a segment are either all larger or all smaller than values in adjacent segments — meaning no valid jumps can cross segment boundaries.

Inside each segment, any index can reach every other index, so the maximum reachable value from any index in the segment is simply the maximum value in that segment.

Approach:

Precompute prefix maximums and suffix minimums to identify segment boundaries.
Segment definition: A cut occurs at index i if all values up to i are ≤ all values after i. This ensures no jump can cross this boundary.
Segment building: Scan from left to right, when prefixMax[i] <= suffixMin[i+1], end current segment and start new one.
Result assignment: For each segment, find its maximum value and assign it to every index in the segment.

Let's implement this solution in PHP: 3660. Jump Game IX

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

// Test cases
$nums = [2,1,3];
print_r(jumpGameIX($nums));

$nums = [2,3,1];
print_r(jumpGameIX($nums));
?>

Explanation:

Prefix max array: prefixMax[i] = max value from nums[0..i]
Suffix min array: suffixMin[i] = min value from nums[i..n-1]
Why prefixMax[i] <= suffixMin[i+1] works as a cut:
- All elements on left ≤ all elements on right
- Any forward jump (j > i) requires nums[j] < nums[i], but if right side values are larger, impossible
- Any backward jump (j < i) requires nums[j] > nums[i], but if left side values are smaller, impossible
- So no edge across this boundary
Inside a segment, the graph is strongly connected (can reach any index), so max value in segment = answer for all indices in that segment.

Complexity

Time Complexity: O(n)
- Two linear passes for prefix & suffix arrays
- One linear pass to build segments
- One linear pass to assign values
Space Complexity: O(n) - Stores prefixMax, suffixMin, ans arrays (can be optimized but fine for constraints)

Contact Links

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

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

LinkedIn
GitHub

61. Rotate List

MD ARIFUL HAQUE — Tue, 05 May 2026 17:09:44 +0000

61. Rotate List

Difficulty: Medium

Topics: Linked List, Two Pointers

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

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

Example 2:

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

Example 3:

Input: head = [1], k = 0
Output: [1]

Example 4:

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

Example 5:

Input: head = [], k = 5
Output: []

Example 6:

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

Constraints:

The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 10⁹

Solution:

This solution rotates a singly linked list to the right by k places in O(n) time and O(1) space. It first computes the list length, reduces k modulo the length, finds the new head and tail, then performs the rotation by linking the tail to the old head and breaking the list at the new tail.

Approach:

Find list length and tail node to handle cases where k is larger than the list length.
Reduce k by taking k % length to avoid unnecessary rotations.
Locate new tail at position length - k - 1 using traversal from head.
Perform rotation by making the original tail point to the original head, and the new tail point to null.
Return new head, which is the node after the new tail.

Let's implement this solution in PHP: 61. Rotate List

<?php
/**
 * @param ListNode $head
 * @param Integer $k
 * @return ListNode
 */
function rotateRight($head, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation:

Edge Cases If the list is empty, has one node, or k == 0, return the head immediately.
Find length and tail Traverse the list to count nodes and store the last node.
Optimize k Since rotating by length gives the same list, set k = k % length. If k == 0, no rotation is needed.
Find new tail position The new tail is at index length - k - 1 (0-based). Traverse from head to this node.
Re-link nodes
- Original tail's next points to original head (close loop).
- New tail's next is set to null (break loop).
- New head is newTail->next.
Return new head This completes the rotation.

Complexity

Time Complexity: O(n) - One pass to find length, another partial pass to find new tail.
Space Complexity: O(1) - Only a few pointers used, no extra data structures.

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

48. Rotate Image

MD ARIFUL HAQUE — Mon, 04 May 2026 15:09:21 +0000

48. Rotate Image

Difficulty: Medium

Topics: Array, Math, Matrix

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution:

The solution rotates an n x n matrix 90 degrees clockwise in-place without using extra memory. It achieves this by a two-step process: first transposing the matrix (swap rows and columns), then reversing each row. This approach is a standard and efficient solution for this problem.

Approach:

Transpose the matrix — Convert all matrix[i][j] to matrix[j][i] by swapping elements across the diagonal.
Reverse each row — After transposition, reversing the order of elements in each row effectively completes the 90° clockwise rotation.
In-place operations — Both steps modify the original matrix directly, satisfying the problem constraint.

Let's implement this solution in PHP: 48. Rotate Image

<?php
/**
 * @param Integer[][] $matrix
 * @return NULL
 */
function rotate(array &$matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo rotate([[1,2,3],[4,5,6],[7,8,9]]) . "\n";                                  // Output: [[7,4,1],[8,5,2],[9,6,3]]
echo rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]) . "\n";           // Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
?>

Explanation:

Transpose brings rows into columns, which is part of the rotation but in the wrong order.
- In a 3×3 matrix, first row [1, 2, 3] becomes first column [1, 4, 7] after transpose.
Reversing each row arranges these columns horizontally in the correct order for clockwise rotation.
- After transpose, first row is [1, 4, 7]. After reversal → [7, 4, 1], which matches final first row.
For a matrix of size n, the inner loop for transpose starts at i + 1 to avoid double-swapping.
The reversal step uses array_reverse for simplicity, but a manual swap loop would also work and be just as efficient.

Complexity

Time Complexity: O(n²) — Each element is accessed once during transpose (n²/2 swaps) and once during row reversal (n × n/2 swaps).
Space Complexity: O(1) — Only a constant amount of extra space is 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

788. Rotated Digits

MD ARIFUL HAQUE — Sat, 02 May 2026 17:39:42 +0000

788. Rotated Digits

Difficulty: Medium

Topics: Senior, Math, Dynamic Programming, Weekly Contest 73

An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. For example:

0, 1, and 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
6 and 9 rotate to each other, and
the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

Example 1:

Input: n = 10
Output: 4
Explanation:
- There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
- Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 2
Output: 1

Example 4:

Input: n = 100
Output: 40

Example 5:

Input: n = 30
Output: 13

Example 5:

Input: n = 10000
Output: 2320

Constraints:

1 <= n <= 10⁴

Solution:

The solution counts integers between 1 and n that are good — meaning when each digit is rotated 180°, the resulting number is different from the original and contains no invalid digits (3, 4, 7).

It iterates over each number, checks digit-by-digit using the rotation rules, and increments a counter for good numbers.

Approach:

Loop through all integers from 1 to n.
For each number, check if it is “good” using digit-by-digit validation.
A number is not good if:
- Any digit is 3, 4, or 7 (invalid).
- After rotation, the number remains unchanged (i.e., contains only 0, 1, or 8).
A number is good if:
- No invalid digits.
- At least one digit from {2,5,6,9} exists (since those change on rotation).
Return the total count.

Let's implement this solution in PHP: 788. Rotated Digits

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

/**
 * Check if a number is "good"
 *
 * @param Integer $num
 * @return bool
 */
function isGood(int $num): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo rotatedDigits(10) . "\n";          // Output: 4
echo rotatedDigits(1) . "\n";           // Output: 0
echo rotatedDigits(2) . "\n";           // Output: 1
echo rotatedDigits(100) . "\n";         // Output: 40
echo rotatedDigits(30) . "\n";          // Output: 13
echo rotatedDigits(10000) . "\n";       // Output: 2320
?>

Explanation:

Digit rotation mapping:
- 0,1,8 → rotate to themselves.
- 2,5 → rotate to each other.
- 6,9 → rotate to each other.
- 3,4,7 → become invalid.
Why hasRotating flag?
- If all digits are in {0,1,8}, the rotated number equals the original → not good.
- If any digit is in {2,5,6,9}, the rotated number is different → good.
Early exit: If an invalid digit 3,4,7 is found, the number is immediately rejected.

Complexity

Time Complexity: O(n * d), where d is the number of digits in n (at most 5 for n ≤ 10⁴). So roughly O(n log₁₀ n).
Space Complexity: O(1) — only a few variables used per iteration.
Trade-off: Simple implementation but linear in n, which is fine given the constraint n ≤ 10⁴.

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

396. Rotate Function

MD ARIFUL HAQUE — Fri, 01 May 2026 17:54:26 +0000

396. Rotate Function

Difficulty: Medium

Topics: Junior, Array, Math, Dynamic Programming

You are given an integer array nums of length n.

Assume arrₖ to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

F(k) = 0 * arrₖ[0] + 1 * arrₖ[1] + ... + (n - 1) * arrₖ[n - 1].

Return the maximum value of F(0), F(1), ..., F(n-1).

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: nums = [4,3,2,6]
Output: 26
Explanation:
- F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
- F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
- F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
- F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
- So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

Input: nums = [100]
Output: 0

Example 3:

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

Constraints:

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

Solution:

The solution efficiently computes the maximum value of the rotation function F(k) without explicitly rotating the array for each k.

It calculates F(0) directly, then derives each subsequent F(k) from the previous one using a mathematical recurrence relation.

This approach avoids the O(n²) brute force and runs in O(n) time and O(1) extra space.

Approach:

Direct calculation of F(0) F(0) = 0*nums[0] + 1*nums[1] + ... + (n-1)*nums[n-1] is computed in one pass.
Mathematical recurrence for F(k) Rotating the array clockwise by one position changes F(k) as follows: F(k) = F(k-1) + sum(nums) - n ⋅ nums[n-k].
Iterative update Start from F(0) and apply the recurrence for each rotation k = 1 to n-1, tracking the maximum value.
Edge case handling If n == 1, return 0 immediately since F(0) = 0.

Let's implement this solution in PHP: 396. Rotate Function

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

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

Explanation:

Why the recurrence works
- When rotating one step clockwise, the last element becomes first, increasing its coefficient from n-1 to 0 (a drop of n-1), and all other elements shift right, increasing their coefficients by 1.
- The net change is: F(k) = F(k-1) + sum(nums) - n ⋅ last element before rotation.
Avoiding array rotation By keeping track of which element is currently last in the virtual rotation (nums[$n - $k - 1]), the formula works directly on the original array.
One-pass optimization Instead of recomputing F(k) from scratch each time, we update in O(1) per k, leading to O(n) total operations.

Complexity

Time Complexity: O(n), One pass to compute sum and F(0), plus one pass to update and compare for n-1 rotations.
Space Complexity: O(1), Only a few integer variables are used, regardless of input size.

Contact Links

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

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

LinkedIn
GitHub

3742. Maximum Path Score in a Grid

MD ARIFUL HAQUE — Thu, 30 Apr 2026 17:50:02 +0000

3742. Maximum Path Score in a Grid

Difficulty: Medium

Topics: Staff, Array, Dynamic Programming, Matrix, Weekly Contest 475

You are given an m x n grid where each cell contains one of the values 0, 1, or 2. You are also given an integer k.

You start from the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1) by moving only right or down.

Each cell contributes a specific score and incurs an associated cost, according to their cell values:

0: adds 0 to your score and costs 0.
1: adds 1 to your score and costs 1.
2: adds 2 to your score and costs 1.

Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.

Note: If you reach the last cell but the total cost exceeds k, the path is invalid.

Example 1:

Input: grid = [[0, 1],[2, 0]], k = 1
Output: 2
Explanation: The optimal path is:

Cell	`grid[i][j]`	Score	Total Score	Cost	Total Cost
(0,0)	0	0	0	0	0
(0,1)	2	2	2	1	1
(1,1)	0	0	2	0	1

Thus, the maximum possible score is 2.

Example 2:

Input: grid = [[0, 1],[1, 2]], k = 1
Output: -1
Explanation: There is no path that reaches cell (1, 1) without exceeding cost k. Thus, the answer is -1.

Constraints:

1 <= m, n <= 200
0 <= k <= 10³
grid[0][0] == 0
0 <= grid[i][j] <= 2

Hint:

Use dynamic programming.
Let dp[i][j][c] = max score at cell (i,j) with total cost exactly c (0 <= c <= k).
Update dp[i][j][c] from (i-1,j) and (i,j-1) using cost = (grid[i][j] == 0 ? 0 : 1) and score = grid[i][j].
Answer = max(dp[m-1][n-1][c]) for c=0..k, or -1 if none.

Solution:

This problem asks for the maximum score from (0,0) to (m-1,n-1) moving only right or down, where each cell contributes a score and a cost based on its value (0→score 0, cost 0; 1→score 1, cost 1; 2→score 2, cost 1), with a total cost limit k. The solution uses dynamic programming where dp[i][j][c] is the maximum score at cell (i,j) with exactly cost c, and transitions come from left or above. To save memory, we only keep two rows of dp states.

Approach:

DP definition dp[i][j][c] = maximum score achievable at cell (i,j) with total cost exactly c.
Transitions From (i-1,j) (above) or (i,j-1) (left), add the current cell’s score and cost.
Memory optimization
- Since m, n ≤ 200 and k ≤ 10³, a full 3D array would be large (~ 200 × 200 × 1001 ints).
- We use two 2D arrays prev (for previous row) and curr (for current row), each of size n × (k+1).
Initialization (0,0) starts with its own cost and score.
Processing
- First row: fill left to right.
- Then for each next row, process first column using prev, then remaining columns using both prev and curr.
Answer Max of dp[m-1][n-1][c] for all c ≤ k. If all -1, return -1.

Let's implement this solution in PHP: 3742. Maximum Path Score in a Grid

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

// Test cases
$grid1 = [[0, 1], [2, 0]];
$k1 = 1;
echo maxPathScore($grid1, $k1) . "\n";              // Output: 2

$grid2 = [[0, 1], [1, 2]];
$k2 = 1;
echo maxPathScore($grid2, $k2) . "\n";              // Output: -1
?>

Explanation:

Step 1: Start at (0,0) Only one path starts here. Add its cost and score to dp[0][0][cost].
Step 2: Fill first row Each cell only has a path from left. For each previous cost c that’s reachable, create new cost = c + cell_cost, new score = prev_score + cell_score.
Step 3: Fill first column of next rows Each cell only has a path from above. Same transition logic.
Step 4: Fill remaining cells Each cell can come from left (already in curr) or above (in prev). Take max of both transitions.
Step 5: Answer retrieval After processing all rows, last cell’s DP array contains max scores for each exact cost. We want max score for cost ≤ k, so loop over all costs up to k.

Complexity

Time Complexity: O(m × n × k) — For each cell, we loop over all costs c from 0..k to update from two possible previous cells.
Space Complexity: O(n × k) — Only two rows of n × (k+1) DP tables are kept at any time.

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