LeetCode Problem 3751

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Enumeration

Solution

LeetCode 3751 - Total Waviness of Numbers in Range I

Problem Understanding

This problem asks us to compute the total waviness of every integer in an inclusive range [num1, num2].

For a single number, waviness is defined as the number of digits that are either peaks or valleys.

A digit is a peak if it is strictly larger than both adjacent digits. A digit is a valley if it is strictly smaller than both adjacent digits. Since a digit must have both a left neighbor and a right neighbor to be evaluated, the first and last digits of a number can never contribute to waviness.

For example, in the number 4848:

• The second digit 8 is greater than 4 and 4, so it is a peak.
• The third digit 4 is smaller than 8 and 8, so it is a valley.

Therefore the waviness is 2.

The input consists of two integers defining an inclusive range. The output is the sum of waviness values across every number in that range.

The constraint is:

1 <= num1 <= num2 <= 100000

This upper bound is quite small. There are at most 100000 numbers to examine, and each number contains at most 6 digits because 100000 is the largest possible value.

This observation is important because it means a direct enumeration solution is already efficient enough.

Several edge cases deserve attention:

• Numbers with fewer than three digits always contribute 0.
• Equal neighboring digits never form peaks or valleys because the comparison must be strict.
• The range may contain a single number.
• The upper bound 100000 has six digits, so implementations must correctly handle varying digit lengths.
• Peaks and valleys can occur multiple times within the same number.

Approaches

Brute Force

The most direct solution is to iterate through every number in the range.

For each number:

1. Convert it into its digit representation.
2. If it contains fewer than three digits, its waviness is zero.
3. For every interior digit, compare it with its immediate neighbors.
4. Count one waviness point whenever the digit is strictly larger than both neighbors or strictly smaller than both neighbors.
5. Add that count to the global answer.

This approach is clearly correct because it follows the definition of waviness exactly.

Given that there are at most 100000 numbers and each number contains at most 6 digits, the total work is extremely small.

Optimal Observation

Although the problem is tagged with dynamic programming and enumeration, the actual constraints make a full digit-DP solution unnecessary.

The key observation is that:

• Maximum range size is 100000.
• Maximum digit count is 6.

Therefore a complete scan of the range performs at most roughly:

100000 × 6 = 600000

digit operations.

This is easily fast enough, making straightforward enumeration the most practical and simplest solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((num2 - num1 + 1) × D)	O(D)	Directly computes waviness for every number
Optimal	O((num2 - num1 + 1) × D)	O(D)	Same approach, constraints are small enough that enumeration is optimal in practice

Here D is the number of digits, at most 6.

Algorithm Walkthrough

1. Initialize a variable total to store the accumulated waviness across the range.
2. Iterate through every integer value from num1 to num2 inclusive.
3. Convert the current number into a string of digits.
4. If the digit count is less than 3, skip further processing because such numbers cannot contain peaks or valleys.
5. For each interior position i from 1 to len(digits) - 2, retrieve:

• left = digits[i - 1]
• current = digits[i]
• right = digits[i + 1]

6. Check whether current is a peak:

• current > left
• current > right

7. Check whether current is a valley:

• current < left
• current < right

8. If either condition is true, increment the total waviness count.
9. After processing all numbers, return total.

Why it Works

The algorithm examines every digit that is eligible to be a peak or valley. For each interior digit, it applies exactly the same strict comparison rules given in the problem statement. Every valid peak or valley contributes one count, and no invalid digit is counted. Since every number in the range is processed exactly once, the final sum equals the total waviness of all numbers in the range.

Python Solution

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        total = 0

        for value in range(num1, num2 + 1):
            digits = str(value)

            if len(digits) < 3:
                continue

            for i in range(1, len(digits) - 1):
                left = digits[i - 1]
                current = digits[i]
                right = digits[i + 1]

                if (current > left and current > right) or (
                    current < left and current < right
                ):
                    total += 1

        return total

The implementation follows the algorithm directly.

The outer loop enumerates every number in the range. Each number is converted into a string because digit access becomes straightforward through indexing.

Numbers with fewer than three digits are skipped immediately because they cannot contain interior positions.

For every interior digit, the code compares the current digit against its left and right neighbors. If the digit is strictly greater than both neighbors, it is a peak. If it is strictly less than both neighbors, it is a valley.

Whenever either condition is satisfied, the global answer is incremented.

Finally, the accumulated total waviness is returned.

Go Solution

func totalWaviness(num1 int, num2 int) int {
    total := 0

    for value := num1; value <= num2; value++ {
        digits := []byte(fmt.Sprintf("%d", value))

        if len(digits) < 3 {
            continue
        }

        for i := 1; i < len(digits)-1; i++ {
            left := digits[i-1]
            current := digits[i]
            right := digits[i+1]

            if (current > left && current > right) ||
                (current < left && current < right) {
                total++
            }
        }
    }

    return total
}

The Go implementation mirrors the Python solution closely.

The main difference is that numbers are converted into a byte slice representation of their decimal string using fmt.Sprintf. Byte comparisons work correctly because digit characters preserve numeric ordering in ASCII.

No special overflow handling is required because the maximum possible answer is far below Go's integer limits.

Worked Examples

Example 1

Input:

num1 = 120
num2 = 130

Number	Interior Digit	Peak/Valley	Waviness
120	2	Peak	1
121	2	Peak	1
122	2	No	0
123	2	No	0
124	2	No	0
125	2	No	0
126	2	No	0
127	2	No	0
128	2	No	0
129	2	No	0
130	3	Peak	1

Total:

1 + 1 + 1 = 3

Example 2

Input:

num1 = 198
num2 = 202

Number	Interior Digit	Peak/Valley	Waviness
198	9	Peak	1
199	9	No	0
200	0	No	0
201	0	Valley	1
202	0	Valley	1

Total:

1 + 0 + 0 + 1 + 1 = 3

Example 3

Input:

num1 = 4848
num2 = 4848

Digits:

4 8 4 8

Position	Digit	Left	Right	Result
1	8	4	4	Peak
2	4	8	8	Valley

Total waviness:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O((num2 - num1 + 1) × D)	Each number is scanned once and each digit is inspected once
Space	O(D)	Storage for the digit representation of a single number

Since D ≤ 6, the algorithm is effectively linear in the size of the range. Even the worst case of scanning all numbers from 1 to 100000 requires only a few hundred thousand digit comparisons.

Test Cases

sol = Solution()

assert sol.totalWaviness(120, 130) == 3  # Example 1
assert sol.totalWaviness(198, 202) == 3  # Example 2
assert sol.totalWaviness(4848, 4848) == 2  # Example 3

assert sol.totalWaviness(1, 9) == 0  # Single-digit numbers
assert sol.totalWaviness(10, 99) == 0  # Two-digit numbers

assert sol.totalWaviness(121, 121) == 1  # Single peak
assert sol.totalWaviness(101, 101) == 1  # Single valley

assert sol.totalWaviness(111, 111) == 0  # Equal digits
assert sol.totalWaviness(123, 123) == 0  # Strictly increasing
assert sol.totalWaviness(321, 321) == 0  # Strictly decreasing

assert sol.totalWaviness(909, 909) == 1  # Peak in center
assert sol.totalWaviness(8080, 8080) == 2  # Peak then valley

assert sol.totalWaviness(100000, 100000) == 0  # Upper constraint boundary
assert sol.totalWaviness(99999, 100000) >= 0  # Boundary crossing

Test Summary

Test	Why
(120, 130)	Verifies example 1
(198, 202)	Verifies example 2
(4848, 4848)	Verifies multiple waviness points in one number
(1, 9)	Single-digit edge case
(10, 99)	Two-digit edge case
(121, 121)	Single peak detection
(101, 101)	Single valley detection
(111, 111)	Equal digits should not count
(123, 123)	Increasing sequence
(321, 321)	Decreasing sequence
(909, 909)	Peak in the middle
(8080, 8080)	Multiple interior extrema
(100000, 100000)	Maximum value boundary
(99999, 100000)	Transition across digit lengths

Edge Cases

Numbers With Fewer Than Three Digits

A common mistake is to attempt peak or valley checks on numbers that do not have enough digits. Since peaks and valleys require both a left and right neighbor, every one-digit and two-digit number must contribute zero. The implementation explicitly skips numbers whose digit count is less than three.

Equal Neighboring Digits

The definition requires strict inequality. A digit equal to either neighbor cannot be a peak or valley. For example, 111, 122, and 211 all have waviness zero. The implementation uses only > and < comparisons, ensuring equal digits are never counted.

Multiple Peaks and Valleys in One Number

A number can contribute more than one waviness point. For example, 4848 contains both a peak and a valley. An incorrect implementation might stop after finding the first valid position. The algorithm examines every interior digit independently, ensuring all peaks and valleys are counted.

Maximum Input Range

The largest possible range is from 1 to 100000. Although this appears large at first glance, each number contains at most six digits. The implementation processes every number directly and remains comfortably within acceptable limits because the total number of digit inspections is small.