DEV Community: MD ARIFUL HAQUE

1306. Jump Game III

MD ARIFUL HAQUE — Sun, 17 May 2026 15:37:06 +0000

1306. Jump Game III

Difficulty: Medium

Topics: Staff, Array, Depth-First Search, Breadth-First Search, Weekly Contest 169

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
- All possible ways to reach at index 3 with value 0 are:
- index 5 -> index 4 -> index 1 -> index 3
- index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
- One possible way to reach at index 3 with value 0 is:
- index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] < arr.length
0 <= start < arr.length

Hint:

Think of BFS to solve the problem.
When you reach a position with a value = 0 then return true.

Solution:

This solution solves Jump Game III using a BFS (Breadth-First Search) approach. Starting from the given start index, it explores all reachable positions by jumping forward or backward by arr[i] steps. It stops early and returns true as soon as it finds an index whose value is 0. If BFS completes without finding a zero, it returns false.

The solution is efficient and avoids revisiting indices, making it suitable for arrays up to 50,000 elements.

Approach:

Use BFS to systematically explore reachable indices level by level.
Maintain a visited array to prevent revisiting indices and avoid infinite loops.
Start from the start index and push it into a queue.
While the queue is not empty:
- Pop the current index i.
- If arr[i] == 0, return true.
- Compute forward = i + arr[i] and backward = i - arr[i].
- If forward is within bounds and not visited, mark visited and enqueue it.
- If backward is within bounds and not visited, mark visited and enqueue it.
If BFS finishes, return false (no zero reachable).

Let's implement this solution in PHP: 1306. Jump Game III

<?php
/**
 * @param Integer[] $arr
 * @param Integer $start
 * @return Boolean
 */
function canReach(array $arr, int $start): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(canReach([4,2,3,0,3,1,2], 5)) . "\n";           // Output: true
var_dump(canReach([4,2,3,0,3,1,2], 0)) . "\n";           // Output: true
var_dump(canReach([3,0,2,1,2], 2)) . "\n";               // Output: false
?>

Explanation:

BFS guarantees we explore all possible paths without recursion depth issues.
Visited array is crucial to prevent reprocessing indices, which could happen if there are cycles in jumps.
Early termination happens as soon as a zero is found, optimizing performance.
This method works because each jump is deterministic: from i you can only go to i ± arr[i].
BFS is preferred over DFS here because it naturally finds the shortest path, though for this problem the first zero found is sufficient.

Complexity

Time Complexity: O(n), Each index is visited at most once, and each visit does constant-time work.
Space Complexity: O(n), Due to the visited array and queue (which in worst case can hold all indices).

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

154. Find Minimum in Rotated Sorted Array II

MD ARIFUL HAQUE — Sat, 16 May 2026 13:23:36 +0000

154. Find Minimum in Rotated Sorted Array II

Difficulty: Hard

Topics: Array, Binary Search

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

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

Example 2:

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

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Solution:

This solution uses a modified binary search to find the minimum element in a rotated sorted array that may contain duplicates.

Unlike the standard version (Leetcode 153), duplicate values can appear anywhere in the array, which can make it impossible to determine which half contains the minimum using a simple comparison of nums[mid] and nums[high].

The algorithm handles this by reducing the search space when a tie occurs between nums[mid] and nums[high].

Approach:

Binary Search with Duplicate Handling Use two pointers low and high to define the current search range.
Compare nums[mid] and nums[high]
- If nums[mid] > nums[high]: Minimum is in the right half → move low to mid + 1.
- If nums[mid] < nums[high]: Minimum is in the left half → move high to mid.
- If nums[mid] == nums[high]: Cannot decide, so reduce high by 1 to remove a duplicate from consideration.
Terminate when low == high At that point, nums[low] is the minimum.

Let's implement this solution in PHP: 154. Find Minimum in Rotated Sorted Array II

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

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

Explanation:

Binary search is efficient for sorted rotated arrays, but duplicates can break the deterministic half-elimination.
When nums[mid] > nums[high], the array is rotated such that the minimum lies strictly to the right of mid.
When nums[mid] < nums[high], the segment from mid to high is properly sorted, so the minimum must be at or before mid.
When nums[mid] == nums[high], we can't tell if the minimum is left or right — but since nums[mid] equals nums[high], we can safely shrink the range by ignoring high.
This approach still works in O(log n) on average, but degrades to O(n) in worst case (e.g., when all elements are equal).

Complexity

Time Complexity:
- Average: O(log n)
- Worst case (all elements equal): O(n)
Space Complexity: O(1) — only a few variables used.

Contact Links

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

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

LinkedIn
GitHub

153. Find Minimum in Rotated Sorted Array

MD ARIFUL HAQUE — Fri, 15 May 2026 17:41:30 +0000

153. Find Minimum in Rotated Sorted Array

Difficulty: Medium

Topics: Array, Binary Search

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Hint:

