Check if Number Has Equal Digit Count and Digit Value - Solution & Explanation
Problem Statement
You are given a 0-indexed string num of length n consisting of digits.
Return true if for every index i in the range 0 <= i < n, the digit i occurs num[i] times in num, otherwise return false.
Example 1:
Input: num = "1210" Output: true Explanation: num[0] = '1'. The digit 0 occurs once in num. num[1] = '2'. The digit 1 occurs twice in num. num[2] = '1'. The digit 2 occurs once in num. num[3] = '0'. The digit 3 occurs zero times in num. The condition holds true for every index in "1210", so return true.
Example 2:
Input: num = "030" Output: false Explanation: num[0] = '0'. The digit 0 should occur zero times, but actually occurs twice in num. num[1] = '3'. The digit 1 should occur three times, but actually occurs zero times in num. num[2] = '0'. The digit 2 occurs zero times in num. The indices 0 and 1 both violate the condition, so return false.
Constraints:
n == num.length1 <= n <= 10numconsists of digits.
Approach Overview
Problem Overview: You are given a numeric string num. For each index i, the digit at that position represents how many times digit i must appear in the entire string. The task is to check whether the actual frequency of every digit matches the value stored at its corresponding index.
Approach 1: Count Digits with a Frequency Array (O(n) time, O(1) space)
The direct solution counts how often each digit appears, then verifies whether those counts match the values in the string. Iterate once through num and update a frequency array of size 10 where freq[d] stores how many times digit d occurs. Then iterate again through the string: for index i, convert num[i] to an integer and compare it with freq[i]. If any index fails the check, return false. If all positions match, the number satisfies the condition. The array size is constant (digits 0–9), so the space complexity stays O(1). This approach relies on simple counting and works well because the digit range is fixed.
Approach 2: Count and Verify In-place (O(n^2) time, O(1) space)
This version avoids storing a separate frequency structure. For each index i, scan the entire string and count how many times digit i appears. Compare that count directly with num[i]. If any mismatch occurs, return false. Since each position triggers a full scan, the algorithm performs up to n scans of length n, giving O(n^2) time complexity. The advantage is minimal memory usage—no extra arrays or hash table structures. The logic is simple but slower for longer inputs.
Recommended for interviews: The frequency array solution is the expected answer. It demonstrates efficient use of string traversal and constant-size counting structures, achieving linear time with minimal space. Showing the naive repeated-count idea first can demonstrate problem understanding, but interviewers typically want the O(n) counting approach.
Approach 1: Count Digits with a Frequency Array
Use an array to count the frequency of each digit (0-9) in the string. Check if each digit i matches the count specified at num[i].
This C solution uses an array to track the frequency of each digit. It iterates over the input string to populate this frequency array and then checks each digit against the expected count.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as the array size is constant (10 elements).
Approach 2: Count and Verify In-place
Instead of storing results in an array, count digits as needed directly against the requirement in the input string.
This approach counts occurrences of each expected digit in-place by iterating over the string multiple times for each digit check.
Complexity
Time Complexity: O(n^2).
Space Complexity: O(1).
Approach 3: Counting + Enumeration
We can use an array cnt of length 10 to count the occurrences of each digit in the string num. Then, we enumerate each digit in the string num and check if its occurrence count equals the digit itself. If this condition is satisfied for all digits, we return true; otherwise, we return false.
The time complexity is O(n), and the space complexity is O(|\Sigma|). Here, n is the length of the string num, and |\Sigma| is the range of possible digit values, which is 10.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Count Digits with a Frequency Array | Time Complexity: O(n), where n is the length of the string. |
| Count and Verify In-place | Time Complexity: O(n^2). |
| Counting + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Digits with Frequency Array | O(n) | O(1) | Best general solution; efficient for all inputs with constant digit range |
| Count and Verify In-place | O(n^2) | O(1) | Useful when avoiding extra memory or demonstrating brute-force reasoning |
Video Solution
Leetcode 2283 - Check if Number Has Equal Digit Count and Digit Value || Biweekly Contest 79 • Leetcode Hub • 1,393 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Number Has Equal Digit Count and Digit Value easy or hard?
Check if Number Has Equal Digit Count and Digit Value Python/Java solution
How to solve Check if Number Has Equal Digit Count and Digit Value in O(n)?
What is the best approach for Check if Number Has Equal Digit Count and Digit Value?
Is Check if Number Has Equal Digit Count and Digit Value asked at Google/Amazon/Meta?
What data structure is used in Check if Number Has Equal Digit Count and Digit Value?
What is the time complexity of Check if Number Has Equal Digit Count and Digit Value?
Ready to solve this problem?
Practice Check if Number Has Equal Digit Count and Digit Value with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor