Welcome to Subscribe On Youtube

4049. Count Values With Equally Spaced Occurrences II

Description

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 i1 < i2 < ... < im, then i2 - i1 = i3 - i2 = ... = im - im-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 <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Hash Table

Thinking

The previous problem only handled exactly three occurrences. Here a value must appear at least three times, and every occurrence must lie on the same common difference. With $n = 10^5$ we cannot rescan the original array for each value.

After grouping indices by value, the lists still have total length $n$. If every adjacent gap equals the first gap, the whole sequence is an arithmetic progression.

Grouping followed by a linear scan of each list is enough.

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. Skip it if its length is less than $3$. Otherwise let $d = \textit{pos}[1] - \textit{pos}[0]$ and check whether every adjacent gap equals $d$. If so, 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) {
                continue;
            }

            int d = pos.get(1) - pos.get(0);
            boolean ok = true;
            for (int i = 1; i < pos.size(); i++) {
                if (pos.get(i) - pos.get(i - 1) != d) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                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) {
                continue;
            }

            int d = pos[1] - pos[0];
            bool ok = true;
            for (int i = 1; i < pos.size(); i++) {
                if (pos[i] - pos[i - 1] != d) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                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)
        ans = 0
        for pos in g.values():
            if len(pos) < 3:
                continue
            d = pos[1] - pos[0]
            if all(j - i == d for i, j in pairwise(pos)):
                ans += 1
        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 {
			continue
		}

		d := pos[1] - pos[0]
		ok := true
		for i := 1; i < len(pos); i++ {
			if pos[i]-pos[i-1] != d {
				ok = false
				break
			}
		}

		if ok {
			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) {
            continue;
        }

        const d = pos[1] - pos[0];
        let ok = true;
        for (let i = 1; i < pos.length; i++) {
            if (pos[i] - pos[i - 1] !== d) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    return ans;
}

All Problems

All Solutions