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.

Description Hints 1 Solution Video 8:05

4049. Count Values With Equally Spaced Occurrences II

Medium62.9% acceptance

You are given an integer array nums.

An integer x is called special if:

x appears at least three times in nums.
All occurrences of x are equally spaced in nums. In other words, if all occurrences of x are at indices i₁ < i₂ < ... < i_m, then i₂ - i₁ = i₃ - i₂ = ... = i_m - i_m-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 <= 10⁵
1 <= nums[i] <= 10⁹

Topics

Array Hash Table

Hints open one at a time

Hint 1

Use a hash map to group occurrence indices by value. A value is special if its group contains at least three indices and every consecutive gap equals the first gap.

8:05

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

4049. Count Values With Equally Spaced Occurrences II

Topics

Hints open one at a time

Similar problems