Max Distinct Counts After Splitting Array

Given an integer array, split it into two non-empty subarrays and maximise `distinct(left) + distinct(right)`. The expected solution updates left/right frequency structures in one pass. Requirements Input: an integer array arr of length n. Choose a split point i with 1 <= i < n. Let left = arr[0:i] and right = arr[i:n]. Output: the maximum value of countDistinct(left) + countDistinct(right) over all valid split points. Notes The brute-force approach recomputes distinct counts for every split and times out. Use a frequency map for the right side and a set or frequency map for the left side. Initialise the right map with every array element. Sweep the split point left-to-right, moving one element at a time from right to left, updating distinct counts incrementally. Time is O(n) and space is O(n). Preparation Practise the one-pass transfer pattern: initialise the right frequency map, move arr[i] to the left set, decrement/remove it on the right, and update the best after each valid non-empty split. Add tests where all values are equal, all values are distinct, and the optimal split is near an edge.