Find the Longest Equal Subarray - Practice Coding Problems

Find the Longest Equal Subarray - Problem

You are given a 0-indexed integer array nums and an integer k.

A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.

Return the length of the longest possible equal subarray after deleting at most k elements from nums.

A subarray is a contiguous, possibly empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,2,2,1], k = 2

› Output: 3

💡 Note: We can focus on element 1 which appears at positions [0,1,4]. To make subarray from index 0 to 4 all equal to 1, we need to delete the 2 elements at positions 2 and 3. Since 2 ≤ k, we can achieve a length of 3.

Example 2 — No Deletions Needed

$ Input: nums = [1,1,1,1], k = 1

› Output: 4

💡 Note: All elements are already equal, so no deletions needed. The longest equal subarray has length 4.

Example 3 — Limited Deletions

$ Input: nums = [1,2,1], k = 0

› Output: 1

💡 Note: With k=0, we cannot delete any elements. The longest equal subarray is any single element, with length 1.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ nums.length
0 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,1,2,2,1] with k=2 deletions allowed

Process

Focus on element 1, find longest window needing ≤k deletions

Output

Maximum length achievable is 3

Key Takeaway

🎯 Key Insight: Use sliding window on positions of each unique element to efficiently find the longest achievable equal subarray

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to focus on one element type at a time and use sliding window to find the longest subarray where we can make all elements equal by deleting at most k elements. Best approach uses sliding window for optimal O(n) time complexity by processing element positions efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window (Optimal)	O(n)	O(n)	Use sliding window for each unique element to find maximum length
Brute Force	O(n³)	O(1)	Check all possible subarrays and count deletions needed

Sliding Window (Optimal) — Algorithm Steps

Step 1: Collect positions of each unique element
Step 2: For each element, use sliding window on its positions
Step 3: Expand window while gaps between positions ≤ k
Step 4: Track maximum window size across all elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Positions

Collect positions of each unique element

Sliding Window

For each element, find longest valid window

Calculate Result

Track maximum window size across all elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUMS 1000
#define MAX_VAL 1000

int solution(int* nums, int numsSize, int k) {
    // Simple approach: for each unique element, collect its positions
    int maxLength = 0;
    
    // Try each element as the target
    for (int target_idx = 0; target_idx < numsSize; target_idx++) {
        int target = nums[target_idx];
        int positions[MAX_NUMS];
        int posCount = 0;
        
        // Collect all positions of this target element
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] == target) {
                positions[posCount++] = i;
            }
        }
        
        // Use sliding window on positions
        int left = 0;
        for (int right = 0; right < posCount; right++) {
            // Elements to delete = total span - elements we keep
            int totalSpan = positions[right] - positions[left] + 1;
            int elementsToKeep = right - left + 1;
            int elementsToDelete = totalSpan - elementsToKeep;
            
            // Shrink window if too many deletions needed
            while (elementsToDelete > k && left <= right) {
                left++;
                if (left <= right) {
                    totalSpan = positions[right] - positions[left] + 1;
                    elementsToKeep = right - left + 1;
                    elementsToDelete = totalSpan - elementsToKeep;
                }
            }
            
            if (left <= right && elementsToKeep > maxLength) {
                maxLength = elementsToKeep;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[MAX_NUMS];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element processed once, sliding window amortized O(n) per unique element

✓ Linear Growth

Space Complexity

O(n)

Hash map stores positions for each unique element

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler