4048. Count Values with Equally Spaced Occurrences I

Problem Statement

4048. Count Values With Equally Spaced Occurrences I

Easy

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 i₁ < i₂ < i₃, then i₂ - i₁ = i₃ - i₂.

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

Java

Source file

class Solution {
    public int countSpecialIntegers(int[] nums) {
        int[] freq = new int[101];
        int[] last = new int[101];
        int[] spacing = new int[101];
        boolean[] impossible = new boolean[101];
        for (int i = 0; i < nums.length; i++) {
            if (++freq[nums[i]] == 2)
                spacing[nums[i]] = i - last[nums[i]];
            else if (freq[nums[i]] > 2 && spacing[nums[i]] != i - last[nums[i]])
                impossible[nums[i]] = true;
            else if (freq[nums[i]] > 3)
                impossible[nums[i]] = true;
            last[nums[i]] = i;
        }
        int ans = 0;
        for (int i = 0; i <= 100; i++)
            if (freq[i] == 3 && !impossible[i])
                ans++;
        return ans;
    }
}