DEV Community: MD ARIFUL HAQUE

1344. Angle Between Hands of a Clock

MD ARIFUL HAQUE — Thu, 18 Jun 2026 16:50:47 +0000

1344. Angle Between Hands of a Clock

Difficulty: Medium

Topics: Staff, Math, Biweekly Contest 19

Given two numbers, hour and minutes, return the smaller angle (in degrees) formed between the hour and the minute hand.

Answers within 10⁻⁵ of the actual value will be accepted as correct.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Constraints:

1 <= hour <= 12
0 <= minutes <= 59

Hint:

The tricky part is determining how the minute hand affects the position of the hour hand.
Calculate the angles separately then find the difference.

Solution:

We implement a direct mathematical solution to compute the smaller angle between the clock hands. By calculating each hand’s angular position independently and then taking the minimum of the absolute difference and its complement to 360°, we efficiently obtain the result in constant time.

Approach

Minute hand angle – Each minute moves the minute hand by 6° (since 360° / 60 = 6°).
Hour hand angle – Each hour moves the hour hand by 30° (since 360° / 12 = 30°), plus an additional 0.5° per minute (since 30° / 60 = 0.5°).
Normalize hour – Convert 12 to 0 because the 12‑hour dial wraps around.
Compute difference – Take the absolute angular difference.
Return smaller angle – Since two lines form two angles (θ and 360°−θ), we return the minimum.

Let's implement this solution in PHP: 1. Angle Between Hands of a Clock

<?php
/**
 * @param Integer $hour
 * @param Integer $minutes
 * @return Float
 */
function angleClock(int $hour, int $minutes): float
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo angleClock(12, 30);        // Output: 165
echo angleClock(3, 30);         // Output: 75
echo angleClock(3, 15);         // Output: 7.5
?>

Explanation:

The minute hand angle is simply minutes * 6.
The hour hand angle is (hour % 12) * 30 + minutes * 0.5, accounting for the hour hand's continuous movement.
The absolute difference |hourAngle - minuteAngle| gives one of the two angles.
The smaller angle is always min(diff, 360 - diff) because the total circle is 360°.
This works for all valid inputs (1–12 hour, 0–59 minutes) and meets the required precision (10⁻⁵).

Complexity Analysis

Time Complexity: O(1) – only a few arithmetic operations, independent of input size.
Space Complexity: O(1) – uses only a constant number of variables.

Contact Links

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

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

LinkedIn
GitHub

3614. Process String with Special Operations II

MD ARIFUL HAQUE — Wed, 17 Jun 2026 16:24:31 +0000

3614. Process String with Special Operations II

Difficulty: Hard

Topics: Senior Staff, String, Simulation, Weekly Contest 458

You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and '%'.

You are also given an integer k.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.

Return the kᵗʰ character of the final string result. If k is out of the bounds of result, return '.'.

Example 1:

Input: s = "a#b%*", k = 1
Output: "a"
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'a'`	Append `'a'`	`"a"`
1	`'#'`	Duplicate `result`	`"aa"`
2	`'b'`	Append `'b'`	`"aab"`
3	`'%'`	Reverse `result`	`"baa"`
4	`'*'`	Remove the last character	`"ba"`

The final result is "ba". The character at index k = 1 is 'a'.

Example 2:

Input: s = "cd%#*#", k = 3
Output: "d"
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'c'`	Append `'c'`	`"c"`
1	`'d'`	Append `'d'`	`"cd"`
2	`'%'`	Reverse `result`	`"dc"`
3	`'#'`	Duplicate `result`	`"dcdc"`
4	`'*'`	Remove the last character	`"dcd"`
5	`'#'`	Duplicate `result`	`"dcddcd"`

The final result is "dcddcd". The character at index k = 3 is 'd'.

Example 3:

Input: s = "z*#", k = 0
Output: "."
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'z'`	Append `'z'`	`"z"`
1	`'*'`	Remove the last character	`""`
2	`'#'`	Duplicate the string	`""`

The final result is "". Since index k = 0 is out of bounds, the output is '.'.

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters and special characters '*', '#', and '%'.
0 <= k <= 10¹⁵
The length of result after processing s will not exceed 10¹⁵.

Hint:

Track the length of the string after each operation on s.
Walk backwards through s, undoing each # by using modulus on the tracked lengths, and undoing each % by mirroring across the midpoint, to pinpoint the kᵗʰ character.

Solution:

We simulate the process in reverse to avoid constructing strings that may be up to 10¹⁵ characters long. First, we compute the length after each operation. Then, starting from the final index k, we walk backward through the operations, reversing their effects (# and %) until we identify which original letter corresponds to the desired position. This guarantees O(n) time and O(n) space.

Approach

Forward length pass
- Iterate through s once, maintaining the current length after each operation:
- Letters → increment length
- * → decrement if possible
- # → double length
- % → length unchanged
- Store the length after each step in an array.
Validate k If k is out of bounds of the final length, return ".".
Backward reduction
- Traverse s from the last operation to the first. At each step:
- Letter: If k points to the last position of the current length, return that letter. Otherwise, just move left.
- ***: No change to k; the removed character is not relevant for earlier positions.
- #**: If k is in the duplicated second half (k >= prevLength), map it to the first half by subtracting prevLength.
- %**: Reverse the index within the previous length: k = prevLength - 1 - k.
Return result If we exit the loop without finding a letter (should not happen for valid k), return ".".

Let's implement this solution in PHP: 1. Process String with Special Operations II

<?php
/**
 * @param String $s
 * @param Integer $k
 * @return String
 */
function processStr(string $s, int $k): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo processStr("a#b%*", 1);        // Output: "a"
echo processStr("cd%#*#", 3);       // Output: "d"
echo processStr("z*#", 0);          // Output: "."
?>

Explanation:

Why process backwards? Forward simulation would build enormous strings (up to 10¹⁵), which is infeasible. Backward processing lets us reduce the problem to finding which original letter generated a specific position.
Handling # (duplicate) The duplicate operation creates two identical halves. If our target k falls in the second half, we simply subtract the first half’s length to map it to the corresponding position in the first half.
Handling % (reverse) Reversal mirrors the string. The character at index k in the reversed string comes from index prevLength - 1 - k in the string before reversal. We apply that mirror transformation.
Handling * (deletion) Since we only care about the final string, a deletion removes the last character. When walking backward, that last character is irrelevant for earlier indices, so we just ignore the operation.
Handling letters When we encounter a letter appended at the end of the string, if k is exactly the last index of that current string, that letter is our answer. Otherwise, we continue backward to earlier operations.

Complexity Analysis

Time complexity: O(n), where n is the length of s — one forward pass and one backward pass.
Space complexity: O(n) — to store the length array of size 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

3612. Process String with Special Operations I

MD ARIFUL HAQUE — Tue, 16 Jun 2026 16:45:57 +0000

3612. Process String with Special Operations I

Difficulty: Medium

Topics: Senior, String, Simulation, Weekly Contest 458

You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and %.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.

Return the final string result after processing all characters in s.

Example 1:

Input: s = "a#b%*"
Output: "ba"
Explanation:

i s[i] Operation Current result

0 'a' Append 'a' "a"

1 '#' Duplicate result "aa"

2 'b' Append 'b' "aab"

3 '%' Reverse result "baa"

4 '*' Remove the last character "ba"
- Thus, the final result is "ba".

Example 2:

Input: s = "z*#"
Output: ""
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'z'`	Append `'z'`	`"z"`
1	`'*'`	Remove the last character	`""`
2	`'#'`	Duplicate the string	`""`

Thus, the final result is "".

Constraints:

1 <= s.length <= 20
s consists of only lowercase English letters and special characters *, #, and %.

Hint:

Simulate as described

Solution:

The problem requires simulating a string transformation where regular letters are appended, and special characters (*, #, %) trigger specific operations—removal, duplication, or reversal of the current result. Since constraints are small (len ≤ 20), a direct left‑to‑right simulation using string operations is straightforward and efficient.

Approach

Linear Scan: Iterate through the input string from left to right, applying operations as defined.
Use PHP String Functions:
- .= for appending letters.
- substr($result, 0, -1) for safe removal of the last character.
- $result .= $result for duplication.
- strrev() for reversal.
Edge Cases:
- * on empty string does nothing.
- # on empty string stays empty.
- % on empty string stays empty.
No Extra Data Structures: Since only the final string is needed, maintain a single string variable.

Let's implement this solution in PHP: 1. Process String with Special Operations I

<?php
/**
 * @param String $s
 * @return String
 */
function processStr(string $s): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo processStr("a#b%*");       // Output: "ba"
echo processStr("z*#");         // Output: ""
?>

Explanation:

Initialize $result as an empty string to hold the output.
Loop through each character $char in the input string $s.
If $char is a lowercase letter, append it directly to $result.
If $char is '*':
- Check if $result is not empty.
- If yes, remove its last character using substr().
If $char is '#':
- Duplicate the current $result by appending a copy of itself ($result .= $result).
If $char is '%':
- Reverse $result using strrev().
After the loop, return the final $result.

Complexity Analysis

Time Complexity: O(n × m) in the worst case, where n is the length of s and m is the length of result.
- Each append, removal, duplication, and reversal takes O(m) time in PHP due to string copying.
- With n ≤ 20, this is negligible.
Space Complexity: O(m), where m is the length of the final 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

2095. Delete the Middle Node of a Linked List

MD ARIFUL HAQUE — Mon, 15 Jun 2026 17:56:23 +0000

2095. Delete the Middle Node of a Linked List

Difficulty: Medium

Topics: Senior, Linked List, Two Pointers, Weekly Contest 270

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋ᵗʰ node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
- The above figure represents the given linked list. The indices of the nodes are written below.
- Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
- We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
- The above figure represents the given linked list.
- For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
- The above figure represents the given linked list.
- For n = 2, node 1 with value 1 is the middle node, which is marked in red.
- Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

The number of nodes in the list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Hint:

If a point with a speed s moves n units in a given time, a point with speed 2 * s will move 2 * n units at the same time. Can you use this to find the middle node of a linked list?
If you are given the middle node, the node before it, and the node after it, how can you modify the linked list?

Similar Questions:

Solution:

This problem requires removing the middle node of a singly linked list, where the middle is defined as the ⌊n / 2⌋-th node using 0-based indexing.

The solution uses the two-pointer (slow & fast) technique to locate the node before the middle in one pass, then bypasses the middle node to delete it.

Approach:

Two-pointer traversal:
- slow moves one step at a time, fast moves two steps.
- By the time fast reaches the end, slow is at the middle node.
Tracking previous node:
- Keep a prev pointer to remember the node before slow.
- This allows linking prev to slow->next to skip the middle node.
Edge case handling:
- If the list has only one node, return null (since removing it leaves an empty list).

Let's implement this solution in PHP: 2095. Delete the Middle Node of a Linked List

<?php
/**
 * @param ListNode $head
 * @return ListNode
 */
function deleteMiddle(ListNode $head): ?ListNode
{
    // If there's only one node, return null
    if ($head->next == null) {
        return null;
    }

    $slow = $head;
    $fast = $head;
    $prev = null;

    // Move fast twice as fast as slow
    while ($fast !== null && $fast->next !== null) {
        $prev = $slow;
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    // $slow is the middle node, $prev is the node before it
    $prev->next = $slow->next;

    return $head;
}

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

Explanation:

Initialization:
- slow = head, fast = head, prev = null.
- Check for the single-node case: if head->next == null, return null.
Finding the middle:
- Loop while fast != null && fast->next != null.
- Update prev = slow, then move slow = slow->next, fast = fast->next->next.
- At loop end, slow is exactly the middle node, prev is the node before it.
Deletion:
- Set prev->next = slow->next to bypass the middle node.
- Return head (the original head of the modified list).

Complexity

Time Complexity: O(n), Single pass through the list to find and delete the middle node.
Space Complexity: O(1), Only a constant amount of extra space (three pointers).

2130. Maximum Twin Sum of a Linked List

MD ARIFUL HAQUE — Sun, 14 Jun 2026 15:01:43 +0000

2130. Maximum Twin Sum of a Linked List

Difficulty: Medium

Topics: Senior, Linked List, Two Pointers, Stack, Biweekly Contest 69

In a linked list of size n, where n is even, the iᵗʰ node (0-indexed) of the linked list is known as the twin of the (n-1-i)ᵗʰ node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
- Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
- There are no other nodes with twins in the linked list.
- Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
- The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
- Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation: There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Hint:

How can "reversing" a part of the linked list help find the answer?
We know that the nodes of the first half are twins of nodes in the second half, so try dividing the linked list in half and reverse the second half.
How can two pointers be used to find every twin sum optimally?
Use two different pointers pointing to the first nodes of the two halves of the linked list. The second pointer will point to the first node of the reversed half, which is the (n-1-i)ᵗʰ node in the original linked list. By moving both pointers forward at the same time, we find all twin sums.

Solution:

We have a singly linked list with even length n.
For each node at index i (0‑based), its twin is the node at index n-1-i.
Twin sum = node.val + twin.val.
Goal: Find the maximum twin sum.

Approach:

Step 1 — Understand the twin pairing

Because the list length is even, the first half is paired with the second half in reverse order:

Index 0 pairs with n-1
Index 1 pairs with n-2
...
Index n/2 - 1 pairs with n/2

This is symmetric.

Step 2 — Efficient approach

We don’t want to traverse the list repeatedly for each pair.

The optimal way:

Find the middle of the list (using slow & fast pointers). This gives us the start of the second half.
Reverse the second half of the list. Then, the first node of the reversed second half corresponds to the last node of the original list.
Traverse both halves together and compute twin sums.

Step 3 — Why reverse the second half?

Without reversal, to access the twin of the first node, we’d have to go to the end — O(n) per pair.
After reversal, the twin of the first node becomes the first node of the reversed half, so we can just move pointers forward in parallel.

Step 4 — Steps in detail

Find the middle node (starting point of the second half).
Reverse the second half of the list.
Initialize a pointer to the start of the first half, and another to the start of the reversed second half.
Iterate while the second half pointer is not null (this will automatically cover all pairs exactly once).
Compute sum, track the max.

Step 5 — Edge cases

Minimum length 2 → only one pair.
Maximum length 100,000 → algorithm must be O(n) time, O(1) extra space (other than recursion stack, but we’ll do iterative reversal).

Let's implement this solution in PHP: 2130. Maximum Twin Sum of a Linked List

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

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

Explanation:

Finding the middle: slow moves one step, fast moves two steps. When fast reaches the end, slow is at the start of the second half.
Reversing the second half: Standard iterative reversal. We don’t need the original order of the second half anymore.
Computing sums:
- first starts from head, second starts from the reversed head.
- They naturally align to give twin sums in order.

Complexity

Time Complexity: O(n), one pass to find middle, one pass to reverse, one pass to compute sums.
Space Complexity: O(1), only a few pointers.

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

3838. Weighted Word Mapping

MD ARIFUL HAQUE — Sat, 13 Jun 2026 17:53:33 +0000

3838. Weighted Word Mapping

Difficulty: Easy

Topics: Mid Level, Array, String, Simulation, Biweekly Contest 176

You are given an array of strings words, where each string represents a word containing lowercase English letters.

You are also given an integer array weights of length 26, where weights[i] represents the weight of the iᵗʰ lowercase English letter.

The weight of a word is defined as the sum of the weights of its characters.

For each word, take its weight modulo 26 and map the result to a lowercase English letter using reverse alphabetical order (0 -> 'z', 1 -> 'y', ..., 25 -> 'a').

Return a string formed by concatenating the mapped characters for all words in order.

Example 1:

Input: words = ["abcd","def","xyz"], weights = [5,3,12,14,1,2,3,2,10,6,6,9,7,8,7,10,8,9,6,9,9,8,3,7,7,2]
Output: "rij"
Explanation:
- The weight of "abcd" is 5 + 3 + 12 + 14 = 34. The result modulo 26 is 34 % 26 = 8, which maps to 'r'.
- The weight of "def" is 14 + 1 + 2 = 17. The result modulo 26 is 17 % 26 = 17, which maps to 'i'.
- The weight of "xyz" is 7 + 7 + 2 = 16. The result modulo 26 is 16 % 26 = 16, which maps to 'j'.
- Thus, the string formed by concatenating the mapped characters is "rij".

Example 2:

Input: words = ["a","b","c"], weights = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Output: "yyy"
Explanation:
- Each word has weight 1. The result modulo 26 is 1 % 26 = 1, which maps to 'y'.
- Thus, the string formed by concatenating the mapped characters is "yyy".

Example 3:

Input: words = ["abcd"], weights = [7,5,3,4,3,5,4,9,4,2,2,7,10,2,5,10,6,1,2,2,4,1,3,4,4,5]
Output: "g"
Explanation:
- The weight of "abcd" is 7 + 5 + 3 + 4 = 19. The result modulo 26 is 19 % 26 = 19, which maps to 'g'.
- Thus, the string formed by concatenating the mapped characters is "g".

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 10
weights.length == 26
1 <= weights[i] <= 100
words[i] consists of lowercase English letters.

Hint:

For each word, sum character weights using weights[c - 'a']
Take the sum modulo 26
Map the value to a character using reverse order: char = 'z' - value
Append all mapped characters in order to form the result string

Solution:

This solution computes the weighted sum of characters for each word using a given letter-weight mapping, reduces the sum modulo 26, then maps the result to a lowercase letter in reverse alphabetical order (0 → 'z', 1 → 'y', …). The mapped letters are concatenated to form the final output string.

Approach:

Loop through each word in the input array.
For each character in a word, find its corresponding weight using the weights array.
Sum the weights to get the total word weight.
Apply modulo 26 to the sum.
Map the result to a letter using the formula: chr(ord('z') - modulo_value).
Append this letter to the result string.
Return the result string after processing all words.

Let's implement this solution in PHP: 3838. Weighted Word Mapping

<?php
/**
 * @param String[] $words
 * @param Integer[] $weights
 * @return String
 */
function mapWordWeights(array $words, array $weights): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo mapWordWeights(["abcd","def","xyz"], [5,3,12,14,1,2,3,2,10,6,6,9,7,8,7,10,8,9,6,9,9,8,3,7,7,2]) . "\n";        // Output: "rij"
echo mapWordWeights(["a","b","c"], [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]) . "\n";                   // Output: "yyy"
echo mapWordWeights(["abcd"], [7,5,3,4,3,5,4,9,4,2,2,7,10,2,5,10,6,1,2,2,4,1,3,4,4,5]) . "\n";                      // Output: "g"
?>

Explanation:

The weight of a word is the sum of weights of its characters (where weights[0] corresponds to 'a', weights[1] to 'b', etc.).
sum % 26 ensures the result stays in the range 0–25.
The mapping 0 → 'z', 1 → 'y', … is achieved by subtracting the modulo value from ord('z').
The example "abcd" with weights [5,3,12,14] gives sum 34, 34 % 26 = 8, 'z' - 8 = 'r'.
The process repeats for each word, concatenating results in order.

Complexity

Time Complexity: O(N × L), where N = number of words, L = average word length. Each character is processed once.
Space Complexity: O(N), for the result string, ignoring input storage. Constant extra space is used for computation.

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

3559. Number of Ways to Assign Edge Weights II

MD ARIFUL HAQUE — Fri, 12 Jun 2026 17:01:19 +0000

3559. Number of Ways to Assign Edge Weights II

Difficulty: Hard

Topics: Senior Staff, Array, Math, Dynamic Programming, Bit Manipulation, Tree, Depth-First Search, Biweekly Contest 157

There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1. The tree is represented by a 2D integer array edges of length n - 1, where edges[i] = [uᵢ, vᵢ] indicates that there is an edge between nodes uᵢ and vᵢ.

Initially, all edges have a weight of 0. You must assign each edge a weight of either 1 or 2.

The cost of a path between any two nodes u and v is the total weight of all edges in the path connecting them.

You are given a 2D integer array queries. For each queries[i] = [uᵢ, vᵢ], determine the number of ways to assign weights to edges in the path such that the cost of the path between uᵢ and vᵢ is odd.

Return an array answer, where answer[i] is the number of valid assignments for queries[i].

Since the answer may be large, apply modulo 10⁹ + 7 to each answer[i].

Note: For each query, disregard all edges not in the path between node uᵢ and vᵢ.

Example 1:

Input: edges = [[1,2]], queries = [[1,1],[1,2]]
Output: [0,1]
Explanation:
- Query [1,1]: The path from Node 1 to itself consists of no edges, so the cost is 0. Thus, the number of valid assignments is 0.
- Query [1,2]: The path from Node 1 to Node 2 consists of one edge (1 → 2). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.

Example 2:

Input: edges = [[1,2],[1,3],[3,4],[3,5]], queries = [[1,4],[3,4],[2,5]]
Output: [2,1,4]
Explanation:
- Query [1,4]: The path from Node 1 to Node 4 consists of two edges (1 → 3 and 3 → 4). Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.
- Query [3,4]: The path from Node 3 to Node 4 consists of one edge (3 → 4). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
- Query [2,5]: The path from Node 2 to Node 5 consists of three edges (2 → 1, 1 → 3, and 3 → 5). Assigning (1,2,2), (2,1,2), (2,2,1), or (1,1,1) makes the cost odd. Thus, the number of valid assignments is 4.

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i] == [uᵢ, vᵢ]
1 <= queries.length <= 10⁵
queries[i] == [uᵢ, vᵢ]
1 <= uᵢ, vᵢ <= n
edges represents a valid tree.

Hint:

Dynamic programming with states chainLength and sumParity.
Use Lowest Common Ancestor to find the distance between any two nodes quickly in O(logn).

Solution:

The problem asks: given a tree where each edge can be weighted 1 or 2, for each query (u, v), count the number of weight assignments to the edges only on the path from u to v such that the total cost of that path is odd.

The key observation is that if a path has k edges, then each edge contributes either 1 or 2 to the sum. The sum is odd if the number of edges with weight 1 is odd. So, for k edges, the number of ways to choose an odd number of them to be 1 is:

If k > 0, the number of ways = 2⁽ᵏ⁻¹⁾.
If k = 0 (u == v), the answer is 0.

Thus, the problem reduces to:

Find the distance k (number of edges) between u and v.
If k == 0, answer 0.
Else, answer 2⁽ᵏ⁻¹⁾ mod (10⁹+7).

We use LCA (Lowest Common Ancestor) to find the distance efficiently.

Approach:

Observation For a path with k edges, there are 2ᵏ total assignments. Exactly half of them (if k>0) have an odd sum because flipping any one weight changes parity. So count = 2⁽ᵏ⁻¹⁾.
Distance in tree Distance between u and v in a tree = depth[u] + depth[v] - 2*depth[lca(u,v)].
LCA using binary lifting Preprocess parents up to log(n) levels so that LCA queries are O(log n).
Power modulo Compute 2⁽ᵏ⁻¹⁾ mod MOD using fast exponentiation.
Special case If u == v, distance = 0, answer = 0.

Let's implement this solution in PHP: 3559. Number of Ways to Assign Edge Weights II

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

/**
 * @param $u
 * @param $p
 * @param $graph
 * @param $parent
 * @param $depth
 * @param $d
 * @return void
 */
private function dfs($u, $p, &$graph, &$parent, &$depth, $d): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $u
 * @param $v
 * @param $parent
 * @param $depth
 * @param $LOG
 * @return mixed
 */
function lca($u, $v, &$parent, &$depth, $LOG): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $x
 * @param $n
 * @return int
 */
function modPow($x, $n): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation:

DFS preprocessing
- First DFS sets depth of each node and immediate parent.
- Then build binary lifting table: parent[k][v] = 2ᵏ-th ancestor of v.
LCA function
- Step 1: Bring both nodes to same depth.
- Step 2: If they are the same, return.
- Step 3: Lift both up together until just below LCA, then return parent.
Answer per query Compute distance dist. If dist == 0, output 0. Else output 2⁽ᵈᶦˢᵗ⁻¹⁾ mod MOD.
ModPow Recursive modular exponentiation ensures result fits in modulo space.

Complexity

Time Complexity:
- Preprocessing DFS: O(n)
- Binary lifting table: O(n log n)
- Each query: O(log n)
- Total: O(n log n + q log n) → Efficient for n, q ≤ 1e5.
Space Complexity:
- O(n log n) for binary lifting table
- O(n) for depth and adjacency list

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

3691. Maximum Total Subarray Value II

MD ARIFUL HAQUE — Wed, 10 Jun 2026 16:00:13 +0000

3691. Maximum Total Subarray Value II

Difficulty: Hard

Topics: Principal, Array, Greedy, Segment Tree, Heap (Priority Queue), Weekly Contest 468

You are given an integer array nums of length n and an integer k.

You must select exactly k distinct subarrays¹ nums[l..r] of nums. Subarrays may overlap, but the exact same subarray (same l and r) cannot be chosen more than once.

The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).

