3751. Total Waviness of Numbers in Range I

MediumMathDynamic ProgrammingEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

For any number, we measure something called its waviness, which counts how many of its digits are peaks or valleys:

A digit is a peak if it is strictly greater than both the digit on its left and the digit on its right.
A digit is a valley if it is strictly less than both the digit on its left and the digit on its right.
The first and last digits of a number can never be peaks or valleys, because they only have one neighbor.
Any number with fewer than 3 digits has a waviness of 0, since there is no digit that has two neighbors.

For example, in the number 12321:

The digit 2 (second position) is a peak because 2 > 1 and 2 > 3 is false, so let's pick a clearer one.
In 13231, the digit 3 (second position) is a peak (3 > 1 and 3 > 2), the digit 2 (third position) is a valley (2 < 3 and 2 < 3), and the digit 3 (fourth position) is a peak (3 > 2 and 3 > 1). So its waviness is 3.

Your task is to compute the waviness of every number in the range [num1, num2] and return the total sum of all these waviness values.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Iterating over each number in the range and counting peaks and valleys among its digits is a direct simulation of the described process.

Open in Flowchart

Intuition

The problem asks us to add up the waviness of every number in the range [num1, num2]. The most direct idea is to simply look at each number one by one and count its peaks and valleys, then keep a running total.

To find the waviness of a single number, we first need access to its individual digits. We can extract them by repeatedly taking the last digit using x % 10 and removing it with x //= 10. This gives us all the digits of the number stored in an array.

Once we have the digits, the rule is straightforward: a digit in the middle (not the first or last) is interesting only if it stands out from both of its neighbors. So for each middle digit, we check two conditions:

If it is greater than both neighbors, it is a peak.
If it is less than both neighbors, it is a valley.

Either case adds 1 to the waviness count. Numbers with fewer than 3 digits are skipped entirely, since they cannot have any middle digit with two neighbors.

By wrapping this counting logic into a helper function f(x), we can cleanly compute the waviness of any single number. Then we just loop through the whole range and sum up f(x) for each value, which naturally gives us the final answer.

Pattern Learn more about Math and Dynamic Programming patterns.

Solution Approach

Solution 1: Simulation

We define a helper function f(x) to calculate the waviness value of integer x. In this function, we store each digit of integer x into an array nums. The extraction is done by repeatedly taking x % 10 (the last digit) and then shrinking the number with x //= 10, until x becomes 0.

After collecting the digits, let m be the length of nums. If m < 3, the number has fewer than 3 digits, so its waviness value is 0 and we return immediately.

Otherwise, we initialize a counter s = 0 and iterate through each non-leading and non-trailing digit, that is, indices i from 1 to m - 2. For each such digit nums[i], we check:

If nums[i] > nums[i - 1] and nums[i] > nums[i + 1], it is a peak, so we add 1 to s.
Otherwise, if nums[i] < nums[i - 1] and nums[i] < nums[i + 1], it is a valley, so we add 1 to s.

We then return s as the waviness value of x.

Finally, we iterate through each integer x in the range [num1, num2] and accumulate its waviness value f(x) to obtain the final result.

The time complexity is O(n × log m), where n is the count of integers in the range [num1, num2], and log m reflects the number of digits we process for each integer m. The space complexity is O(log m), used to store the digits of a single number.

Example Walkthrough

Let's trace through a small example with num1 = 230 and num2 = 232. We need to compute the waviness of every number in this range and sum them up.

We'll use the helper function f(x) on each number, then accumulate the results.

Step 1: Compute f(230)

First, extract the digits by repeatedly taking x % 10 and shrinking with x //= 10:

230 % 10 = 0 → nums = [0], then x = 23
23 % 10 = 3 → nums = [0, 3], then x = 2
2 % 10 = 2 → nums = [0, 3, 2], then x = 0 (stop)

So nums = [0, 3, 2] (digits stored least-significant first). The length m = 3, which is not less than 3, so we proceed.

Iterate over the middle indices i from 1 to m - 2 = 1, so only i = 1:

nums[1] = 3, neighbors are nums[0] = 0 and nums[2] = 2.
Is it a peak? 3 > 0 ✅ and 3 > 2 ✅ → yes, add 1.

So f(230) = 1. (This makes sense: in 230, the digit 3 is strictly greater than 2 and 0.)

Step 2: Compute f(231)

Extract digits:

231 % 10 = 1 → nums = [1], then x = 23
23 % 10 = 3 → nums = [1, 3], then x = 2
2 % 10 = 2 → nums = [1, 3, 2], then x = 0 (stop)

So nums = [1, 3, 2], m = 3. Check i = 1:

nums[1] = 3, neighbors nums[0] = 1 and nums[2] = 2.
Peak? 3 > 1 ✅ and 3 > 2 ✅ → yes, add 1.

So f(231) = 1. (In 231, the digit 3 is a peak.)

Step 3: Compute f(232)

Extract digits:

232 % 10 = 2 → nums = [2], then x = 23
23 % 10 = 3 → nums = [2, 3], then x = 2
2 % 10 = 2 → nums = [2, 3, 2], then x = 0 (stop)

So nums = [2, 3, 2], m = 3. Check i = 1:

nums[1] = 3, neighbors nums[0] = 2 and nums[2] = 2.
Peak? 3 > 2 ✅ and 3 > 2 ✅ → yes, add 1.

So f(232) = 1. (In 232, the middle 3 is a peak.)

Step 4: Sum everything up

Number	Digits	Waviness
230	`[0, 3, 2]`	1
231	`[1, 3, 2]`	1
232	`[2, 3, 2]`	1

Total = 1 + 1 + 1 = 3.

The final answer for the range [230, 232] is 3.

This walkthrough shows the two-layer structure of the solution: the outer loop visits each number in the range, while the inner helper f(x) extracts digits and counts peaks/valleys among the middle positions.

Solution Implementation

1class Solution:
2    def totalWaviness(self, num1: int, num2: int) -> int:
3        def count_waviness(value: int) -> int:
4            # Extract the digits of `value` into a list (least significant first).
5            digits: list[int] = []
6            while value:
7                digits.append(value % 10)
8                value //= 10
9
10            length = len(digits)
11            # A waviness point needs both a left and right neighbor,
12            # so numbers with fewer than 3 digits contribute nothing.
13            if length < 3:
14                return 0
15
16            count = 0
17            # Inspect every interior digit (skip the first and last).
18            for i in range(1, length - 1):
19                left, mid, right = digits[i - 1], digits[i], digits[i + 1]
20                # Local maximum: greater than both neighbors.
21                if mid > left and mid > right:
22                    count += 1
23                # Local minimum: smaller than both neighbors.
24                elif mid < left and mid < right:
25                    count += 1
26            return count
27
28        # Sum the waviness of every number in the inclusive range [num1, num2].
29        return sum(count_waviness(value) for value in range(num1, num2 + 1))
30

1class Solution {
2    /**
3     * Calculates the total "waviness" of all integers in the inclusive range [num1, num2].
4     * The waviness of a single number is the count of its "wave" digits (local peaks or valleys).
5     *
6     * @param num1 the lower bound of the range (inclusive)
7     * @param num2 the upper bound of the range (inclusive)
8     * @return the sum of waviness values for every integer in the range
9     */
10    public int totalWaviness(int num1, int num2) {
11        int totalSum = 0;
12        // Accumulate the waviness for each number in the range.
13        for (int current = num1; current <= num2; current++) {
14            totalSum += computeWaviness(current);
15        }
16        return totalSum;
17    }
18
19    /**
20     * Computes the waviness of a single number.
21     * A digit (excluding the first and last) is considered "wavy" if it is either:
22     *   - a local peak  (strictly greater than both neighbors), or
23     *   - a local valley (strictly less than both neighbors).
24     *
25     * @param value the number whose waviness is computed
26     * @return the number of wavy digits in the value
27     */
28    private int computeWaviness(int value) {
29        // Buffer large enough to hold the digits of any 32-bit integer.
30        int[] digits = new int[20];
31        int length = 0;
32
33        // Extract digits from least significant to most significant.
34        // After this loop, digits[0] is the lowest-order digit.
35        while (value > 0) {
36            digits[length++] = value % 10;
37            value /= 10;
38        }
39
40        // Numbers with fewer than 3 digits have no interior digits to be wavy.
41        if (length < 3) {
42            return 0;
43        }
44
45        int waviness = 0;
46        // Examine every interior digit and test the peak/valley condition.
47        for (int i = 1; i < length - 1; i++) {
48            boolean isPeak = digits[i] > digits[i - 1] && digits[i] > digits[i + 1];
49            boolean isValley = digits[i] < digits[i - 1] && digits[i] < digits[i + 1];
50            if (isPeak || isValley) {
51                waviness++;
52            }
53        }
54        return waviness;
55    }
56}
57

