DSCPPAS275 - Editorial

editorial
,
1

Problem Statement:

Given an array arr consisting of only the integers 0, 1, and 2, the task is to find the number of contiguous subarrays that contain at least one occurrence of each integer (0, 1, and 2).

Approach:

To solve this problem, we can use the sliding window (two-pointer) technique in combination with a hashmap (or unordered_map) to efficiently count the number of valid subarrays that include at least one 0, 1, and 2. The key idea is to maintain a window that expands to include more elements and contracts when it has included at least one of each of the required numbers.

Time Complexity:

  • Time Complexity: The algorithm runs in O(N) time, where N is the length of the array. This is because each element is processed at most twice—once by the j pointer and once by the i pointer.

  • Space Complexity: The space complexity is O(1) in terms of the number of distinct elements (since countMap only stores counts for 0, 1, and 2).