The total value is the sum of the values of all chosen subarrays.

Return the maximum possible total value you can achieve.

Example 1:

Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
- One optimal approach is:
  - Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
  - Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.
- Adding these gives 2 + 2 = 4.

Example 2:

Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
- One optimal approach is:
  - Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
  - Choose nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
  - Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.
- Adding these gives 4 + 4 + 4 = 12.

Constraints:

1 <= n == nums.length <= 5 * 10⁴
0 <= nums[i] <= 10⁹
1 <= k <= min(10⁵, n * (n + 1) / 2)

Hint:

For fixed l, the sequence v(l,r)=max(nums[l..r])−min(nums[l..r]) is non-increasing as r moves left.
Build RMQs (sparse tables) for range max/min so each v(l,r) is queryable in O(1).
Use a max-heap with v(l,n-1) for all l; pop the largest k times, and after popping an entry from (l,r) push (l,r-1) if r>l.

Solution:

This solution finds the maximum possible sum of the values of exactly k distinct subarrays, where a subarray’s value is max - min.

The approach uses a max-heap to always pick the largest-value subarray remaining, and for each picked subarray (l, r), it inserts the next smaller subarray (l, r-1) into the heap (if possible).

A sparse table enables O(1) range maximum/minimum queries to compute subarray values efficiently.

Approach:

