Count Values With Equally Spaced Occurrences II solution and explanation
2 more videos on this problem
LeetCode 4049 | Biweekly Contest 191 Q2 | Count Values With Equally Spaced Occurrences II | C++CodeSprint · 8:05 · 91 views
Leetcode 4049 : Count Values With Equally Spaced Occurences IIJash Rashne · 12:14 · 6 views
Easy Hash Map Solution! 💡 LeetCode 4049: Count Values With Equally Spaced Occurrences IIengfootsteps · 4:01 · 1 view
The problem
You are given an integer array nums.
An integer x is called special if:
xappears at least three times innums.- All occurrences of
xare equally spaced innums. In other words, if all occurrences ofxare at indicesi1 < i2 < ... < im, theni2 - i1 = i3 - i2 = ... = im - im-1.
Return the number of distinct special integers in nums.
Example 1:
Input: nums = [1,8,1,5,1,5,8,5]
Output: 2
Explanation:
- 1 is special because it occurs at equally spaced indices 0, 2, and 4.
- 5 is special because it occurs at equally spaced indices 3, 5, and 7.
- 8 is not special because it occurs only twice.
Therefore, the answer is 2.
Example 2:
Input: nums = [8,8,8,8]
Output: 1
Explanation:
8 is special because it occurs at equally spaced indices 0, 1, 2, and 3. Therefore, the answer is 1.
Example 3:
Input: nums = [8,6,6,8,8]
Output: 0
Explanation:
8 occurs at indices 0, 3, and 4, which are not equally spaced. 6 occurs only twice. Therefore, no integer is special.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You scan an array and count the values whose occurrences form an equally spaced pattern, meaning the gap between consecutive occurrences of the same value never changes. The input can be large, so the solution has to avoid rescanning the array for every value.
Approach 1: Brute Force Scan Per Value (O(n^2) time, O(n) space)
Collect the distinct values, then for each value walk the array and record every index where it appears. Compute the differences between consecutive indices and check that they are all identical. This is easy to reason about and it confirms the definition directly. The cost is that each value triggers a full pass over the array, so with many distinct values you do O(n) work per value and O(n^2) overall. Use it to verify your understanding before optimizing.
Approach 2: Hash Table with Per-Value State (O(n) time, O(n) space)
Use a hash table keyed by value. For each value, store its last seen index, its common gap, and a flag that says whether the spacing still holds. When you read a value at index i, look up its entry. If it is new, record the index. If it has a stored gap, compare i minus the last index to that gap and mark the value as broken on any mismatch. Each element is processed once, so the whole array is handled in a single pass. The key insight is that you never need the full list of positions. Two numbers per value are enough to decide whether the spacing is still equal.
Approach 3: Single Pass With Counting Summary (O(n) time, O(n) space)
Once the per-value state is built, a second pass over the hash table counts the values that still satisfy the condition. This separates the work into collection and evaluation, which makes the logic easier to test. It uses the same asymptotic cost as Approach 2, so you only pick it when clarity matters more than a small constant factor. Both approaches rely on array traversal and constant-time hash lookups.
Recommended for interviews: Interviewers expect you to start with the brute force, state its O(n^2) cost, and then move to the hash table version. The brute force shows you understand the definition. The single pass hash table solution shows you can compress the per-value history into a few numbers and reach O(n) time. Explain why the gap check only needs the last index, since that is the step interviewers probe most.
Solution
Thinking
The previous problem only handled exactly three occurrences. Here a value must appear at least three times, and every occurrence must lie on the same common difference. With
n = 10^5we cannot rescan the original array for each value.After grouping indices by value, the lists still have total length
n. If every adjacent gap equals the first gap, the whole sequence is an arithmetic progression.Grouping followed by a linear scan of each list is enough.
We use a hash table to record all indices where each integer appears. Traverse nums and append index i to the list of nums[i].
Then iterate over each index list pos in the hash table. Skip it if its length is less than 3. Otherwise let d = pos[1] - pos[0] and check whether every adjacent gap equals d. If so, the integer is special and we increment the answer by 1.
The time complexity is O(n) and the space complexity is O(n), where n is the length of nums.
class Solution:
def countSpecialIntegers(self, nums: list[int]) -> int:
g = defaultdict(list)
for i, x in enumerate(nums):
g[x].append(i)
ans = 0
for pos in g.values():
if len(pos) < 3:
continue
d = pos[1] - pos[0]
if all(j - i == d for i, j in pairwise(pos)):
ans += 1
return ansclass Solution {
public int countSpecialIntegers(int[] nums) {
Map<Integer, List<Integer>> g = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
g.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
}
int ans = 0;
for (List<Integer> pos : g.values()) {
if (pos.size() < 3) {
continue;
}
int d = pos.get(1) - pos.get(0);
boolean ok = true;
for (int i = 1; i < pos.size(); i++) {
if (pos.get(i) - pos.get(i - 1) != d) {
ok = false;
break;
}
}
if (ok) {
ans++;
}
}
return ans;
}
}class Solution {
public:
int countSpecialIntegers(vector<int>& nums) {
unordered_map<int, vector<int>> g;
for (int i = 0; i < nums.size(); i++) {
g[nums[i]].push_back(i);
}
int ans = 0;
for (auto& [x, pos] : g) {
if (pos.size() < 3) {
continue;
}
int d = pos[1] - pos[0];
bool ok = true;
for (int i = 1; i < pos.size(); i++) {
if (pos[i] - pos[i - 1] != d) {
ok = false;
break;
}
}
if (ok) {
ans++;
}
}
return ans;
}
};function countSpecialIntegers(nums: number[]): number {
const g = new Map<number, number[]>();
for (let i = 0; i < nums.length; i++) {
if (!g.has(nums[i])) {
g.set(nums[i], []);
}
g.get(nums[i])!.push(i);
}
let ans = 0;
for (const pos of g.values()) {
if (pos.length < 3) {
continue;
}
const d = pos[1] - pos[0];
let ok = true;
for (let i = 1; i < pos.length; i++) {
if (pos[i] - pos[i - 1] !== d) {
ok = false;
break;
}
}
if (ok) {
ans++;
}
}
return ans;
}func countSpecialIntegers(nums []int) int {
g := make(map[int][]int)
for i, x := range nums {
g[x] = append(g[x], i)
}
ans := 0
for _, pos := range g {
if len(pos) < 3 {
continue
}
d := pos[1] - pos[0]
ok := true
for i := 1; i < len(pos); i++ {
if pos[i]-pos[i-1] != d {
ok = false
break
}
}
if ok {
ans++
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan Per Value | O(n^2) | O(n) | Small inputs or verifying the definition |
| Hash Table with Per-Value State | O(n) | O(n) | General case and interview answer |
| Single Pass with Counting Summary | O(n) | O(n) | When you want separate collection and evaluation steps |
Frequently asked questions
Count Values With Equally Spaced Occurrences II Python solution
A Python solution uses a dict mapping each value to its last index and gap, then loops through the array once with enumerate. Each lookup and update is O(1) on average, so the full solution is O(n) time and O(n) space. FleetCode provides the Python version alongside Java and C++.
Is Count Values With Equally Spaced Occurrences II easy or hard?
It is a Medium problem. The hash table idea is straightforward once you see that two numbers per value are enough to check spacing. The difficulty comes from proving the gap logic is correct and handling edge cases like values that appear only once.
How to solve Count Values With Equally Spaced Occurrences II in O(n)?
Store per-value state in a hash table during a single traversal. For each index, compare the distance from the value's last occurrence to its stored gap, and mark the value as broken on any mismatch. Count the values that are never broken at the end.
What is the best approach for Count Values With Equally Spaced Occurrences II?
The best approach is a hash table that tracks, for each value, its last index, its common gap, and whether the spacing still holds. You process the array in one pass, which gives O(n) time and O(n) extra space.
What data structure is used in Count Values With Equally Spaced Occurrences II?
The main data structure is a hash table (dictionary or map) keyed by value, storing the last index and gap for each value. The input itself is an array that you traverse once.
What is the time complexity of Count Values With Equally Spaced Occurrences II?
The optimal solution runs in O(n) time because each element is read once and each hash table operation is average O(1). A brute force version that rescans the array for every value runs in O(n^2) time.
Is Count Values With Equally Spaced Occurrences II asked at Google, Amazon, or Meta?
This problem is tagged as Array and Hash Table on FleetCode, and it is a Medium difficulty problem with a 62.9% acceptance rate. Company-specific frequency data changes over time, so check recent interview reports on your target company's question bank before preparing.