Subarray with Maximum Target Frequency

Overview

The goal is to find a contiguous subarray of a fixed length (windowSize) that contains the highest number of occurrences of a specific "target value." This target value is defined by the element at nums[targetIndex].

If multiple subarrays share the same maximum frequency, we are required to return the smallest starting index. This tie-breaking rule suggests we should process the array from left to right and only update our result if we find a frequency strictly greater than our current maximum.

Brute Force

The brute force approach involves checking every possible starting index $i$ for a subarray of length windowSize. For each starting index, we iterate through the $k$ elements ($k = \text{windowSize}$) and count how many times the target value appears.

1. Identify the target value: target = nums[targetIndex].
2. Loop through every valid starting index $i$ from $0$ to $n - \text{windowSize}$.
3. For each $i$, slice the array or loop from $i$ to $i + \text{windowSize}$ to count occurrences of target.
4. Keep track of the maximum count found and the corresponding index.

def max_target_frequency_subarray(nums: list[int], targetIndex: int, windowSize: int) -> int:
    target = nums[targetIndex]
    n = len(nums)
    max_count = -1
    best_index = 0
    
    # Check every possible starting position
    for i in range(n - windowSize + 1):
        current_count = 0
        # Count target in the current window [i, i + windowSize)
        for j in range(i, i + windowSize):
            if nums[j] == target:
                current_count += 1
        
        # Update if we find a strictly better frequency
        if current_count > max_count:
            max_count = current_count
            best_index = i
            
    return best_index

Time complexity: O(N * K) — where N is the length of the array and K is the windowSize, as we iterate over the window for every possible start position. Space complexity: O(1) — we only store a few integer variables regardless of input size.

Optimal / Best Approach (Sliding Window)

We can optimize the counting process using the Sliding Window technique. Instead of re-counting the target value from scratch for every position, we observe that moving the window one step to the right only changes two elements:

1. The element that leaves the window (at the back).
2. The element that enters the window (at the front).

By maintaining a running current_count, we can update it in $O(1)$ time per shift.

1. Initialize current_count by counting occurrences of target in the first window (indices $0$ to windowSize - 1).
2. Set max_count = current_count and best_index = 0.
3. Slide the window from index $1$ up to $n - \text{windowSize}$.
4. For each step:
   • If the element leaving (nums[i-1]) was the target, decrement current_count.
   • If the element entering (nums[i + windowSize - 1]) is the target, increment current_count.
   • If current_count > max_count, update max_count and best_index.

def max_target_frequency_subarray(nums: list[int], targetIndex: int, windowSize: int) -> int:
    target = nums[targetIndex]
    n = len(nums)
    
    # 1. Calculate the count for the very first window
    current_count = 0
    for i in range(windowSize):
        if nums[i] == target:
            current_count += 1
            
    max_count = current_count
    best_index = 0
    
    # 2. Slide the window across the rest of the array
    for i in range(1, n - windowSize + 1):
        # Element leaving the window
        if nums[i - 1] == target:
            current_count -= 1
        
        # Element entering the window
        if nums[i + windowSize - 1] == target:
            current_count += 1
            
        # Update only on strictly greater to maintain the minimum starting index
        if current_count > max_count:
            max_count = current_count
            best_index = i
            
    return best_index

Time complexity: O(N) — we traverse the array once to initialize the window and once more to slide it across. Space complexity: O(1) — we perform the calculations in-place using a constant amount of extra space.

Why this works

The sliding window technique is ideal here because the "property" we are tracking (count of a specific value) is incrementally updatable. Since the problem asks for the minimum starting index in case of ties, our loop naturally handles this by only updating best_index when we find a count that is strictly higher than any seen previously. If a later window has the same count as the current max_count, the if current_count > max_count condition fails, leaving the earlier (smaller) index as the result.

Fast