Weekly Contest 502 | leetcode 3931|leetcode 3932 | leetcode 3933 | leetcode 3934 | Binary Search
Check Adjacent Digit Differences - Video Solution
Watch 8 video solutions for Check Adjacent Digit Differences, a easy level problem involving String. This walkthrough by Code With Vick has 841 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string s consisting of digits.
Return true if the absolute difference between every pair of adjacent digits is at most 2, otherwise return false.
The absolute difference between a and b is defined as abs(a - b).
Example 1:
Input: s = "132"
Output: true
Explanation:
- The absolute difference between digits at
s[0]ands[1]isabs(1 - 3) = 2. - The absolute difference between digits at
s[1]ands[2]isabs(3 - 2) = 1. - Since both differences are at most 2, the answer is true.
Example 2:
Input: s = "129"
Output: false
Explanation:
- The absolute difference between digits at
s[0]ands[1]isabs(1 - 2) = 1. - The absolute difference between digits at
s[1]ands[2]isabs(2 - 9) = 7, which is greater than 2. - Therefore, the answer is false.
Constraints:
2 <= s.length <= 100sconsists only of digits.
Approach Overview
Problem Overview: Given an integer, determine whether every pair of adjacent digits has an absolute difference of exactly 1. If all neighboring digits satisfy this condition, return true; otherwise return false.
Approach 1: Convert to String and Compare Neighbors (O(n) time, O(n) space)
Convert the integer into a string so each digit becomes easy to access by index. Iterate from the first digit to the second-to-last digit and compute the absolute difference between s[i] and s[i+1]. If any pair has a difference other than 1, return false immediately. This approach is simple and readable, which makes it common in interview settings where clarity matters more than micro-optimizations. The tradeoff is the extra space used to store the string representation.
Approach 2: Mathematical Digit Extraction (O(n) time, O(1) space)
Instead of converting the number to a string, repeatedly extract digits using modulo and division operations. Store the last digit with num % 10, remove it with num // 10, and compare it with the next extracted digit. Each comparison checks abs(current - next) == 1. This avoids allocating extra memory and works directly on the integer. The logic relies on basic math operations and sequential processing similar to techniques used in number manipulation problems.
Approach 3: Early Exit Linear Scan (O(n) time, O(1) space)
Regardless of whether digits come from a string or arithmetic extraction, the optimal strategy is a single pass with early termination. As soon as one pair violates the rule, stop processing and return false. This keeps the algorithm efficient and avoids unnecessary work. The pattern is essentially a simple linear scan where each step compares neighboring elements.
Recommended for interviews: The mathematical digit extraction approach. It demonstrates comfort with integer manipulation and achieves O(1) auxiliary space. The string approach is still acceptable and often faster to implement during a timed interview, but showing the constant‑space method signals stronger control over low‑level operations.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Conversion and Neighbor Check | O(n) | O(n) | When readability and quick implementation matter |
| Mathematical Digit Extraction | O(n) | O(1) | When optimizing memory or demonstrating number manipulation |
| Early Exit Linear Scan | O(n) | O(1) | General case where immediate failure detection improves runtime |