1class Solution {
2public:
3    // Compute the total "waviness" for all integers in the inclusive range [num1, num2].
4    int totalWaviness(int num1, int num2) {
5        int totalCount = 0;
6        for (int value = num1; value <= num2; ++value) {
7            totalCount += countWaves(value);
8        }
9        return totalCount;
10    }
11
12private:
13    // Count the number of "wave" positions in a single number.
14    // A wave position is a digit that is either a strict local maximum
15    // (greater than both neighbors) or a strict local minimum
16    // (less than both neighbors).
17    int countWaves(int value) {
18        int digits[20];
19        int length = 0;
20
21        // Extract digits from least significant to most significant.
22        // (The relative ordering used for peak/valley checks is preserved.)
23        while (value > 0) {
24            digits[length++] = value % 10;
25            value /= 10;
26        }
27
28        // A number needs at least 3 digits to contain an interior digit
29        // that can be a local maximum or minimum.
30        if (length < 3) {
31            return 0;
32        }
33
34        int waveCount = 0;
35        // Examine every interior digit and test for a peak or a valley.
36        for (int i = 1; i < length - 1; ++i) {
37            bool isPeak = digits[i] > digits[i - 1] && digits[i] > digits[i + 1];
38            bool isValley = digits[i] < digits[i - 1] && digits[i] < digits[i + 1];
39            if (isPeak || isValley) {
40                ++waveCount;
41            }
42        }
43        return waveCount;
44    }
45};
46

1/**
2 * Computes the sum of "waviness" values for all integers
3 * in the inclusive range [num1, num2].
4 *
5 * @param num1 - The lower bound of the range (inclusive).
6 * @param num2 - The upper bound of the range (inclusive).
7 * @returns The total accumulated waviness across the range.
8 */
9function totalWaviness(num1: number, num2: number): number {
10    let total = 0;
11    // Iterate over every integer in the range and accumulate its waviness.
12    for (let current = num1; current <= num2; current++) {
13        total += f(current);
14    }
15    return total;
16}
17
18/**
19 * Calculates the "waviness" of a single number.
20 *
21 * Waviness is defined as the number of digits (excluding the first and last)
22 * that are a strict local peak (greater than both neighbors) or
23 * a strict local valley (less than both neighbors).
24 *
25 * @param x - The number whose waviness is evaluated.
26 * @returns The count of local peaks and valleys among the digits.
27 */
28function f(x: number): number {
29    // Extract the digits of x from least significant to most significant.
30    const digits: number[] = [];
31    while (x > 0) {
32        digits.push(x % 10);
33        x = Math.floor(x / 10);
34    }
35
36    const length = digits.length;
37    // Fewer than 3 digits cannot form a peak or valley.
38    if (length < 3) {
39        return 0;
40    }
41
42    let waviness = 0;
43    // Check each interior digit to see if it is a local peak or valley.
44    for (let i = 1; i < length - 1; i++) {
45        const isPeak = digits[i] > digits[i - 1] && digits[i] > digits[i + 1];
46        const isValley = digits[i] < digits[i - 1] && digits[i] < digits[i + 1];
47        if (isPeak || isValley) {
48            waviness++;
49        }
50    }
51
52    return waviness;
53}
54

Time and Space Complexity

Time complexity: O((num2 - num1 + 1) × log num2).

The outer sum iterates over every integer x in the range [num1, num2], which contributes a factor of O(num2 - num1 + 1). For each value x, the helper function f(x) extracts its digits via the while x loop, running O(log x) times (the number of digits of x), and then iterates over those digits once more, which is also O(log x). Since x ≤ num2, the per-element cost is O(log num2). Multiplying the two factors gives an overall time complexity of O((num2 - num1 + 1) × log num2).
Space complexity: O(log num2).

