Skip to content

4049. Count Values With Equally Spaced Occurrences II

DifficultyMedium

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}\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}

Comments