Sub-arrays with equal number of occurences

Given an array arr[] and two integers say, x and y, find the number of sub-arrays in which the number of occurrences of x is equal to the number of occurrences of y.

Examples:

Input: arr[] = [1, 2, 1] , x= 1 , y = 2
Output: 2
Explanation: The possible sub-arrays have same equal number of occurrences of x and y are:
1) [1, 2], x and y have same occurrence(1).
2) [2, 1], x and y have same occurrence(1).

Input: arr[] = [1, 2, 1] , x = 4 , y = 6
Output: 6
Explanation: The possible sub-arrays have same equal number of occurrences of x and y are:
1) [1], x and y have same occurrence(0).
2) [2], x and y have same occurrence(0).
3) [1], x and y have same occurrence(0).
4) [1, 2], x and y have same occurrence(0).
5) [2, 1], x and y have same occurrence(0).
6) [1, 2, 1], x and y have same occurrence(0).

Input: arr[] = [1, 2, 1] , x= 1 , y = 4
Output: 1
Explanation: The possible sub-array have same equal number of occurrences of x and y is: [2], x and y have same occurrence(0)

Constraints: 
1 <= arr.size() <= 10⁶
1 <= arr[i], x, y<=10⁶

Approach 01:

#include <unordered_map>
#include <vector>

class Solution {
public:
    static int sameOccurrence(std::vector<int>& arr, int x, int y) {
        std::unordered_map<int, int> diffMap; // Maps the difference of occurrences of x and y
        diffMap[0] = 1;  // Starting point when x and y have occurred the same number of times
        
        int difference = 0;
        int countOccurrences = 0;

        for (int num : arr) {
            if (num == x) {
                difference++;
            } else if (num == y) {
                difference--;
            }

            if (diffMap.find(difference) != diffMap.end()) {
                countOccurrences += diffMap[difference];
            }

            diffMap[difference]++;
        }

        return countOccurrences;
    }
};

class Solution:
    def sameOccurrence(self, arr, x, y):
        diffMap = {0: 1}  # Maps the difference of occurrences of x and y
        
        difference = 0
        countOccurrences = 0

        for num in arr:
            if num == x:
                difference += 1
            elif num == y:
                difference -= 1

            if difference in diffMap:
                countOccurrences += diffMap[difference]

            diffMap[difference] = diffMap.get(difference, 0) + 1

        return countOccurrences

Time Complexity

• Single pass through the array:

  The algorithm iterates over the array of size n exactly once. For each element, we perform constant time operations such as updating the difference and checking/updating the hash map. Thus, the time complexity for this iteration is \(O(n)\).

• Hash map operations:

  Both insertion and lookup operations in the hash map are performed in average constant time, i.e., \(O(1)\), assuming the hash map is balanced and there are no significant collisions.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the number of elements in the input array.

Space Complexity

• Hash map storage:

  The hash map stores the differences in occurrences between x and y. In the worst case, the difference can be unique for each prefix of the array, so the hash map could contain up to n entries. Thus, the space complexity for the hash map is \(O(n)\).

• Auxiliary Space:

  We use a constant amount of extra space for variables like difference and countOccurrences, which does not depend on the size of the input array.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where n is the size of the input array due to the storage used by the hash map.