DEV Community: MD ARIFUL HAQUE

1391. Check if There is a Valid Path in a Grid

MD ARIFUL HAQUE — Mon, 27 Apr 2026 16:42:46 +0000

1391. Check if There is a Valid Path in a Grid

Difficulty: Medium

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

You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Hint:

Start DFS from the node (0, 0) and follow the path till you stop.
When you reach a cell and cannot move anymore check that this cell is (m - 1, n - 1) or not.

Solution:

The problem requires checking whether there exists a valid path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) strictly following the predefined connections of each street type. A DFS (Depth-First Search) approach is used to explore connected cells according to street shapes, ensuring movement is only possible when the current street and the neighbor’s street align properly.

Approach:

Grid Traversal with DFS Start from the source cell (0, 0) and recursively explore reachable cells.
Street Connection Mapping Each street type (1–6) has specific connection directions: 0=Up, 1=Right, 2=Down, 3=Left.
Compatibility Check Between Cells When moving from a cell to a neighbor, the neighbor must support the opposite movement direction relative to the current cell.
Visited Tracking Prevent revisiting cells to avoid infinite loops.
Termination Condition Stop and return true if the bottom-right cell is reached.

Let's implement this solution in PHP: 1391. Check if There is a Valid Path in a Grid

<?php
class Solution {
    private int $m;
    private int $n;
    private array $grid;

    // Directions: up, right, down, left
    private array $dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];

    // For each street type (1-6), list of directions it connects to
    // Up:0, Right:1, Down:2, Left:3
    private array $connections = [
        1 => [1, 3],      // left and right
        2 => [0, 2],      // up and down
        3 => [2, 3],      // down and left
        4 => [1, 2],      // right and down
        5 => [0, 3],      // up and left
        6 => [0, 1]       // up and right
    ];

    // Inverse mapping: from direction to required connection in neighbor
    // If we go from current cell to neighbor in direction d,
    // neighbor must have the opposite direction in its connections
    private array $opposite = [2, 3, 0, 1]; // opposite[0]=2 (up<->down), etc.

    /**
     * @param Integer[][] $grid
     * @return Boolean
     */
    function hasValidPath(array $grid): bool
    {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $r
     * @param $c
     * @param $visited
     * @return bool
     */
    private function dfs($r, $c, &$visited): bool
    {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Test cases
$solution = new Solution();
$result1 = $solution->hasValidPath([[2,4,3],[6,5,2]]);
echo ($result1 ? "true" : "false") . "\n\n";            // Output: true
$result1 = $solution->hasValidPath([[1,2,1],[1,2,1]]);
echo ($result1 ? "true" : "false") . "\n\n";            // Output: false
$result1 = $solution->hasValidPath([[1,1,2]]);
echo ($result1 ? "true" : "false") . "\n\n";            // Output: false
?>

Explanation:

Street Connections Array
- For each street type, store which directions it connects to.
- Example:
- Street 1 (left-right) → [3, 1] (Left, Right)
- Street 2 (up-down) → [0, 2] (Up, Down)
Opposite Directions Array
- For a given moving direction, the entering direction for the neighbor is opposite.
- Example: If we go right (1), the neighbor must accept entry from left (3).
DFS Logic
1. If current cell is the destination → return true.
2. Mark current cell as visited.
3. For each allowed direction of current street:
  - Compute neighbor coordinates.
  - If neighbor inside bounds and not visited:
    - Check if neighbor’s connections include the required opposite direction.
    - If yes, recursively DFS from neighbor.
    - If DFS returns true, propagate true.
4. If all directions fail, return false.
Why DFS Works Since the path is deterministic once you choose a valid direction (no cycles possible except back-and-forth which visited prevents), DFS reliably explores all possible connected routes.

Complexity

Time Complexity: O(m * n), Each cell is visited at most once, and at each cell, only a constant number of directions is checked.
Space Complexity: O(m * n), For the visited matrix and recursion stack in worst case (if the grid is fully traversable).

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

1559. Detect Cycles in 2D Grid

MD ARIFUL HAQUE — Sun, 26 Apr 2026 17:45:41 +0000

1559. Detect Cycles in 2D Grid

Difficulty: Medium

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

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle(1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid consists only of lowercase English letters.

Hint:

Keep track of the parent (previous position) to avoid considering an invalid path.
Use DFS or BFS and keep track of visited cells to see if there is a cycle.

Solution:

We need to detect a cycle where all cells in the cycle have the same character, the cycle length is at least 4, and we cannot instantly go back to the parent cell.
A cycle exists if during DFS/BFS we encounter a cell that is already visited and is not the parent cell — because if it’s visited and not parent, then we’ve found a cycle.

Approach:

We can solve this with DFS, keeping track of the parent of each cell in the traversal so we can avoid simply backtracking to the previous cell.

Steps:

Loop through each cell, if not visited, start DFS.
In DFS:
- Mark current cell as visited.
- Explore all four neighbors with the same character.
- If the neighbor is visited and is not the parent cell → cycle found.
- If neighbor not visited, recurse with current cell as parent.
If at any point we find a cycle, return true.
If no cycles found after all cells, return false.

Let's implement this solution in PHP: 1559. Detect Cycles in 2D Grid

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

// Test cases
echo containsCycle([["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]) . "\n";           // Output: true
echo containsCycle([["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]) . "\n";           // Output: true
echo containsCycle([["a","b","b"],["b","z","b"],["b","b","a"]]) . "\n";                                         // Output: false
?>

Explanation:

DFS function Marks current cell as visited, stores its character, and checks all four directions.
Neighbor validity Ensures neighbor is within bounds and has the same character as the current cell.
Cycle check If neighbor is visited and is not the parent → cycle exists → return true.
Recursive exploration If neighbor is unvisited, recursively call DFS. If any call returns true, propagate result.
Main loop For each unvisited cell, start DFS. If cycle found, return true immediately.
No cycle found After traversing all cells, return false.

Complexity

Time Complexity: O(m × n), Each cell is visited once in DFS (ignoring constant-time neighbor checks).
Space Complexity: O(m × n), For the visited matrix and the recursion stack in worst case (e.g., entire grid same char forming a path).

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

3464. Maximize the Distance Between Points on a Square

MD ARIFUL HAQUE — Sat, 25 Apr 2026 15:19:22 +0000

3464. Maximize the Distance Between Points on a Square

Difficulty: Hard

Topics: Principal, Array, Math, Binary Search, Geometry, Sorting, Weekly Contest 438

You are given an integer side, representing the edge length of a square with corners at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane.

You are also given a positive integer k and a 2D integer array points, where points[i] = [xi, yi] represents the coordinate of a point lying on the boundary of the square.

You need to select k elements among points such that the minimum Manhattan distance between any two points is maximized.

Return the maximum possible minimum Manhattan distance between the selected k points.

The Manhattan Distance between two cells (xᵢ, yᵢ) and (xⱼ, yⱼ) is |xᵢ - xⱼ| + |yᵢ - yⱼ|.

Example 1:

Input: side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
Output: 2
Explanation: Select all four points.

Example 2:

Input: side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
Output: 1
Explanation: Select the points (0, 0), (2, 0), (2, 2), and (2, 1).

Example 3:

Input: side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
Output: 1
Explanation:

Select the points (0, 0), (0, 1), (0, 2), (1, 2), and (2, 2).

Example 4:

Input: side = 40, points = [[0,14],[0,40],[32,0],[0,30],[34,40]], k = 4
Output: 26

Constraints:

1 <= side <= 10⁹
4 <= points.length <= min(4 * side, 15 * 10³)
points[i] == [xi, yi]
The input is generated such that:
- points[i] lies on the boundary of the square.
- All points[i] are unique.
4 <= k <= min(25, points.length)

Hint:

Can we use binary search for this problem?
Think of the coordinates on a straight line in clockwise order.
Binary search on the minimum Manhattan distance x.
During the binary search, for each coordinate, find the immediate next coordinate with distance >= x.
Greedily select up to k coordinates.

Solution:

This problem asks us to select k points from a given set of points on the boundary of a square to maximize the minimum Manhattan distance between any two selected points.

We solve it by:

Transforming the problem into a 1D ordering around the square perimeter.
Binary searching on the possible minimum distance.
Greedy checking whether a given distance is feasible with at least k points.

Approach:

Binary Search on the answer
- The answer lies between 0 and side (max possible Manhattan dist on the boundary).
- We binary search for the maximum d such that we can pick k points with all pairwise distances ≥ d.
Flatten the square perimeter into a 1D sequence
- Points on the boundary are ordered clockwise starting from the left edge.
- This converts perimeter positions into a linear coordinate for easier traversal.
Feasibility check for a given d
- We greedily try to form the longest sequence of points where consecutive Manhattan distances are at least d.
- If the longest sequence length ≥ k, then d is feasible.
Greedy sequence building
- We maintain sequences (segments) starting at earlier points, and for each new point, we try to extend the longest possible segment ending at it, ensuring the jump distance meets d.

Let's implement this solution in PHP: 3464. Maximize the Distance Between Points on a Square

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

/**
 * Returns true if we can select k points such that the minimum Manhattan
 * distance between any two consecutive chosen points is at least d.
 *
 * @param array $ordered
 * @param int $k
 * @param int $d
 * @return bool
 */
function isValidDistance(array $ordered, int $k, int $d): bool {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Returns the ordered points on the perimeter of a square of side length side,
 * starting from left, top, right, and bottom boundaries.
 *
 * @param int $side
 * @param array $points
 * @return array
 */
function getOrderedPoints(int $side, array $points): array {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxDistance(2, [[0,2],[2,0],[2,2],[0,0]], 4) . "\n";                           // Output: 2
echo maxDistance(2, [[0,0],[1,2],[2,0],[2,2],[2,1]], 4) . "\n";                     // Output: 1
echo maxDistance(2, [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], 5) . "\n";         // Output: 1
echo maxDistance(40, [[0,14],[0,40],[32,0],[0,30],[34,40]], 4) . "\n";              // Output: 26
?>

Explanation:

Ordering the points
- Split points by which side of the square they lie on: left, top, right, bottom.
- Sort each side appropriately to get clockwise order.
- Merge them: left (bottom to top), top (left to right), right (top to bottom), bottom (right to left).
Binary search range
- low = 0, high = side.
- While low < high, test mid = (low + high + 1) / 2.
Feasibility check for distance d
- Start with the first point as a sequence of length 1.
- For each new point (x, y), try to extend all existing sequences where the distance from that sequence’s end to (x, y) ≥ d.
- Choose the longest extension.
- Track the maximum sequence length seen.
- If at any point we can form length ≥ k, return true.
Manhattan distance in 1D
- Since points are in order around the perimeter, the Manhattan distance between two points in this 1D flattened representation is simply the smaller of:
  - the direct distance along the perimeter,
  - side*4 - direct distance (going the other way around).
- The implementation uses absolute coordinate differences directly, so it works even if points wrap across the start/end.
Greedy choice
- For a candidate d, we try to maximize the number of points we can pick with gaps ≥ d without skipping too many points.
- This is like a longest path problem in a DAG where edges exist if distance ≥ d.

Complexity

Time Complexity:
- Sorting: O(n log n) where n = len(points).
- Binary search: O(log side) iterations.
- Each feasibility check: O(n²) in worst case due to linear scan over sequences.
- Total: O(n² log side).
Space Complexity: O(n) for storing ordered points and sequence data.

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

2833. Furthest Point From Origin

MD ARIFUL HAQUE — Fri, 24 Apr 2026 17:41:47 +0000

2833. Furthest Point From Origin

Difficulty: Easy

Topics: Mid Level, String, Counting, Weekly Contest 360

You are given a string moves of length n consisting only of characters 'L', 'R', and '_'. The string represents your movement on a number line starting from the origin 0.

In the iᵗʰ move, you can choose one of the following directions:

move to the left if moves[i] = 'L' or moves[i] = '_'
move to the right if moves[i] = 'R' or moves[i] = '_'

Return the distance from the origin of the furthest point you can get to after n moves.

Example 1:

Input: moves = "L_RL__R"
Output: 3
Explanation: The furthest point we can reach from the origin 0 is point -3 through the following sequence of moves "LLRLLLR".

Example 2:

Input: moves = "RLL"
Output: 5
Explanation: The furthest point we can reach from the origin 0 is point -5 through the following sequence of moves "LRLLLLL".

Example 3:

Input: moves = "_______"
Output: 7
Explanation: The furthest point we can reach from the origin 0 is point 7 through the following sequence of moves "RRRRRRR".

Example 4:

Input: moves = "R"
Output: 1

Example 5:

Input: moves = "_"
Output: 1

Constraints:

1 <= moves.length == n <= 50
moves consists only of characters 'L', 'R' and '_'.

Hint:

In an optimal answer, all occurrences of '_’ will be replaced with the same character.
Replace all characters of '_’ with the character that occurs the most.

Solution:

The goal is to find the furthest possible distance from the origin after processing a series of moves where 'L' and 'R' are fixed, and '_' can be chosen as either 'L' or 'R'. The solution calculates the net position range based on fixed moves and then uses all underscores to maximize distance in one direction.

Approach:

Count the number of 'L', 'R', and '_' in the input string.
Compute the net position after all fixed moves: net = count('R') - count('L').
The underscores can be used entirely as 'R' (to increase net position) or as 'L' (to decrease net position).
Calculate the two possible final positions:
- All underscores as 'R': maxPos = net + underscoreCount
- All underscores as 'L': minPos = net - underscoreCount
The answer is the maximum absolute value of these two positions, representing the furthest distance from origin.

Let's implement this solution in PHP: 2833. Furthest Point From Origin

<?php
/**
 * @param String $moves
 * @return Integer
 */
function furthestDistanceFromOrigin(string $moves): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo furthestDistanceFromOrigin("L_RL__R") . "\n";              // Output: 3
echo furthestDistanceFromOrigin("_R__LL_") . "\n";              // Output: 5
echo furthestDistanceFromOrigin("_______") . "\n";              // Output: 7
echo furthestDistanceFromOrigin("R") . "\n";                    // Output: 1
echo furthestDistanceFromOrigin("_") . "\n";                    // Output: 1
?>

Explanation:

Step 1 — Count moves:
- $r = substr_count($moves, 'R')
- $l = substr_count($moves, 'L')
- $underscore = substr_count($moves, '_')
- This gives us the fixed net movement and flexibility.
Step 2 — Net from fixed moves: $net = $r - $l represents the position after fixed moves only.
Step 3 — Two extreme final positions:
- If all '_' move right: $maxPos = $net + $underscore
- If all '_' move left: $minPos = $net - $underscore
Step 4 — Furthest point: The furthest distance from origin is the larger absolute value of $maxPos and $minPos.

Complexity

Time Complexity: O(n), Counting takes linear time based on string length.
Space Complexity: O(1), Only a few integer variables are used.
Algorithmic efficiency: Optimal — no sorting or extra data structures needed.

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

2615. Sum of Distances

MD ARIFUL HAQUE — Thu, 23 Apr 2026 14:35:33 +0000

2615. Sum of Distances

Difficulty: Medium

Topics: Senior, Array, Hash Table, Prefix Sum, Weekly Contest 340

You are given a 0-indexed integer array nums. There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.

Return the array arr.

Example 1:

Input: nums = [1,3,1,1,2]
Output: [5,0,3,4,0]
Explanation:
- When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5.
- When i = 1, arr[1] = 0 because there is no other index with value 3.
- When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3.
- When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4.
- When i = 4, arr[4] = 0 because there is no other index with value 2.

Example 2:

Input: nums = [0,5,3]
Output: [0,0,0]
Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.

Constraints:

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

Note: This question is the same as 2121: Intervals Between Identical Elements.

Hint:

Can we use the prefix sum here?
For each number x, collect all the indices where x occurs, and calculate the prefix sum of the array.
For each occurrence of x, the indices to the right will be regular subtraction while the indices to the left will be reversed subtraction.

Solution:

The solution computes, for each index i, the sum of absolute differences |i - j| for all j ≠ i where nums[j] == nums[i].

It groups indices by value, then uses prefix sums to efficiently calculate the total distance to all other same-valued indices in O(n) time.

Approach:

Group indices by value — create a mapping from each unique number to a list of indices where it appears.
For each group of indices (already sorted by the order they appear in nums):
- Compute the prefix sums of the indices.
- For each index pos at position j in the group:
  - Split the group into left and right parts relative to pos.
  - Use the formula:
```
arr[pos] = (pos * leftCount - leftSum) + (rightSum - pos * rightCount)
```
  where:
  - leftCount = j, rightCount = k - j - 1
  - leftSum = sum of indices to the left of pos
  - rightSum = sum of indices to the right of pos
This avoids an O(k²) per-group computation.

Let's implement this solution in PHP: 2615. Sum of Distances

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

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

Explanation:

Why grouping?

The problem only requires distances to indices with the same value. Grouping allows us to process all same-value indices together.
Why prefix sums?

If we have sorted indices [i₀, i₁, ..., iₖ₋₁] for a value, then for index iⱼ:
- Distance to all left indices = iⱼ * j - sum(i₀..iⱼ₋₁)
- Distance to all right indices = sum(iⱼ₊₁..iₖ₋₁) - iⱼ * (k - j - 1)
- Prefix sums let us compute sum(i₀..iⱼ₋₁) and sum(iⱼ₊₁..iₖ₋₁) in O(1).
Why efficient?

Each index is processed once, and prefix sums are computed in O(k) per group, so total O(n).

Complexity

Time Complexity: O(n) — We iterate through the array to group indices, then process each group with prefix sums. Each index’s distance is computed in constant time after prefix sums.
Space Complexity: O(n) — For storing the groups of indices and prefix sums.

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

2452. Words Within Two Edits of Dictionary

MD ARIFUL HAQUE — Wed, 22 Apr 2026 16:51:19 +0000

2452. Words Within Two Edits of Dictionary

Difficulty: Medium

Topics: Senior, Array, String, Trie, Biweekly Contest 90

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
- Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation: Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints:

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
All queries[i] and dictionary[j] are composed of lowercase English letters.

Hint:

Try brute-forcing the problem.
For each word in queries, try comparing to each word in dictionary.
If there is a maximum of two edit differences, the word should be present in answer.

Solution:

The problem requires identifying which words from queries can be transformed into any word from dictionary with at most two letter changes (edits). The brute-force approach compares each query word with each dictionary word, counting character mismatches, and stops early if more than two mismatches are found.

Approach:

Brute-force comparison between each query and each dictionary word.
Character-by-character mismatch counting for each pair.
Early termination if mismatch count exceeds 2.
Order preservation by processing queries in their original order.

Let's implement this solution in PHP: 2452. Words Within Two Edits of Dictionary

<?php
/**
 * @param String[] $queries
 * @param String[] $dictionary
 * @return String[]
 */
function twoEditWords(array $queries, array $dictionary): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo twoEditWords(["word","note","ants","wood"], ["wood","joke","moat"]) . "\n";    // Output: ["word","note","wood"]
echo twoEditWords(["yes"], ["not"]) . "\n";                                         // Output: []
?>

Explanation:

Step 1 — Initialize result array: An empty array $result is created to store query words that meet the condition.
Step 2 — Iterate through queries: For each $query, assume initially it’s not matched ($matched = false).
Step 3 — Compare with dictionary: Loop through $dictionary. For each $dictWord, compare characters with $query.
Step 4 — Count differences: Track $diffCount for positions where characters differ.
Step 5 — Early stop: If $diffCount > 2, break out of the inner loop for that dictionary word.
Step 6 — Match found: If $diffCount <= 2, set $matched = true and break out of the dictionary loop.
Step 7 — Add to result: If $matched, append $query to $result.
Step 8 — Return result: After processing all queries, return $result.

Complexity

Time Complexity:
- O(q . d . n) where q = number of queries, d = size of dictionary, n = length of each word.
- In worst case, each comparison checks all n characters (up to 100), and q, d ≤ 100, so at most 100 . 100 . 100 = 10⁶ operations, which is acceptable.
Space Complexity:
- O(q) for the result array (excluding input storage).
- No additional data structures proportional to input size beyond the result.

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

1722. Minimize Hamming Distance After Swap Operations

MD ARIFUL HAQUE — Tue, 21 Apr 2026 16:36:08 +0000

1722. Minimize Hamming Distance After Swap Operations

Difficulty: Medium

Topics: Staff, Array, Depth-First Search, Union-Find, Weekly Contest 223

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [aᵢ, bᵢ] indicates that you are allowed to swap the elements at index aᵢ and index bᵢ (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation:
- source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
- The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation:
- There are no allowed swaps.
- The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= aᵢ, bᵢ <= n - 1
aᵢ != bᵢ

Hint:

The source array can be imagined as a graph where each index is a node and each allowedSwaps[i] is an edge.
Nodes within the same component can be freely swapped with each other.
For each component, find the number of common elements. The elements that are not in common will contribute to the total Hamming distance.

Solution:

This problem is about minimizing the Hamming distance between two arrays by swapping elements in source using allowed swaps.

The key insight is that indices connected through allowed swaps form components where any permutation of values is possible.

Thus, within each component, we can rearrange source values freely to match as many target values as possible.

The solution uses a Union-Find (Disjoint Set Union) data structure to group indices into connected components, then counts mismatches per component.

Approach:

Union-Find (DSU) is used to group indices that are directly or indirectly connected via allowedSwaps.
For each component, collect all source and target values.
Count frequency of each value in source and target within the component.
For each value, the number of matches = min(source_count, target_count).
The Hamming distance for the component = component_size - matches.
Sum over all components to get total minimum Hamming distance.

Let's implement this solution in PHP: 1722. Minimize Hamming Distance After Swap Operations

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

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

Explanation:

Graph interpretation:
- Each index is a node, each allowed swap is an undirected edge.
- Nodes in the same connected component can be rearranged arbitrarily.
Union-Find:
- Merges indices connected by swaps.
- After processing all swaps, find(i) gives the root of the component containing i.
Group indices: Use a map from root → list of indices.
Count matches per component: Since we can permute freely, the best we can do is match as many target values as possible from the multiset of source values in that component.
Compute mismatches:
- component_size - matches gives the number of positions that cannot be fixed in that component.
- Summing over all components gives the minimum possible Hamming distance.

Complexity

Time Complexity:
- Building DSU: O(α(n) * m) where m = len(allowedSwaps) and α is inverse Ackermann (near constant).
- Grouping indices: O(n).
- Counting frequencies per component: total O(n) across all components.
- Overall: O(n + m * α(n)).
Space Complexity:
- DSU arrays: O(n).
- Component grouping: O(n).
- Frequency maps per component: total O(n) across all components.
- Overall: O(n).

Contact Links

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

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

LinkedIn
GitHub

2078. Two Furthest Houses With Different Colors

MD ARIFUL HAQUE — Mon, 20 Apr 2026 17:31:14 +0000

2078. Two Furthest Houses With Different Colors

Difficulty: Easy

Topics: Mid Level, Array, Greedy, Weekly Contest 268

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the iᵗʰ house.

Return the maximum distance between two houses with different colors.

The distance between the iᵗʰ and jᵗʰ houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation:
- In the above image, color 1 is blue, and color 6 is red.
- The furthest two houses with different colors are house 0 and house 3.
- House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
- Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation:
- In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
- The furthest two houses with different colors are house 0 and house 4.
- House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation:
- The furthest two houses with different colors are house 0 and house 1.
- House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Hint:

The constraints are small. Can you try the combination of every two houses?
Greedily, the maximum distance will come from either the pair of the leftmost house and possibly some house on the right with a different color, or the pair of the rightmost house and possibly some house on the left with a different color.

Solution:

The problem asks for the maximum distance between two houses with different colors.

A brute-force solution (checking all pairs) would be O(n²), but an O(n) greedy approach works by focusing only on the leftmost and rightmost houses.

Approach:

Observation: The maximum distance will always involve either the leftmost house (index 0) paired with the farthest house to the right that has a different color, or the rightmost house (index n-1) paired with the farthest house to the left that has a different color.
Why greedy works:
- If the leftmost and rightmost houses have different colors, the distance n-1 is already maximal.
- If they have the same color, the farthest house with a different color from the leftmost house must be somewhere on the right side, and from the rightmost house on the left side.
- The optimal distance will be one of these two candidates, because any interior pair would have a smaller span than extending to one of the ends.

Let's implement this solution in PHP: 2078. Two Furthest Houses With Different Colors

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

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

Explanation:

Case 1 – Start from leftmost house: Scan from the right end toward the left, stop at the first house with a color different from colors[0]. Compute distance and update maxDist.
Case 2 – Start from rightmost house: Scan from the left end toward the right, stop at the first house with a color different from colors[n-1]. Compute distance and update maxDist.
Why both cases are needed: The farthest different-colored house from the left end might be closer to the right end than the farthest different-colored house from the right end. We must consider both to cover the true maximum.
Return the maximum of the two candidates.

Complexity

Time Complexity: O(n) – at most two linear scans.
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

1855. Maximum Distance Between a Pair of Values

MD ARIFUL HAQUE — Sun, 19 Apr 2026 14:04:18 +0000

1855. Maximum Distance Between a Pair of Values

Difficulty: Medium

Topics: Senior, Array, Two Pointers, Binary Search, Weekly Contest 240

You are given two non-increasing 0-indexed integer arrays nums1 and nums2.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation:
- The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
- The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation:
- The valid pairs are (0,0), (0,1), and (1,1).
- The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation:
- The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
- The maximum distance is 2 with pair (2,4).

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
Both nums1 and nums2 are non-increasing.

Hint:

Since both arrays are sorted in a non-increasing way this means that for each value in the first array. We can find the farthest value smaller than it using binary search.
There is another solution using a two pointers approach since the first array is non-increasing the farthest j such that nums2[j] ≥ nums1[i] is at least as far as the farthest j such that nums2[j] ≥ nums1[i-1]

Solution:

We need to find the maximum j - i such that i <= j and nums1[i] <= nums2[j], given both arrays are non-increasing.

The solution uses a two-pointer technique to efficiently find the farthest valid j for each i, leveraging the sorted property to avoid nested loops.

Approach:

Two-pointer traversal: One pointer i for nums1, one pointer j for nums2.
Greedy expansion of j: If nums1[i] <= nums2[j], we have a valid pair, so we try to increase j to maximize distance.
Adjusting i when condition fails: If nums1[i] > nums2[j], we move i forward (since arrays are non-increasing, nums1[i] will decrease, possibly satisfying condition later).
Maintain j >= i: When moving i forward, we ensure j is at least i to keep j - i non-negative.

Let's implement this solution in PHP: 1855. Maximum Distance Between a Pair of Values

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

// Test cases
echo maxDistance([55,30,5,4,2], [100,20,10,10,5]) . "\n";           // Output: 2
echo maxDistance([2,2,2], [10,10,1]) . "\n";                        // Output: 1
echo maxDistance([30,29,19,5], [25,25,25,25,25]) . "\n";            // Output: 2
?>

Explanation:

Start with i = 0, j = 0, ans = 0.
While i < n and j < m:
- If nums1[i] <= nums2[j]:
  - It's a valid pair, so update ans = max(ans, j - i).
  - Move j forward to try to get a larger j for same i.
- Else (nums1[i] > nums2[j]):
  - Condition fails, so move i forward (since nums1[i] will decrease, may become <= later).
  - If j < i, set j = i to maintain j >= i.
Return ans.

Complexity

Time Complexity: O(n + m), Each pointer moves at most n + m times.
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

3783. Mirror Distance of an Integer

MD ARIFUL HAQUE — Sat, 18 Apr 2026 14:32:03 +0000

3783. Mirror Distance of an Integer

Difficulty: Easy

Topics: Mid Level, Math, Weekly Contest 481

You are given an integer n.

Define its mirror distance as: abs(n - reverse(n)) where reverse(n) is the integer formed by reversing the digits of n.

Return an integer denoting the mirror distance of n.

abs(x) denotes the absolute value of x.

Example 1:

Input: n = 25
Output: 27
Explanation:
- reverse(25) = 52.
- Thus, the answer is abs(25 - 52) = 27.

Example 2:

Input: n = 10
Output: 9
Explanation:
- reverse(10) = 01 which is 1.
- Thus, the answer is abs(10 - 1) = 9.

Example 3:

Input: n = 7
Output: 0
Explanation:
- reverse(7) = 7.
- Thus, the answer is abs(7 - 7) = 0.

Example 4:

Input: n = 100
Output: 99

Constraints:

1 <= n <= 10⁹

Hint:

Simulate as described

Solution:

The function calculates the mirror distance of an integer by reversing its digits, then returning the absolute difference between the original number and its reverse.

Approach:

Convert the integer to its digit-reversed form without converting to a string.
Use a loop to extract digits from the original number and build the reversed number.
Return the absolute difference between the original and reversed numbers.

Let's implement this solution in PHP: 3783. Mirror Distance of an Integer

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

// Test cases
echo mirrorDistance(25) . "\n";         // Output: 27
echo mirrorDistance(10) . "\n";         // Output: 9
echo mirrorDistance(7) . "\n";          // Output: 0
echo mirrorDistance(100) . "\n";        // Output: 99
?>

Explanation:

Reverse the digits:
- Repeatedly take the last digit of n using n % 10.
- Append it to reversed by multiplying reversed by 10 and adding the digit.
- Remove the last digit from n using integer division by 10.
- Continue until n becomes 0.
Handle leading zeros:
- The reversal process automatically discards leading zeros because they don’t contribute to the integer value (e.g., 10 → 1).
Compute mirror distance:
- Use abs(original - reversed) to get the positive difference.

Complexity

Time Complexity: O(d) where d is the number of digits in n (at most 10, since n ≤ 10⁹).
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

3761. Minimum Absolute Distance Between Mirror Pairs

MD ARIFUL HAQUE — Fri, 17 Apr 2026 16:36:06 +0000

3761. Minimum Absolute Distance Between Mirror Pairs

Difficulty: Medium

Topics: Staff, Array, Hash Table, Math, Weekly Contest 478

You are given an integer array nums.

A mirror pair is a pair of indices (i, j) such that:

0 <= i < j < nums.length, and
reverse(nums[i]) == nums[j], where reverse(x) denotes the integer formed by reversing the digits of x. Leading zeros are omitted after reversing, for example reverse(120) = 21.

Return the minimum absolute distance between the indices of any mirror pair. The absolute distance between indices i and j is abs(i - j).

If no mirror pair exists, return -1.

Example 1:

Input: nums = [12,21,45,33,54]
Output: 1
Explanation:
- The mirror pairs are:
  - (0, 1) since reverse(nums[0]) = reverse(12) = 21 = nums[1], giving an absolute distance abs(0 - 1) = 1.
  - (2, 4) since reverse(nums[2]) = reverse(45) = 54 = nums[4], giving an absolute distance abs(2 - 4) = 2.
- The minimum absolute distance among all pairs is 1.

Example 2:

Input: nums = [120,21]
Output: 1
Explanation:
- There is only one mirror pair (0, 1) since reverse(nums[0]) = reverse(120) = 21 = nums[1].
- The minimum absolute distance is 1.

Example 3:

Input: nums = [21,120]
Output: -1
Explanation: There are no mirror pairs in the array.

Example 4:

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

Constraints:

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

Hint:

Scan left to right with a hash map: for each nums[i], if the map contains key nums[i] then set ans = min(ans, i - map[nums[i]]).
Store/update the current index under key reverse(nums[i]), so future matches use the most recent index.

Solution:

This solution finds the minimum absolute distance between indices of mirror pairs in an array. A mirror pair consists of two numbers where one is the digit-reversed version of the other. The algorithm uses a single pass with a hash map to track the most recent index of each number's reverse, efficiently finding the smallest index gap in O(n) time.

Approach:

Single-pass traversal with hash map storage
Reverse number computation for each array element
Look for existing matches before storing current index
Track minimum distance by comparing current index with previously stored index of the same number
Store current index under the reversed number key for future matches

Let's implement this solution in PHP: 3761. Minimum Absolute Distance Between Mirror Pairs

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

// Test cases
echo minAbsoluteDistanceMirrorPairs([12, 21, 45, 33, 54]) . "\n";           // Output: 1
echo minAbsoluteDistanceMirrorPairs([120, 21]) . "\n";                      // Output: 1
echo minAbsoluteDistanceMirrorPairs([21, 120]) . "\n";                      // Output: -1
echo minAbsoluteDistanceMirrorPairs([1,10,100,1,10]) . "\n";                // Output: 1
?>

Explanation:

Key Insight: When scanning left to right, if we encounter a number that matches a previously stored reversed number, they form a mirror pair. The reverse of the previous number equals the current number, and vice versa.
Hash Map Strategy: Store each number's latest index under the key equal to its reverse. This ensures that when we later see a number that matches a previously stored reverse, we can calculate the distance immediately.
Distance Calculation: Since we always store the latest index for each reversed number, we minimize the distance for each potential pair. Using abs(i - j) simplifies to i - j because i is always greater than j during forward traversal.
Edge Cases:
- Numbers with trailing zeros (e.g., 120 → 21) are handled correctly by converting to integer after reversal
- Single-element arrays or arrays with no mirror pairs return -1
- Multiple occurrences of the same number are handled by overwriting the map entry, which actually helps find smaller gaps

Complexity

Time Complexity: O(n) - single pass through the array with O(1) operations per element (reversal of digits is O(log₁₀(num)) which is effectively constant as numbers ≤ 10⁹ have at most 10 digits)
Space Complexity: O(n) - in worst case, the hash map stores a unique entry for each distinct reversed number in the 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

3488. Closest Equal Element Queries

MD ARIFUL HAQUE — Thu, 16 Apr 2026 17:17:19 +0000

3488. Closest Equal Element Queries

Difficulty: Medium

Topics: Senior, Array, Hash Table, Binary Search, Weekly Contest 441

You are given a circular array nums and an array queries.

For each query i, you have to find the following:

The minimum distance between the element at index queries[i] and any other index j in the circular array, where nums[j] == nums[queries[i]]. If no such index exists, the answer for that query should be -1.

Return an array answer of the same size as queries, where answer[i] represents the result for query i.

Example 1:

Input: nums = [1,3,1,4,1,3,2], queries = [0,3,5]
Output: [2,-1,3]
Explanation:
- Query 0: The element at queries[0] = 0 is nums[0] = 1. The nearest index with the same value is 2, and the distance between them is 2.
- Query 1: The element at queries[1] = 3 is nums[3] = 4. No other index contains 4, so the result is -1.
- Query 2: The element at queries[2] = 5 is nums[5] = 3. The nearest index with the same value is 1, and the distance between them is 3 (following the circular path: 5 -> 6 -> 0 -> 1).

Example 2:

Input: nums = [1,2,3,4], queries = [0,1,2,3]
Output: [-1,-1,-1,-1]
Explanation: Each value in nums is unique, so no index shares the same value as the queried element. This results in -1 for all queries.

Example 3:

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

Constraints:

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

Hint:

Use a dictionary that maps each unique value in the array to a sorted list of its indices.
For each query, use binary search on the sorted indices list to find the nearest occurrences of the target value.

Solution:

The problem asks for the minimum circular distance between a given index and any other index containing the same value.

The solution groups indices by value, uses binary search to find neighbors in the circular array, and computes distances with wrap-around logic.

If a value appears only once, the answer is -1.

Approach:

Group indices by value using a hash map (dictionary) where keys are array values and values are sorted lists of their indices.
For each query index:
- Retrieve the sorted list of indices for its value.
- If only one index exists → answer is -1.
- Use binary search to locate the query index within its value’s index list.
- Check the previous and next indices in the circular list (wrap around using modulo).
- Compute the circular distance between the query index and each candidate.
- Take the minimum of these distances as the answer.
Return an array of answers in the same order as queries.

Let's implement this solution in PHP: 3488. Closest Equal Element Queries

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

/**
 * Binary search to find the exact position or insertion point
 *
 * @param $arr
 * @param $target
 * @return mixed
 */
function binarySearch($arr, $target): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Calculate circular distance between two indices
 *
 * @param $i
 * @param $j
 * @param $n
 * @return mixed
 */
function circularDistance($i, $j, $n): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

?>

Explanation:

Grouping indices: We traverse the array once and store each index in a list corresponding to its value. This allows quick access to all positions of a given value.
Binary search for neighbors: For a query index q, we find its position in the sorted index list. Then, the nearest other indices with the same value are the ones immediately before and after it in that list (wrapping around at ends).
Circular distance: On a circular array of length n, the distance between indices i and j is min(|i - j|, n - |i - j|).
Handling uniqueness: If a value appears only once, there is no other index to compare, so we return -1.

Complexity

Time Complexity:
- Grouping indices: O(n)
- Each query: binary search O(log m) where m is the frequency of that value
- Total: O(n + q log n) worst case, but since q ≤ n, it’s efficient.
Space Complexity: Hash map storing all indices: O(n)

Contact Links

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

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

LinkedIn
GitHub