Array was originally in ascending order. Now that the array is rotated, there would be a point in the array where there is a small deflection from the increasing sequence. eg. The array would be something like [4, 5, 6, 7, 0, 1, 2].
You can divide the search space into two and see which direction to go. Can you think of an algorithm which has O(logN) search complexity?
All the elements to the left of inflection point > first element of the array.
All the elements to the right of inflection point < first element of the array.

Solution:

This solution finds the minimum element in a rotated sorted array of unique integers using binary search in O(log n) time.

It compares the middle element with the rightmost element to decide whether the minimum lies in the left or right half.

Approach:

Binary search on rotated sorted array Use left and right pointers, compute mid, and compare nums[mid] with nums[right].
If nums[mid] > nums[right] The smallest element must be in the right half, so move left to mid + 1.
If nums[mid] <= nums[right] The smallest element is in the left half (including mid), so move right to mid.
Terminate when left == right That position holds the minimum.

Let's implement this solution in PHP: 153. Find Minimum in Rotated Sorted Array

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

// Test cases
echo findMin([3,4,5,1,2]) . "\n";                   // Output: 1
echo findMin([4,5,6,7,0,1,2]) . "\n";               // Output: 0
echo findMin([11,13,15,17]) . "\n";                 // Output: 11
?>

Explanation:

The array is a sorted array that has been rotated, so it consists of two increasing segments: [large increasing part, small increasing part].
The minimum is the start of the second segment.
Comparing mid with right helps determine which segment mid lies in:
- If mid > right, then mid is in the first larger segment, so min is to the right.
- If mid <= right, then mid is in the second smaller segment or the right part, so min is to the left or at mid.
This comparison works because all elements are unique and sorted, so no ambiguity.
The loop ends when the search space narrows to one element — the minimum.

Complexity

Time Complexity: O(log n) — each step halves the search space.
Space Complexity: O(1) — only a few integer variables used.

Contact Links

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

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

LinkedIn
GitHub

2784. Check if Array is Good

MD ARIFUL HAQUE — Thu, 14 May 2026 16:48:54 +0000

2784. Check if Array is Good

Difficulty: Easy

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

You are given an integer array nums. We consider an array good if it is a permutation of an array base[n].

base[n] = [1, 2, ..., n - 1, n, n] (in other words, it is an array of length n + 1 which contains 1 to n - 1 exactly once, plus two occurrences of n). For example, base[1] = [1, 1] and base[3] = [1, 2, 3, 3].

Return true if the given array is good, otherwise return false.

Note: A permutation of integers represents an arrangement of these numbers.

Example 1:

Input: nums = [2, 1, 3]
Output: false
Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. However, base[3] has four elements but array nums has three. Therefore, it can not be a permutation of base[3] = [1, 2, 3, 3]. So the answer is false.

Example 2:

Input: nums = [1, 3, 3, 2]
Output: true
Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. It can be seen that nums is a permutation of base[3] = [1, 2, 3, 3] (by swapping the second and fourth elements in nums, we reach base[3]). Therefore, the answer is true.

Example 3:

Input: nums = [1, 1]
Output: true
Explanation: Since the maximum element of the array is 1, the only candidate n for which this array could be a permutation of base[n], is n = 1. It can be seen that nums is a permutation of base[1] = [1, 1]. Therefore, the answer is true.

Example 4:

Input: nums = [3, 4, 4, 1, 2, 1]
Output: false
Explanation: Since the maximum element of the array is 4, the only candidate n for which this array could be a permutation of base[n], is n = 4. However, base[4] has five elements but array nums has six. Therefore, it can not be a permutation of base[4] = [1, 2, 3, 4, 4]. So the answer is false.

Constraints:

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

Hint:

Find the maximum element of the array.

Solution:

The solution determines if an array is a permutation of base[n] = [1, 2, ..., n-1, n, n].

It first finds the maximum element n in nums, then verifies the array length matches n+1, and finally checks that numbers 1 to n-1 appear exactly once, and n appears exactly twice.

Approach:

Step 1: Find the maximum value n in nums.
Step 2: Check if the array length equals n + 1 (since base[n] has n+1 elements).
Step 3: Count frequency of each number in nums.
Step 4: Verify that numbers from 1 to n-1 appear exactly once.
Step 5: Verify that n appears exactly twice.
Step 6: If all checks pass, return true; otherwise, return false.

Let's implement this solution in PHP: 2784. Check if Array is Good

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

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

Explanation:

Find candidate n: The maximum element of nums must be the n in base[n] because base[n] contains 1 to n-1 once, and n twice (so n is the largest number in the array).
Length check: base[n] has length n+1. If nums length is different, it cannot be a permutation.
Frequency check for 1 to n-1: Each of these numbers must appear exactly once.
Frequency check for n: n must appear exactly twice.
Early returns: The solution fails as soon as any condition is violated, making it efficient.

Complexity

Time Complexity: O(m)*
- Where m is the length of nums.
- max() is O(m), array_count_values() is O(m), loop from 1 to n-1 is O(n) ≤ O(m) since n+1 = m if valid.
Space Complexity: O(m)
- Frequency array stores at most m distinct entries.

Contact Links

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

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

LinkedIn
GitHub

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