3751. Total Waviness of Numbers in Range I

Math
Simulation

TIME

O(R * D)

SPACE

O(D)

Intuition

The range upper bound is only 10^5, so we can inspect every number directly.

For each number, only internal digits can contribute to waviness. A digit contributes 1 if it is strictly greater than both neighbors or strictly smaller than both neighbors.

Approach

Initialize the total answer to 0.
For every number from num1 to num2:
- convert it to a string of digits
- check each internal digit from index 1 to len(digits) - 2
- add 1 when the digit is a peak or valley
Return the total.

Complexity

Let R = num2 - num1 + 1 and D be the maximum number of digits.

Time: O(R * D)
Space: O(D), for the digit string

Since num2 <= 10^5, D is at most 6.

Edge Cases

Numbers with fewer than 3 digits -> waviness is 0
Equal neighboring digits -> not a peak or valley because comparisons must be strict
Single-number range -> return that number's waviness
Alternating digits like 4848 -> every internal digit may contribute

Code

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        """
        3751. Total Waviness of Numbers in Range I
        Time: O(R * D)
        Space: O(D)
        """
        def waviness(num: int) -> int:
            digits = str(num)
            count = 0

            for index in range(1, len(digits) - 1):
                previous_digit = digits[index - 1]
                current_digit = digits[index]
                next_digit = digits[index + 1]

                if (
                    previous_digit < current_digit > next_digit
                    or previous_digit > current_digit < next_digit
                ):
                    count += 1

            return count

        return sum(waviness(num) for num in range(num1, num2 + 1))

/**
 * 3751. Total Waviness of Numbers in Range I
 * Time: O(R * D)
 * Space: O(D)
 */
class Solution {
    public int totalWaviness(int num1, int num2) {
        int total = 0;

        for (int num = num1; num <= num2; num++) {
            total += waviness(num);
        }

        return total;
    }

    private int waviness(int num) {
        String digits = Integer.toString(num);
        int count = 0;

        for (int index = 1; index < digits.length() - 1; index++) {
            char previousDigit = digits.charAt(index - 1);
            char currentDigit = digits.charAt(index);
            char nextDigit = digits.charAt(index + 1);

            if (
                (previousDigit < currentDigit && currentDigit > nextDigit)
                    || (previousDigit > currentDigit && currentDigit < nextDigit)
            ) {
                count++;
            }
        }

        return count;
    }
}