Windows dominated by one topic

Scenario

A social app tags every post with a topic id. A feed feels repetitive when one topic takes over a stretch of it. The ranking team uses a simple rule: a window of k consecutive posts is dominated when one topic fills more than half of it.

Before they ship a new ranking version, the team replays real feeds through it. For each feed, they count the dominated windows. A version that produces many of them goes back for more work on topic balance.

Your task

Write count_dominated(topics, k).

topics[i] is the topic id of post i in the feed, in order, and 1 ≤ k ≤ topics.length.
A window is any k consecutive posts. There are n − k + 1 windows, and they overlap.
A window is dominated when some topic appears in it more than k / 2 times, that is, when its count × 2 > k. Exactly half is not enough.
Return the number of dominated windows.

Examples

Example 1 (traced)#

text2 lines

Input:  topics = [2, 5, 2, 2, 7, 5, 5, 5], k = 4
Output: 2

A topic dominates a window of 4 posts when it fills 3 or more of them.

right	Leaves	Joins	Posts in the window	Counts	over	Dominated windows
0 to 2	none	2, 5, 2	not full yet	2→2, 5→1	0	0
3	none	2	2, 5, 2, 2	2→3, 5→1	1	1
4	2	7	5, 2, 2, 7	2→2, 5→1, 7→1	0	1
5	5	5	2, 2, 7, 5	2→2, 5→1, 7→1	0	1
6	2	5	2, 7, 5, 5	2→1, 5→2, 7→1	0	1
7	2	5	7, 5, 5, 5	5→3, 7→1	1	2

Topic 2 dominates the first window and topic 5 the last. The windows in between hold at most 2 posts of one topic, which is exactly half.

Example 2#

text2 lines

Input:  topics = [4, 9, 4], k = 1
Output: 3

A window of one post is always dominated by its own topic.

Example 3#

text2 lines

Input:  topics = [1, 2, 1, 2], k = 2
Output: 0

Every window holds one post of each topic. One of two is exactly half, so no window is dominated.

Constraints

1 ≤ k ≤ topics.length ≤ 10^5
1 ≤ topics[i] ≤ 10^5

What does n ≤ 10^5 tell you?

Counting every window from scratch costs (n − k + 1) × k steps. With n = 10^5 and k = 5 × 10^4, that is about 2.5 × 10^9 steps, far over the time limit. Aim for O(n).

The window can hold up to 10^5 topics, so finding its largest count by scanning the map is also too slow. You need to know whether some topic is above half without looking at every topic.

Scenario

Your task

Write count_dominated(topics, k).

topics[i] is the topic id of post i in the feed, in order, and 1 ≤ k ≤ topics.length.
A window is any k consecutive posts. There are n − k + 1 windows, and they overlap.
A window is dominated when some topic appears in it more than k / 2 times, that is, when its count × 2 > k. Exactly half is not enough.
Return the number of dominated windows.

Examples

Example 1 (traced)#

text2 lines

Input:  topics = [2, 5, 2, 2, 7, 5, 5, 5], k = 4
Output: 2

A topic dominates a window of 4 posts when it fills 3 or more of them.

right	Leaves	Joins	Posts in the window	Counts	over	Dominated windows
0 to 2	none	2, 5, 2	not full yet	2→2, 5→1	0	0
3	none	2	2, 5, 2, 2	2→3, 5→1	1	1
4	2	7	5, 2, 2, 7	2→2, 5→1, 7→1	0	1
5	5	5	2, 2, 7, 5	2→2, 5→1, 7→1	0	1
6	2	5	2, 7, 5, 5	2→1, 5→2, 7→1	0	1
7	2	5	7, 5, 5, 5	5→3, 7→1	1	2

Topic 2 dominates the first window and topic 5 the last. The windows in between hold at most 2 posts of one topic, which is exactly half.

Example 2#

text2 lines

Input:  topics = [4, 9, 4], k = 1
Output: 3

A window of one post is always dominated by its own topic.

Example 3#

text2 lines

Input:  topics = [1, 2, 1, 2], k = 2
Output: 0

Every window holds one post of each topic. One of two is exactly half, so no window is dominated.

Constraints

1 ≤ k ≤ topics.length ≤ 10^5
1 ≤ topics[i] ≤ 10^5

What does n ≤ 10^5 tell you?

Counting every window from scratch costs (n − k + 1) × k steps. With n = 10^5 and k = 5 × 10^4, that is about 2.5 × 10^9 steps, far over the time limit. Aim for O(n).

The window can hold up to 10^5 topics, so finding its largest count by scanning the map is also too slow. You need to know whether some topic is above half without looking at every topic.