Subarray with Equal Occurrences

January 11, 2024

Problem #

Given an array of integers nums and two integers x and y, find the length of the longest contiguous subarray where the number of occurrences of x is equal to the number of occurrences of y.

Example:

1. Input: nums = [1, 2, 2, 3, 1, 1, 3], x = 1, y = 3 Output: 6 Explanation: The longest subarray with equal occurrences of 1 and 3 is [2, 2, 3, 1, 1, 3].

Solution Approach #

The solution involves using a hashmap to keep track of the difference in counts of x and y at each index. The idea is to find two indices where this difference is the same, indicating an equal number of x and y between these indices.

Algorithm Steps #

1. Initialize a hashmap to store the frequency difference and its first occurrence index.
2. Iterate through the array, keeping track of the count difference between x and y.
3. Update the hashmap with the first occurrence of each count difference.
4. Whenever the same count difference occurs again, calculate the subarray length.
5. Keep track of the maximum length of such subarrays.
6. Return the maximum length found.

Code (Python) #

def longestSubarray(nums, x, y):
    count_diff = max_len = 0
    first_occurrence = {0: -1}

    for i, num in enumerate(nums):
        if num == x:
            count_diff += 1
        elif num == y:
            count_diff -= 1

        if count_diff in first_occurrence:
            max_len = max(max_len, i - first_occurrence[count_diff])
        else:
            first_occurrence[count_diff] = i

    return max_len

# Test the function
print(longestSubarray([1, 2, 2, 3, 1, 1, 3], 1, 3))  # Output: 6

Time Complexity #

O(n), where n is the length of the array. The array is traversed once.

Space Complexity #

O(n), for the hashmap storing the count differences and their first occurrences.