Welcome to Subscribe On Youtube

4048. Count Values With Equally Spaced Occurrences I

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}$.

  • 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;
    }
};

  • 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()
        )


  • 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
}


  • 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;
}

All Problems

All Solutions