Inside f(x), the list nums stores all the digits of x, whose count is O(log x) ≤ O(log num2). This list is recreated for each value but only one exists at a time, so the dominant auxiliary space is O(log num2). The generator expression passed to sum does not materialize all values simultaneously, contributing only constant additional space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing the meaning of "peak" and "valley" due to digit order after extraction

When extracting digits using the value % 10 and value //= 10 technique, the digits are stored in reverse order (least significant digit first). For example, 13231 becomes [1, 3, 2, 3, 1] — which happens to be a palindrome, so the bug stays hidden! But for a number like 12340, the actual digits are 1, 2, 3, 4, 0, while extraction produces [0, 4, 3, 2, 1].

A common mistake is to assume this reversal will change the result. In fact, for counting peaks and valleys, reversing the digit sequence does not change the count: a peak remains a peak and a valley remains a valley regardless of left-to-right vs. right-to-left traversal, because both neighbor comparisons are symmetric. The real danger arises when someone "fixes" the order inconsistently — for instance, reversing only part of the logic, or mixing a reversed list with index assumptions based on the original number. This introduces subtle off-by-position errors.

Solution: Either keep the reversed list (which is correct for this symmetric problem) or explicitly reverse it once for clarity, but never mix conventions:

digits = []
while value:
    digits.append(value % 10)
    value //= 10
digits.reverse()  # Now digits are in natural left-to-right order.

Pitfall 2: Performance blow-up on large ranges

The simulation iterates over every integer in [num1, num2]. If the range spans something like [1, 10**9], this loop runs a billion times and will time out. Many solvers assume the input range is small and are surprised by TLE on hidden large test cases.

Solution: When the range is large, switch to digit DP (digit dynamic programming). The idea is to count the total waviness across all numbers without enumerating each one. Define f(x) as the total waviness of all numbers in [0, x], then answer with f(num2) - f(num1 - 1).

A sketch of the digit DP state:

from functools import lru_cache

def total_up_to(n: int) -> int:
    s = str(n)

    @lru_cache(maxsize=None)
    def dp(pos: int, prev: int, prev2: int, tight: bool, started: bool) -> int:
        if pos == len(s):
            return 0
        limit = int(s[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            ntight = tight and (d == limit)
            nstarted = started or (d > 0)
            add = 0
            # Once we have at least three started digits, the middle one (prev)
            # can be checked as a peak/valley using prev2 (left) and d (right).
            if started and prev2 != -1:
                if prev > prev2 and prev > d:
                    add = 1
                elif prev < prev2 and prev < d:
                    add = 1
            total += add + dp(pos + 1, d, prev if nstarted else -1, ntight, nstarted)
        return total

    return dp(0, -1, -1, True, False)

Note: the leading-zero handling (started/prev2 == -1) is the trickiest part — leading zeros must not be treated as real digits that form peaks/valleys, otherwise numbers like 7 would be wrongly seen as 007.

Pitfall 3: Off-by-one in the interior loop range

The interior digits are indices 1 to length - 2. A frequent mistake is writing range(1, length - 1) but mentally treating it as inclusive of length - 1, or writing range(1, length) which incorrectly includes the last digit (which has no right neighbor) and causes an IndexError at digits[i + 1].

Solution: Remember that range(1, length - 1) already correctly stops at index length - 2, ensuring digits[i + 1] never goes out of bounds:

for i in range(1, length - 1):   # i ranges over interior indices only
    ...
    right = digits[i + 1]        # always valid since i <= length - 2

Pitfall 4: Using if/elif is correct, but using two separate if statements is not

A digit cannot be both a peak and a valley simultaneously, so logically two if blocks would behave the same. However, mistakenly combining the conditions with an or (e.g., if (mid > left and mid > right) or (mid < left and mid < right)) is fine, but writing flawed boundary logic like if mid >= left (using >= instead of strict >) breaks the strictly greater/less requirement, causing plateaus to be miscounted as peaks.

Solution: Always use strict comparisons (> and <), never >= or <=, to honor the "strictly greater" and "strictly less" definitions:

if mid > left and mid > right:      # strict peak
    count += 1
elif mid < left and mid < right:    # strict valley
    count += 1

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering