Problem Statement in English

You’re given two positive integers num1 and num2. The waviness score of an integer is the number of indices i such that the digit at index i is greater than both its neighbors or less than both its neighbors.

The total waviness of numbers in the range [num1, num2] is the sum of the waviness scores of all integers in that range.

Approach

All we need to do is iterate through all the numbers from num1 to num2, and for each number, calculate its waviness score by checking each digit against its neighbors. We can convert the number to a string to easily access its digits.

And we’re done!

Solution in Python


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

        for i in range(num1, num2 + 1):
            score = 0
            s = str(i)
            
            for j in range(1, len(s) - 1):
                if s[j - 1] < s[j] > s[j + 1] or s[j - 1] > s[j] < s[j + 1]:
                    score += 1
            
            res += score

        return res

Complexity

  • Time: $O(n \cdot m)$
    Since we are iterating through all the numbers from num1 to num2 and for each number, we are iterating through its digits to calculate the waviness score. Here, n is the number of integers in the range and m is the average number of digits in those integers.

  • Space: $O(1)$
    We are using a constant amount of space to store the result and the score for each number, regardless of the input size.

And we are done.