Skip to main content
Talentd

Total Waviness of Numbers in Range I - Solution & Explanation

MediumMathDynamic ProgrammingEnumeration8 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105

Approach Overview

Problem Overview: Given a numeric range [L, R], compute the total waviness across all numbers in that interval. Waviness depends on how adjacent digits in a number change, so each number must be inspected digit by digit and its contribution added to the final sum.

Approach 1: Brute Force Enumeration (O((R-L+1) * d) time, O(1) space)

Iterate through every integer from L to R. Convert each number to its digit representation and evaluate the waviness by scanning adjacent digits. Maintain a running total as you process each number. This approach relies purely on enumeration and basic digit processing. It works well when the range size is small but becomes expensive when R - L grows large because every number is processed individually.

Approach 2: Simulation with Digit Processing (O((R-L+1) * d) time, O(1) space)

The practical solution used in most implementations still iterates through the range but computes waviness efficiently while extracting digits. Instead of repeatedly converting to strings, use arithmetic operations (% 10, / 10) to inspect adjacent digits. Track the previous digit and update the waviness contribution during traversal. This keeps the computation tight and avoids extra allocations. The method fits naturally with problems involving math and digit-based rules.

Approach 3: Digit Dynamic Programming (O(d * states) time, O(d * states) space)

If the range becomes very large, iterate by digit position instead of by number. A classic dynamic programming technique builds numbers digit by digit while tracking constraints such as the previous digit and whether the prefix is already smaller than the bound. Each state accumulates the waviness contribution produced by the transition between digits. This avoids enumerating every integer and reduces the problem to processing digit states.

Recommended for interviews: Start with the brute force enumeration to show you understand how waviness is computed from digits. Then optimize the implementation using direct digit simulation to reduce overhead. When the interviewer hints at very large ranges, transitioning to a digit DP solution demonstrates deeper algorithmic skill and familiarity with range digit problems.

Solution

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 in an array nums. If the number has fewer than 3 digits, the waviness value is 0. Otherwise, we iterate through each non-leading and non-trailing digit in the array nums, determine whether it is a peak or valley, and count the waviness value.

Then, 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((num2 - num1 + 1) cdot log num2) and the space complexity is O(log num2).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO((R-L+1) * d)O(1)Small ranges where iterating every number is cheap
Simulation with Digit ProcessingO((R-L+1) * d)O(1)General case when the range fits within typical constraints
Digit Dynamic ProgrammingO(d * states)O(d * states)Very large ranges where enumerating each number is too slow

Video Solution

Total Waviness of Numbers in Range I | Simple | Leetcode 3751 | codestorywithMIK • codestorywithMIK • 5,863 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Total Waviness of Numbers in Range I easy or hard?
Total Waviness of Numbers in Range I is usually categorized as Medium difficulty. The direct simulation is straightforward, but recognizing digit-based optimizations or digit DP techniques requires stronger algorithmic experience.
Total Waviness of Numbers in Range I Python/Java solution
A typical implementation iterates from L to R, extracts digits using modulo and division, and accumulates the waviness value. The same logic works across Python, Java, C++, Go, and TypeScript with identical O((R-L+1) * d) complexity.
How to solve Total Waviness of Numbers in Range I in O(n)?
Treat n as the number of integers in the range. Iterate through each number once and compute its waviness by comparing adjacent digits. Using arithmetic digit extraction keeps the per-number work proportional to its digit count, giving an effective O(n * d) solution.
What is the best approach for Total Waviness of Numbers in Range I?
The most practical approach is simulation with digit processing. Iterate from L to R and compute waviness for each number by scanning adjacent digits using arithmetic operations. This runs in O((R-L+1) * d) time where d is the number of digits, and uses O(1) extra space.
Is Total Waviness of Numbers in Range I asked at Google/Amazon/Meta?
Problems involving digit analysis, enumeration, and digit DP appear frequently in interviews at companies like Google and Amazon. Variants often ask you to process ranges of numbers and compute digit-based metrics efficiently.
What data structure is used in Total Waviness of Numbers in Range I?
The core solution does not require complex data structures. Simple integer variables and digit traversal are enough. More advanced solutions may use memoization tables in digit dynamic programming to store intermediate states.
What is the time complexity of Total Waviness of Numbers in Range I?
A direct simulation approach runs in O((R-L+1) * d) time because each number in the range is processed and each digit pair is examined once. Space complexity is O(1) since only a few variables are needed while scanning digits.

Ready to solve this problem?

Practice Total Waviness of Numbers in Range I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer