LogoKode$word

LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

Learn how to solve LeetCode 3751 Total Waviness of Numbers in Range I using a clean Java brute force approach. Includes intuition, peak and valley logic, dry run, complexity analysis, and interview explanation.

Krishna Shrivastava
3 views
LinkedInGithubX
0
0
LeetCodeJavaStringPeaks and ValleysBrute Force SolutionDigit ProblemsMediumArray
LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 3751 introduces an interesting digit-based pattern problem where we calculate the total waviness of numbers inside a given range.

This problem combines:

  1. Digit traversal
  2. Pattern recognition
  3. Peaks and valleys logic
  4. String manipulation
  5. Brute force iteration

The problem is straightforward once we clearly understand how peaks and valleys work.

Problem Statement

You are given two integers:

num1 and num2

representing the inclusive range:

[num1, num2]

For every number:

  1. A digit is called a peak if it is strictly greater than both neighbors.
  2. A digit is called a valley if it is strictly smaller than both neighbors.

The first and last digits can never be peaks or valleys.

Return the total waviness across all numbers in the range.

Example

Input

num1 = 120
num2 = 130

Output

3

Explanation

Numbers contributing to waviness:

120 → 2 is a peak → waviness = 1
121 → 2 is a peak → waviness = 1
130 → 3 is a peak → waviness = 1

Total:

1 + 1 + 1 = 3

Understanding Peaks and Valleys

Peak Condition

A digit is a peak if:

digit > left neighbor
AND
digit > right neighbor

Example:

484

Here:

8 > 4
8 > 4

So 8 is a peak.

Valley Condition

A digit is a valley if:

digit < left neighbor
AND
digit < right neighbor

Example:

202

Here:

0 < 2
0 < 2

So 0 is a valley.

Key Observation

We only need to check:

index 1 to length-2

because:

  1. First digit has no left neighbor
  2. Last digit has no right neighbor

Intuition

The simplest way:

  1. Iterate through every number in the range
  2. Convert number into characters
  3. Check each middle digit
  4. Count peaks and valleys
  5. Add to final answer

Since constraints are small:

num2 <= 10^5

a brute force approach works efficiently.

Java Solution

class Solution {

public int totalWaviness(int num1, int num2) {

int ans = 0;

if(num1 == num2) {

int temp = num1;

String c = Integer.toString(temp);

char[] arr = c.toCharArray();

for(int i = 1; i < arr.length - 1; i++) {

if((arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) ||
(arr[i] > arr[i - 1] && arr[i] > arr[i + 1])) {

ans++;
}
}

return ans;
}

for(int i = num1; i <= num2; i++) {

String c = Integer.toString(i);

char[] carr = c.toCharArray();

for(int j = 1; j < carr.length - 1; j++) {

if((carr[j] < carr[j - 1] && carr[j] < carr[j + 1]) ||
(carr[j] > carr[j - 1] && carr[j] > carr[j + 1])) {

ans++;
}
}
}

return ans;
}
}

Step-by-Step Explanation

Step 1: Iterate Through Range

for(int i = num1; i <= num2; i++)

Process every number.

Step 2: Convert Number to Character Array

String c = Integer.toString(i);
char[] carr = c.toCharArray();

This makes digit comparison easier.

Step 3: Check Middle Digits

for(int j = 1; j < carr.length - 1; j++)

Skip first and last digits.

Step 4: Check Peak or Valley

(carr[j] < carr[j-1] && carr[j] < carr[j+1])

OR

(carr[j] > carr[j-1] && carr[j] > carr[j+1])

If true:

ans++;

Dry Run

Input

num1 = 198
num2 = 202

Number 198

Digits:

1 9 8

Check 9:

9 > 1
9 > 8

Peak found.

Waviness:

1

Number 199

1 9 9

9 is not strictly greater than right neighbor.

No waviness.

Number 201

2 0 1

0 is smaller than both neighbors.

Valley found.

Number 202

2 0 2

Again:

0 < 2
0 < 2

Valley found.

Final Answer

198 → 1
201 → 1
202 → 1

Total = 3

Time Complexity Analysis

Let:

N = num2 - num1 + 1
D = number of digits

Time Complexity

O(N × D)

At most:

D = 6

which is very small.

Efficient for constraints.

Space Complexity

O(D)

due to character array conversion.

Why Brute Force Works Here

Constraints are small:

num2 <= 100000

So checking every number directly is acceptable.

For larger constraints:

  1. Digit DP would be needed.

But here:

  1. Simplicity is better.

Common Mistakes

1. Including First or Last Digit

These digits cannot be peaks or valleys.

2. Using Non-Strict Comparison

Wrong:

>=
<=

Correct:

>
<

because definition says:

strictly greater
strictly smaller

3. Forgetting Both Conditions

Need to check:

  1. Peak
  2. Valley

Edge Cases

Single Digit Numbers

Waviness:

0

because fewer than 3 digits.

Repeated Digits

Example:

111

No peak or valley.

Alternating Digits

Example:

4848

Produces multiple waviness counts.

Interview Explanation

In interviews explain:

Since the constraints are small, we can directly iterate through every number, convert it into digits, and count peaks and valleys by checking neighboring digits.

This demonstrates:

  1. Observation skills
  2. Constraint analysis
  3. Clean implementation

Conclusion

LeetCode 3751 is a clean implementation problem focused on:

  1. Digit traversal
  2. Pattern recognition
  3. Peaks and valleys
  4. Brute force optimization

The key insight is:

A digit contributes to waviness only if it is strictly greater or strictly smaller than both immediate neighbors.

Once this condition is understood, the implementation becomes very straightforward.

Related Articles

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

Another clean example of the "Binary Search on Answer" pattern — intuition, greedy check, commented Java code, dry run, and complexity analysis.

Read Article
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
LeetCode 402: Remove K Digits — Java Solution Explained

LeetCode 402: Remove K Digits — Java Solution Explained

Learn how to solve LeetCode 402 Remove K Digits using Monotonic Stack in Java. Includes greedy intuition, step-by-step dry run, leading zeros handling, time & space complexity analysis.

Read Article
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article
Ai Assistant Kas