Sparse Table for RMQ: Precompute logs and build sparse tables for both max and min over the array to answer range max/min in O(1).
Heap-based Greedy Selection: Start with all subarrays ending at the last index: (0, n-1), (1, n-1), …, (n-1, n-1), and push their values into a max-heap.
Pop and Push
- Extract the largest-value subarray from the heap, add its value to the total, and push the subarray (l, r-1) back if r > l.
- This ensures we always consider the next best smaller subarray starting at the same l.
Repeat k times
- Perform exactly k extractions (or until heap is empty, though k is guaranteed valid).
- The heap contains at most n elements at any time.

Let's implement this solution in PHP: 3691. Maximum Total Subarray Value II

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

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

Explanation:

Why greedy works
- The sequence value(l, r) for a fixed l is non-increasing as r decreases.
- Therefore, the best global choice always comes from the largest remaining subarray, and shrinking it by one index yields the next best for that start index.
Why O(1) RMQ is needed
- Without fast range queries, calculating each value(l, r) would be O(n) and inefficient.
- Sparse table gives O(1) query after O(n log n) preprocessing.
Heap management
- Only n initial entries are pushed. After each extraction, at most one new entry is pushed.
- Total heap operations: O((n + k) log n).
Handling duplicates
- The heap stores distinct subarrays (l, r), so same (l, r) cannot be chosen twice.
- Pushing (l, r-1) after popping (l, r) ensures all subarrays are considered uniquely.

Complexity

Time Complexity:
- Sparse table preprocessing: O(n log n)
- Heap operations: O((n + k) log n)
- Total: O((n + k) log n)
Space Complexity:
- Sparse tables: O(n log n)
- Heap: O(n)
- Total: O(n log n)

Contact Links

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

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

LinkedIn
GitHub

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

3689. Maximum Total Subarray Value I

MD ARIFUL HAQUE — Tue, 09 Jun 2026 14:27:12 +0000

3689. Maximum Total Subarray Value I

Difficulty: Medium

Topics: Senior, Array, Greedy, Weekly Contest 468

You are given an integer array nums of length n and an integer k.

You need to choose exactly k non-empty subarrays¹ nums[l..r] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once.

The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).

The total value is the sum of the values of all chosen subarrays.

Return the maximum possible total value you can achieve.

Example 1:

Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
- One optimal approach is:
  - Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
  - Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.
- Adding these gives 2 + 2 = 4.

Example 2:

Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
- One optimal approach is:
- Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
- Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
- Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.
- Adding these gives 4 + 4 + 4 = 12.

Example 3:

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

Example 4:

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

Constraints:

1 <= n == nums.length <= 5 * 10⁴
0 <= nums[i] <= 10⁹
1 <= k <= 10⁵

Hint:

Choose the whole subarray k times.

Solution:

The problem asks for the maximum total value achievable by choosing exactly k non-empty subarrays (possibly overlapping or identical) from the array, where a subarray's value is defined as max(subarray) - min(subarray). The key insight is that the maximum possible value for any subarray is the difference between the global maximum and global minimum of the entire array. Since subarrays can be repeated, the optimal strategy is to repeatedly pick the whole array (or any subarray that spans the global max and min) k times, giving a total value of k * (global_max - global_min).

