Count Values With Equally Spaced Occurrences I solution and explanation
The problem
You are given an integer array nums.
An integer x is called special if:
xappears exactly three times innums.- All three occurrences of
xare equally spaced innums. In other words, if all occurrences ofxare at indicesi1 < i2 < i3, theni2 - i1 = i3 - i2.
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 exactly three times at equally spaced indices 0, 2, and 4.
- 5 is special because it occurs exactly three times 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: 0
Explanation:
8 is not special because it does not occur exactly three times. Therefore, the answer is 0.
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 <= 1001 <= nums[i] <= 100
Approach overview
Problem Overview: Count the number of distinct values that occur at equally spaced index positions in the given array. For example, in [1,2,1,2,1], the value 1 appears at indices [0,2,4] and 2 appears at [1,3]; both have constant gaps, so the answer is 2. A value that appears once has no gaps to compare, so it is counted by default. If your version of the problem needs at least two occurrences, simply add that check.
Approach 1: Brute Force Re-scan (O(n²) time, O(n) space)
For every distinct value in the array, scan the entire array again to collect its position list. Because the scan always goes left to right, the positions are sorted automatically. Then compare consecutive positions to verify that the gap is constant. This works but rescans the whole array for each distinct value. If the array contains many distinct values, the total work becomes O(n * u), which is O(n²) in the worst case. Use it only for very small test cases or as a quick mental model.
Approach 2: Hash Map with Index Lists (O(n) time, O(n) space)
A single pass through the array gives you a hash table that maps each value to a list of its indices. Since traversal is left to right, each list is already sorted. After building the map, iterate over every entry and check whether all adjacent index differences are the same. Hash map lookups average O(1), so building the table is O(n). The verification loop also visits each stored index once, keeping the total time O(n). This approach is the clearest grouping solution.
Approach 3: One-pass Gap Validation (O(n) time, O(n) space)
You don't need to store every index for every value. Store only the last index, the expected gap, and validity flag for each value. On the first occurrence, set lastIndex. On the second occurrence, compute the gap and store it. For each later occurrence, compare the new gap; if it differs, mark the value invalid. The space complexity is still O(n) because the hash map can contain a distinct entry per key, but each entry now stores a constant number of fields instead of a list. This is a refined version that many interviewers recognize as an optimization.
Recommended for interviews: Start with Approach 2. It is the most readable, easy to code bug-free, and clearly demonstrates the key insight: group indices by value, then check constant gaps. If the interviewer asks for a tighter, one-pass method, mention Approach 3. The brute force is acceptable only as a starting point. For more practice, explore related array traversal problems on FleetCode.
Solution
Thinking
n \le 100, so even scanning the array once per distinct value would pass. A special integer must appear exactly three times, and those three indices must form an arithmetic progression.After collecting the indices of each value, the check reduces to two facts: the list has length
3, and the first plus the last index equals twice the middle one.A hash table groups the indices in a single pass.
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. If pos has length 3 and pos[0] + pos[2] = 2 times pos[1] (the three occurrences are equally spaced), 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)
return sum(
len(pos) == 3 and pos[0] + pos[2] == pos[1] * 2 for pos in g.values()
)class 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 && pos.get(0) + pos.get(2) == pos.get(1) * 2) {
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 && pos[0] + pos[2] == pos[1] * 2) {
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 && pos[0] + pos[2] === pos[1] * 2) {
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 && pos[0]+pos[2] == pos[1]*2 {
ans++
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Re-scan | O(n²) | O(n) | Small inputs, first mental derivation |
| Hash Map with Index Lists | O(n) | O(n) | General case, clean readable solution |
| One-pass Gap Validation | O(n) | O(n) | Less stored data, in-depth interview discussion |
Frequently asked questions
Count Values With Equally Spaced Occurrences I Python solution?
In Python, use `defaultdict(list)` to store indices. After building the map, for each value check that the list is empty or all adjacent differences are same. For example: `d[v].append(i)` during the loop, then `all(l[i] - l[i-1] == l[1] - l[0] for i in range(2, len(l)))`. This is O(n) time.
Is Count Values With Equally Spaced Occurrences I easy or hard?
It is classified as an easy problem. The main logic is index grouping and comparing constant gaps, which requires only a hash map and a few loops. The only subtle part is deciding how to handle values that appear once or exactly twice.
How to solve Count Values With Equally Spaced Occurrences I in O(n)?
Use a hash map that maps each integer to a list of indices. During the first pass, append the current index to the list for that value. After that, iterate the map and confirm the adjacent index differences are constant. Each index is processed twice, so the total time is O(n).
What is the best approach for Count Values With Equally Spaced Occurrences I?
The best approach uses a hash map to store each value's list of indices and then checks all adjacent gaps equal the same. This runs in O(n) time and O(n) space. A one-pass gap-validation variant stores only the last index and expected gap, reducing per-value overhead while keeping O(n).
Is Count Values With Equally Spaced Occurrences I asked at Google/Amazon/Meta?
It is not a specific FAANG interview question, but the same hash map grouped index-pattern appears in many interview tasks. Interviewers use related variants to test data structure understanding and edge case handling. Therefore, solving this problem is useful practice for big tech interviews.
What data structure is used in Count Values With Equally Spaced Occurrences I?
A hash map (dictionary) is the core data structure. It maps each value to a list of index positions, or to a compact record with last index and gap. Hash maps provide average O(1) lookups, making the solution linear in the array size.
What is the time complexity of Count Values With Equally Spaced Occurrences I?
The optimal solution is O(n) time and O(n) space. The brute-force version that rescans the whole array for each distinct value is O(n²) time. Hash table lookups in the optimal solution average O(1).