Window with the most copies of a target value

The target is not given directly. It is nums[targetIndex], so read it once
up front. After that, the task is: among all windows of exactly windowSize
consecutive elements, find the one holding the most copies of the target,
breaking ties by the smallest start.

Brute force. For every start s from 0 to n - windowSize, count the
target in nums[s : s + windowSize]. That is O(n * k) for k = windowSize.
It is a fine opening line, and it makes the tie rule obvious, but every
window recounts k - 1 elements it shares with its neighbor.

Fixed-size sliding window. Adjacent windows differ by exactly two
elements: one leaves on the left, one enters on the right. So:

1. Count the target in the first window [0, k).
2. For each next start s, subtract 1 if nums[s - 1] was the target and
   add 1 if nums[s + k - 1] is the target.
3. Keep the best count and its start. Update only on a strictly larger
   count, so the earliest start wins ties for free.

Invariant: before checking start s, count equals the number of target
values in nums[s : s + k]. The update in step 2 keeps it true, and the
strict > keeps best_start as the smallest start with the best count.

Validate input first: an empty array, a targetIndex out of range, or a
windowSize outside [1, n] has no answer. Ask the interviewer which
behavior they want; this solution returns -1.

Note that the window containing targetIndex is not special. The answer
window does not have to include the position the target came from.

from typing import List


def most_target_window(nums: List[int], target_index: int, window_size: int) -> int:
    """Start index of the length-`window_size` window with the most copies of
    nums[target_index]. Ties go to the smallest start. Returns -1 when the
    input admits no window."""
    n = len(nums)
    if not (0 <= target_index < n) or not (1 <= window_size <= n):
        return -1

    target = nums[target_index]
    k = window_size

    count = sum(1 for x in nums[:k] if x == target)
    best_count, best_start = count, 0

    for start in range(1, n - k + 1):
        if nums[start - 1] == target:      # element leaving on the left
            count -= 1
        if nums[start + k - 1] == target:  # element entering on the right
            count += 1
        if count > best_count:             # strict: earliest start wins ties
            best_count, best_start = count, start

    return best_start


def most_target_window_brute(nums: List[int], target_index: int, window_size: int) -> int:
    """O(n * k) reference used to check the fast version."""
    n = len(nums)
    if not (0 <= target_index < n) or not (1 <= window_size <= n):
        return -1
    target = nums[target_index]
    best_count, best_start = -1, -1
    for s in range(n - window_size + 1):
        c = nums[s:s + window_size].count(target)
        if c > best_count:
            best_count, best_start = c, s
    return best_start


if __name__ == "__main__":
    import random

    assert most_target_window([4, 7, 1, 4, 4, 4, 2], 0, 3) == 3
    assert most_target_window([4, 7, 4, 1, 4, 4, 2], 0, 3) == 0
    assert most_target_window([9, 3, 3, 9, 3], 1, 2) == 1
    assert most_target_window([1, 2, 1, 2], 0, 2) == 0
    assert most_target_window([5], 0, 1) == 0
    assert most_target_window([8, 8, 8], 2, 3) == 0
    assert most_target_window([1, 2, 3], 5, 2) == -1
    assert most_target_window([1, 2, 3], 0, 4) == -1
    assert most_target_window([], 0, 1) == -1

    for _ in range(2000):
        n = random.randint(1, 15)
        arr = [random.randint(0, 3) for _ in range(n)]
        t = random.randrange(n)
        k = random.randint(1, n)
        assert most_target_window(arr, t, k) == most_target_window_brute(arr, t, k)
    print("ok")

• Time: O(n). The first window costs O(k), then each of the remaining
  n - k starts costs O(1).
• Space: O(1) extra. (The nums[:k] slice in the initial count is O(k);
  a plain index loop makes it O(1) if the interviewer cares.)
• Brute force: O(n * k) time, O(1) extra space.

• nums = [4, 7, 1, 4, 4, 4, 2], targetIndex = 0, windowSize = 3 -> 3
  (counts by start: 1, 1, 2, 3, 2).
• nums = [4, 7, 4, 1, 4, 4, 2], targetIndex = 0, windowSize = 3 -> 0
  (counts 2, 1, 2, 2, 2; four windows tie at 2, earliest wins).
• nums = [9, 3, 3, 9, 3], targetIndex = 1, windowSize = 2 -> 1
  (target 3; [3, 3] at start 1 is the only window with 2).
• nums = [1, 2, 1, 2], targetIndex = 0, windowSize = 2 -> 0
  (every window has one 1; tie goes to the smallest start).
• nums = [5], targetIndex = 0, windowSize = 1 -> 0.
• nums = [8, 8, 8], targetIndex = 2, windowSize = 3 -> 0
  (window covers the whole array).
• targetIndex out of range, windowSize > n, windowSize <= 0, or an
  empty array -> -1.

1. Return the count too, or every tied window. Return
   (best_start, best_count). For all ties, collect starts whose count
   equals the best; reset the list on a strictly larger count. Still O(n).
2. Many queries on one array (different targetIndex / windowSize).
   Precompute, for each distinct value, the sorted list of its positions
   p. For a query (v, k), use two pointers over p: for each left
   occurrence p[i], advance j while p[j] - p[i] < k, so the group
   p[i..j] fits in one window. The earliest start covering that group is
   max(0, p[j] - k + 1). Keep the largest group and, among equals, the
   smallest such start. Cost per query is O(occurrences of v) instead of
   O(n); if v never repeats, the answer is the earliest window holding
   its one copy.
3. Streaming input. Keep a deque (or ring buffer) of the last k
   elements and the running count. Each arriving element is O(1); report
   the best window seen so far by the start offset of the element stream.
4. Smallest window with at least m copies of the target. Collect the
   target's positions p; the answer is min(p[i + m - 1] - p[i] + 1).
   This flips the problem from fixed size to fixed count and is O(n).
5. Allow up to r replacements inside the window (turn non-targets into
   targets). With a fixed size k, the best count becomes
   min(k, count + r), so the earliest window with the most targets is still
   the answer. With a free window size, it becomes the classic "longest run
   after at most r flips" variable sliding window.

Mid-level (L4)

• Reads the target from nums[targetIndex] instead of treating
  targetIndex as a value.
• Gets to the O(n) sliding window, with brute force stated first.
• Handles ties by smallest start and tests the edge cases (window equals the
  array, size 1).

Senior (L5)

• States the window invariant and explains why strict > gives the earliest
  start.
• Raises input validation unprompted and agrees a contract (-1 or raise).
• Verifies against a brute-force reference, and handles follow-ups 1 and 4
  quickly.

Staff (L6+)

• Moves to the many-queries setting: per-value position lists, cost tied to
  occurrence count, and the subtle earliest-start bookkeeping.
• Discusses the streaming version and what changes with unbounded input.
• Keeps the code small and clear; discusses trade-offs rather than adding
  machinery the base problem does not need.