Approach:

Observation: The value of any subarray cannot exceed max(nums) - min(nums) because the maximum and minimum of any subarray are bounded by the global max and min of nums.
Achievability: The whole array itself achieves exactly global_max - global_min.
Repetition: Since subarrays can be chosen more than once (including the exact same subarray), we can simply pick the whole array k times.
Result: Therefore, the maximum total value is k * (global_max - global_min).

Let's implement this solution in PHP: 3689. Maximum Total Subarray Value I

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

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

Explanation:

The value of a subarray is max - min. The maximum possible max is the global maximum, and the minimum possible min is the global minimum. Hence, no subarray can have a value greater than global_max - global_min.
The entire array nums[0..n-1] has exactly global_max - global_min as its value.
Because we can choose the same subarray multiple times, we simply choose the entire array k times.
Thus, the maximum total value is k * (global_max - global_min).

Complexity

Time Complexity: O(n) — one pass to find the min and max of the array.
Space Complexity: O(1) — only a few variables are used.

Contact Links

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

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

LinkedIn
GitHub

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

2574. Left and Right Sum Differences

MD ARIFUL HAQUE — Sat, 06 Jun 2026 17:55:55 +0000

2574. Left and Right Sum Differences

Difficulty: Easy

Topics: Mid Level, Array, Prefix Sum, Weekly Contest 334

You are given a 0-indexed integer array nums of size n.

Define two arrays leftSum and rightSum where:

leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.

Return an integer array answer of size n where answer[i] = |leftSum[i] - rightSum[i]|.

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation:
- The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
- The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation:
- The array leftSum is [0] and the array rightSum is [0].
- The array answer is [|0 - 0|] = [0].

Constraints:

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

Hint:

For each index i, maintain two variables leftSum and rightSum.
Iterate on the range j: [0 … i - 1] and add nums[j] to the leftSum and similarly iterate on the range j: [i + 1 … nums.length - 1] and add nums[j] to the rightSum.

Similar Questions:

Solution:

The solution computes the absolute difference between the sum of elements to the left and the sum of elements to the right for each index in the array. It uses prefix and suffix sums to achieve this efficiently without nested loops.

Approach:

Use prefix sums to calculate leftSum[i] as the sum of all elements before index i.
Use suffix sums to calculate rightSum[i] as the sum of all elements after index i.
For each index i, compute the absolute difference between leftSum[i] and rightSum[i].

Let's implement this solution in PHP: 2574. Left and Right Sum Differences

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

// Test cases
echo leftRightDifference([10,4,8,3]) . "\n";        // Output: [15,1,11,22]
echo leftRightDifference([1]) . "\n";               // Output: [0]
?>

Explanation:

Create arrays leftSum and rightSum of the same length as nums, initialized to 0.
First pass from left to right:
- leftSum[i] = leftSum[i-1] + nums[i-1]
- This accumulates sums of elements before the current index.
Second pass from right to left:
- rightSum[i] = rightSum[i+1] + nums[i+1]
- This accumulates sums of elements after the current index.
Third pass through indices:
- Compute answer[i] = |leftSum[i] - rightSum[i]|
Return the answer array.

Complexity

Time Complexity: O(n) — each element is processed three times (once for left sum, once for right sum, once for answer).
Space Complexity: O(n) — two extra arrays of size n are used for left and right 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

3753. Total Waviness of Numbers in Range II

MD ARIFUL HAQUE — Fri, 05 Jun 2026 15:48:08 +0000

3753. Total Waviness of Numbers in Range II

Difficulty: Hard

Topics: Senior Staff, Math, Dynamic Programming, Biweekly Contest 170

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130
Output: 3
Explanation:
- In the range [120, 130]:
- 120: middle digit 2 is a peak, waviness = 1.
- 121: middle digit 2 is a peak, waviness = 1.
- 130: middle digit 3 is a peak, waviness = 1.
- All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202
Output: 3
Explanation:
- In the range [198, 202]:
  - 198: middle digit 9 is a peak, waviness = 1.
  - 201: middle digit 0 is a valley, waviness = 1.
  - 202: middle digit 0 is a valley, waviness = 1.
  - All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848
Output: 2
Explanation: Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Example 4:

Input: num1 = 63, num2 = 101
Output: 1

Constraints:

1 <= num1 <= num2 <= 10¹⁵

Hint:

Use digit dynamic programming
Build a digit-DP state (position, tight, lastDigit, secondLastDigit)

Solution:

This solution calculates the total sum of waviness for all numbers in a given inclusive range [num1, num2].

Waviness is defined as the count of peaks and valleys in the digit sequence of a number (excluding first and last digits).

The approach uses digit dynamic programming (digit DP) to efficiently process ranges up to 10^15, avoiding brute-force enumeration.

The function totalWaviness(num1, num2) computes the result as solve(num2) - solve(num1 - 1), where solve(n) returns the total waviness for [1, n].

Approach:

Digit DP – We recursively process digits from most significant to least significant.
State – (position, tight, started, secondLast, last) tracks:
- current index in the number
- whether we are bound by the prefix of n (tight)
- whether we have started placing non-leading digits (started)
- the previous two digits (secondLast, last) to detect peaks/valleys
Memoization – For !tight states, we store results to reuse across different numbers.
Contribution counting – When we place a new digit:
- If we have at least 3 digits so far (secondLast !== -1), we check if the middle digit (last) is a peak or valley.
- If yes, we add 1 × (number of valid suffixes) to the waviness sum.
Base case – When all digits are placed (pos == len), return count = 1, waviness = 0.
Range subtraction – totalWaviness(num1, num2) = solve(num2) - solve(num1 - 1).

Let's implement this solution in PHP: 3753. Total Waviness of Numbers in Range II

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function totalWaviness(int $num1, int $num2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param int $n
 * @return int|mixed
 */
function sumWavinessUpTo(int $n): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo totalWaviness(120, 130) . "\n";            // Output: 3
echo totalWaviness(198, 202) . "\n";            // Output: 3
echo totalWaviness(4848, 4848) . "\n";          // Output: 2
echo totalWaviness(63, 101) . "\n";             // Output: 1
?>

Explanation:

Peak & Valley definition
- A digit d is a peak if prev < d > next.
- A digit d is a valley if prev > d < next.
- First and last digits are ignored.
Digit DP state We need the last two digits to know if the current position (as the second last) is a peak/valley when the next digit is chosen.
Transition
- At position pos, we try digits 0..limit:
  - If not started and digit is 0, stay in not started.
  - If not started and digit > 0, start the number, store it as last, secondLast = -1.
  - If started, compute if last (which is the middle digit between secondLast and digit) is peak/valley, and add to waviness accordingly.
Memoization The result for a state (pos, started, secondLast, last) with tight = 0 can be reused across different higher prefixes.
Complexity State count is O(len × 2 × 10 × 10) with len ≤ 16 → very fast.

Complexity

Time Complexity: O(len × 2 × 10 × 10 × 10) ≈ O(16 × 1000) = O(16000) per solve(n), which is trivial for input sizes up to 10¹⁵.
Space Complexity: O(len × 2 × 10 × 10) for memoization table.

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

3751. Total Waviness of Numbers in Range I

MD ARIFUL HAQUE — Thu, 04 Jun 2026 17:55:07 +0000

3751. Total Waviness of Numbers in Range I

Difficulty: Medium

Topics: Senior, Math, Dynamic Programming, Enumeration, Biweekly Contest 170

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130
Output: 3
Explanation:
- In the range [120, 130]:
- 120: middle digit 2 is a peak, waviness = 1.
- 121: middle digit 2 is a peak, waviness = 1.
- 130: middle digit 3 is a peak, waviness = 1.
- All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202
Output: 3
Explanation:
- In the range [198, 202]:
- 198: middle digit 9 is a peak, waviness = 1.
- 201: middle digit 0 is a valley, waviness = 1.
- 202: middle digit 0 is a valley, waviness = 1.
- All other numbers in the range have a waviness of 0.Thus,
- total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848
Output: 2
Explanation: Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Constraints:

1 <= num1 <= num2 <= 10⁵

Hint:

Use bruteforce

Solution:

We compute the waviness of each number in the inclusive range from num1 to num2 and sum the results. Waviness counts internal digits that are strictly greater than both neighbors (peaks) or strictly less than both neighbors (valleys). Numbers with fewer than 3 digits automatically have 0 waviness.

Approach:

Iterate through every number in the range.
Convert each number to a string to access its digits.
Skip numbers with fewer than 3 digits.
Check each interior digit (excluding first and last) for peak or valley conditions.
Sum the waviness for the number.
Accumulate the total over all numbers.

Let's implement this solution in PHP: 3751. Total Waviness of Numbers in Range I

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function totalWaviness(int $num1, int $num2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $num
 * @return int
 */
function wavinessOfNumber($num): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo totalWaviness(120, 130) . "\n";            // Output: 3
echo totalWaviness(198, 202) . "\n";            // Output: 3
echo totalWaviness(4848, 4848) . "\n";          // Output: 2
?>

Explanation:

Brute force enumeration is feasible here because the range is at most 100,000 numbers.
wavinessOfNumber() handles the logic for a single number:
- Split digits into an array.
- Loop from index 1 to len-2 (inclusive) to avoid first and last digits.
- Compare each digit with its immediate left and right neighbors.
- Increment waviness if the digit is a peak (mid > left && mid > right) or a valley (mid < left && mid < right).
The main function totalWaviness() loops from num1 to num2, calling the helper and adding to the total.

Complexity

Time Complexity: O(N * D) where N = range size (num2 - num1 + 1) and D = max digit length (≤ 6 for numbers ≤ 10⁵).
- Here, D is small, so effectively O(N).
Space Complexity: O(D), as only a few variables are used.

Contact Links

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

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

LinkedIn
GitHub