Check Adjacent Digit Differences solution and explanation
7 more videos on this problem
Weekly Contest 502 | leetcode 3931|leetcode 3932 | leetcode 3933 | leetcode 3934 | Binary SearchCode With Vick · 48:42 · 841 views
Check Adjacent Digit Differences | LeetCode 3931 | Weekly Contest 502 | Java | Developer CoderDeveloper Coder · 2:23 · 55 views
Weekly Contest 502 - Check Adjacent Digit Differences | Easy C++ Solution in 3 MinutesDivyansh yadav · 3:30 · 41 views
Check Adjacent Digit Differences | Leetcode 3931 | Explanation With Code | Javacodewithsitaram · 5:53 · 34 views
Weekly Contest 502 | Check Adjacent Digit Differences ExplainedR Sai Siddhu · 3:30 · 26 views
The Smart Observation Behind Check Adjacent Digit Differences | LeetCode 3931Pal Pathak · 9:19 · 18 views
Check Adjacent Digit Differences | Leetcode weekly contest 502 | #3931UMANG AGRAWAL · 4:28 · 10 views
Check Adjacent Digit Differences | 3931 | Weekly Contest 502 | LeetcodeGhost Codes · 1:10 · 8 views
The problem
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.
Solution
We can simulate the process described in the problem: iterate through each pair of adjacent digits in the string and compute their absolute difference. If any pair has an absolute difference greater than 2, return false. If no such pair is found after the traversal, return true.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
class Solution:
def isAdjacentDiffAtMostTwo(self, s: str) -> bool:
return all(abs(x - y) <= 2 for x, y in pairwise(map(int, list(s))))class Solution {
public boolean isAdjacentDiffAtMostTwo(String s) {
for (int i = 1; i < s.length(); ++i) {
if (Math.abs(s.charAt(i - 1) - s.charAt(i)) > 2) {
return false;
}
}
return true;
}
}class Solution {
public:
bool isAdjacentDiffAtMostTwo(string s) {
for (int i = 1; i < s.size(); ++i) {
if (abs(s[i - 1] - s[i]) > 2) {
return false;
}
}
return true;
}
};function isAdjacentDiffAtMostTwo(s: string): boolean {
for (let i = 1; i < s.length; i++) {
if (Math.abs(Number(s[i]) - Number(s[i - 1])) > 2) {
return false;
}
}
return true;
}func isAdjacentDiffAtMostTwo(s string) bool {
for i := 1; i < len(s); i++ {
if abs(int(s[i-1])-int(s[i])) > 2 {
return false
}
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}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 |
Frequently asked questions
Is Check Adjacent Digit Differences easy or hard?
Check Adjacent Digit Differences is generally classified as an Easy problem. The logic requires a basic linear scan and simple arithmetic checks between adjacent digits, making it suitable for beginners practicing number manipulation.
Check Adjacent Digit Differences Python/Java solution
The implementation usually iterates through digits and checks abs(digit[i] - digit[i+1]) == 1. Python can iterate over a string or use modulo operations, while Java commonly uses integer division and modulo to extract digits. Both implementations run in O(n) time.
How to solve Check Adjacent Digit Differences in O(n)?
Process digits sequentially and compare every adjacent pair. Extract digits using modulo (num % 10) and integer division (num // 10) or iterate through a string representation. For each pair, check if abs(d1 - d2) equals 1 and stop immediately if the condition fails.
What is the best approach for Check Adjacent Digit Differences?
The best approach is a single linear scan of the digits while checking the absolute difference between adjacent pairs. Extract digits either by converting the number to a string or using modulo and division operations. The optimal implementation runs in O(n) time with O(1) extra space when digits are processed mathematically.
Is Check Adjacent Digit Differences asked at Google/Amazon/Meta?
Problems involving digit manipulation and adjacency checks appear frequently in coding interviews at large tech companies. While this exact problem may vary, similar questions testing number processing, absolute differences, and linear scans show up in screening rounds.
What data structure is used in Check Adjacent Digit Differences?
No complex data structure is required. The solution typically uses simple integer arithmetic or a string representation of the number. The algorithm relies on sequential comparison of digits rather than storing large structures.
What is the time complexity of Check Adjacent Digit Differences?
The time complexity is O(n), where n is the number of digits in the input number. Each digit is processed once while comparing it with its adjacent neighbor. The space complexity can be O(1) with arithmetic extraction or O(n) if the number is converted to a string.
