Time Complexity: O(n), where n is the length of the input array. The sliding window expands and contracts over the array. Each element is processed at most twice, once when the right pointer includes it in the window and possibly again when the left pointer removes it. Hence, the overall traversal is linear in time.

Space Complexity: O(1), constant auxiliary space. Although we use a hash map to keep track of the count of fruit types in the current window, it holds at most two keys (since we’re allowed only two types of fruits). Therefore, the space usage remains constant and does not scale with input size.

Optimal Approach

Algorithm

In this optimal approach, instead of storing counts of all fruit types using a map, we keep track of just the last two fruit types seen and their last positions. This allows us to avoid using any auxiliary space like a hash map. The idea is simple: we maintain a sliding window that only contains two types of fruits and expand it as long as the new fruit belongs to either of those two types. If a new third type appears, we shrink the window to start right after the last occurrence of the second last fruit type.

Initialize two variables to store the two recent fruit types seen and their last positions.
Traverse the array while expanding the window to include current fruits as long as they match the two types.
If a third fruit type appears, update the window to start just after the last occurrence of one of the older fruit types.
Track the maximum length of valid windows throughout the traversal.