Array Element Repeater — Problem Statement & Solution Guide

ArraysEasy1 task / each of 2 patterns: Easy + Medium

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Array Element Repeater problem optimally.

TopicArrays

Pattern1 task / each of 2 patterns: Easy + Medium

TimeO(n)

SpaceO(1)

Problem Description

Given an array of integers nums and an integer k, find the zero-based starting index of the first contiguous run of identical elements whose total length is exactly k.

More formally, a contiguous run starting at index i of length len is a segment nums[i ... i + len - 1] where all elements are equal, and if i > 0, nums[i - 1] != nums[i], and if i + len < nums.length, nums[i + len] != nums[i].

If multiple runs of length exactly k exist, return the starting index of the one that appears earliest in the array. If no run of length exactly k exists, return -1.

DSA Pattern Breakdown

"Array Element Repeater"

easy

WHY DOES IT MATTER?

Detecting exact‑length runs is a fundamental pattern for problems involving grouping, compression, and frequency analysis. Mastery of this pattern enables candidates to efficiently solve a wide class of array‑based questions without resorting to brute‑force nested loops.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that you only need to track the length of the current homogeneous segment and its start index. By updating a single counter as you iterate, you avoid recomputing lengths for overlapping segments, collapsing an O(n²) solution to O(n).

REAL-WORLD CONNECTION

Think of a log‑processing pipeline that needs to trigger an alert when a specific error code appears exactly k times in a row. The algorithm mirrors how streaming systems detect such patterns in real time without buffering the entire log.

During an interview, write the loop that increments a streak counter and resets it when the value changes. Immediately after incrementing, check if the streak equals k and that the element before the streak (if any) is different – this one‑line condition captures the entire problem.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to detecting a maximal run of equal values in a one‑dimensional array and checking whether any sub‑run of exactly length k exists at the start of such a run. A naive scan that, for each index, expands forward until a different element appears leads to O(n²) time in the worst case (e.g., an array of identical elements). The optimal paradigm leverages a single pass while maintaining a running count of the current streak. When the streak length reaches k, we verify that the element before the streak (if any) differs, guaranteeing that the run is the first occurrence of a contiguous block of exactly k identical numbers. This linear‑time, constant‑space approach is essentially a specialized form of run‑length encoding performed on the fly.

Run‑length encoding (RLE) is a classic compression technique that groups consecutive identical items. By treating the array as a stream and updating a counter whenever the current element matches the previous one, we can compute the length of each run without storing the entire encoding. The key insight is that we only need to know the length of the current run and whether it started at a boundary where the previous element differs. This eliminates the need for nested loops or auxiliary data structures, yielding O(n) time and O(1) extra space, which scales gracefully to very large inputs.

Interview Questions on This Problem

Q1How would you modify the solution if you needed to return all starting indices of runs whose length is exactly k, instead of just the first one?

Maintain the same single‑pass logic but, each time the current run length equals k, record the start index. If the run continues beyond k, discard the previously recorded index because the run is longer than k. Continue scanning to capture subsequent runs. This still runs in O(n) time and O(1) extra space (aside from the output list).

Q2Can you solve the problem using a sliding window of size k? What are the pitfalls?

A sliding window can check each length‑k segment for uniformity, but naïvely recomputing uniformity costs O(k) per window, leading to O(n·k). To achieve O(n), you must maintain a count of distinct values inside the window, which essentially replicates the run‑length counter. The pitfall is forgetting to handle windows that span the boundary of two different runs, causing false positives.

Q3What changes are required if the array is sorted in non‑decreasing order?

If the array is sorted, identical elements are already grouped, so you can binary‑search for the first occurrence of each distinct value and compute its frequency via upper and lower bounds. This yields O(m log n) where m is the number of distinct values, which may be better than O(n) when m ≪ n, but the linear scan remains simpler and optimal for unsorted inputs.

Examples

Example 1

Input

nums = [1, 4, 4, 4, 2, 2, 3], k = 3

Output

Explanation: The contiguous runs of identical elements are [1] (length 1, index 0), [4, 4, 4] (length 3, index 1), [2, 2] (length 2, index 4), and [3] (length 1, index 6). The first run of length exactly 3 starts at index 1.

Example 2

Input

nums = [5, 5, 5, 5, 1, 2, 2], k = 2

Output

Explanation: The contiguous runs are [5, 5, 5, 5] (length 4), [1] (length 1), and [2, 2] (length 2, index 5). The run of 5s has length 4, which is not equal to 2. The first run with length exactly 2 starts at index 5.

Example 3

Input

nums = [7, 7, 7], k = 3

Output

Explanation: The entire array forms a single contiguous run of length 3 starting at index 0.

Example 4

Input

nums = [3, 3, 3, 3], k = 2

Output

-1

Explanation: The only run has length 4. There is no contiguous run of length exactly 2.

Example 5

Input

nums = [-1, -1, 0, 8, 8, 8, -1, -1], k = 2

Output

Explanation: The runs of length 2 are [-1, -1] at index 0 and [-1, -1] at index 6. The first run of length 2 starts at index 0.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= nums.length

Optimal Approach & Strategy

Traverse the array once, maintaining a running count of the current identical segment and its start index; when the count reaches k and the previous element differs, return the start index – O(n) time, O(1) space.

Brute Force Approach

For each index, expand forward until a different value appears, then check if the run length equals k; repeat for all indices, leading to O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findRepeaterIndex(nums, k) {
    const n = nums.length;
    if (n === 0 || k <= 0) return -1;
    
    let start = 0;
    while (start < n) {
        let end = start;
        while (end < n && nums[end] === nums[start]) {
            end++;
        }
        if (end - start === k) {
            return start;
        }
        start = end;
    }
    
    return -1;
}

#include <iostream>
#include <vector>

using namespace std;

int findRepeaterIndex(const vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k <= 0) return -1;
    
    int start = 0;
    while (start < n) {
        int end = start;
        while (end < n && nums[end] == nums[start]) {
            end++;
        }
        if (end - start == k) {
            return start;
        }
        start = end;
    }
    
    return -1;
}

int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << findRepeaterIndex(nums, k) << endl;
    return 0;
}

import java.util.Scanner;

public class Solution {
    public static int findRepeaterIndex(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k <= 0) return -1;
        
        int start = 0;
        while (start < n) {
            int end = start;
            while (end < n && nums[end] == nums[start]) {
                end++;
            }
            if (end - start == k) {
                return start;
            }
            start = end;
        }
        
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(findRepeaterIndex(nums, k));
    }
}

def find_repeater_index(nums: list[int], k: int) -> int:
    n = len(nums)
    if n == 0 or k <= 0:
        return -1
    
    start = 0
    while start < n:
        end = start
        while end < n and nums[end] == nums[start]:
            end += 1
        if end - start == k:
            return start
        start = end
        
    return -1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findRepeaterIndex(nums, k) {
    const n = nums.length;
    if (n === 0 || k <= 0) return -1;
    
    let start = 0;
    while (start < n) {
        let end = start;
        while (end < n && nums[end] === nums[start]) {
            end++;
        }
        if (end - start === k) {
            return start;
        }
        start = end;
    }
    
    return -1;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.