Skip to content

4048. Count Values With Equally Spaced Occurrences I

DifficultyEasy

Description

You are given an integer array nums.

An integer x is called special if:

  • x appears exactly three times in nums.
  • All three occurrences of x are equally spaced in nums. In other words, if all occurrences of x are at indices i1 < i2 < i3, then i2 - 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 <= 100
  • 1 <= nums[i] <= 100

Solutions

Solution 1: Hash Table

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 \(\textit{nums}\) and append index \(i\) to the list of \(\textit{nums}[i]\).

Then iterate over each index list \(\textit{pos}\) in the hash table. If \(\textit{pos}\) has length \(3\) and \(\textit{pos}[0] + \textit{pos}[2] = 2 \times \textit{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 \(\textit{nums}\).

1
2
3
4
5
6
7
8
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()
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments