We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Longest Equal Subarray

Number: 2832

Difficulty: Medium

Paid? No

Companies: Bloomberg, Meesho, Palo Alto Networks

Problem Description

Given a 0-indexed integer array nums and an integer k, you are allowed to delete at most k elements from the array. After deletion, you need to form a contiguous subarray where all its elements are equal. Your task is to determine the length of the longest possible equal subarray that can be obtained after making at most k deletions. Note that the empty subarray is also considered equal.

Key Insights

  • The final equal subarray will consist of repeated instances of one particular number.
  • For a fixed number, if you know all its indices, you can try to “connect” a group of these indices into one contiguous block by removing the elements in between.
  • The required deletions for a block that spans positions i to j in the original array is (nums[j] - nums[i] + 1 - (number of occurrences within that block)).
  • For each unique number, maintain a list of the indices where it occurs, then use a sliding window on these indices to determine the maximum block that can be “glued together” with at most k deletions.
  • The overall answer is the maximum such block length among all unique numbers.

Space and Time Complexity

Time Complexity: O(n) overall, since each element is processed and every list of indices is slid over once. Space Complexity: O(n), for storing indices for each unique number.

Solution

We use a two-step approach:

  1. For each unique number in nums, record the positions at which it occurs.
  2. For each list of positions, apply a sliding window. For a window covering positions[i] to positions[j], the number of deletions required to “connect” these indices into a contiguous block is: (positions[j] - positions[i] + 1) - (j - i + 1) If this is <= k, then the window is valid.
  3. Track the maximum window size (i.e. the count of occurrences of a given number that can be joined after deletions) across all numbers.

This method leverages a hash table (or dictionary) to group indices and a sliding window (two pointers technique) to check the deletion constraint.

Code Solutions

# Python solution with detailed comments

def longestEqualSubarray(nums, k):
    from collections import defaultdict
    
    # Dictionary mapping each number to a list of indices where it appears
    pos_map = defaultdict(list)
    for i, num in enumerate(nums):
        pos_map[num].append(i)
    
    longest = 0
    # Process each unique number independently
    for num, positions in pos_map.items():
        left = 0  # left pointer for the sliding window over positions
        # Iterate with right pointer over positions list
        for right in range(len(positions)):
            # Compute needed deletions within the current window
            # positions[right] - positions[left] gives the span in the original array
            # (right - left + 1) is the count of occurrences (kept elements)
            # Their difference gives deletions needed.
            while positions[right] - positions[left] - (right - left) > k:
                # Not valid, move left pointer to shrink window
                left += 1
            # Update the maximum valid window size (i.e., subarray length)
            longest = max(longest, right - left + 1)
    return longest

# Example usage
print(longestEqualSubarray([1,3,2,3,1,3], 3))
← Back to All Questions