Distinct Category Subarray Sum
MediumHash Map · Amazon
A shopper's browsing history is a list of product category ids, categories. For every contiguous subarray categories[i..j] (with i <= j), count how many distinct category ids it contains. Return the sum of these counts over all subarrays.
If categories is empty, return 0. The result can be much larger than 2^31.
Example 1
- Input:
- categories = [4, 7, 4, 4]
- Output:
- 15
- Explanation
- The four single-element subarrays contribute 1 each (4). The pairs
[4,7],[7,4],[4,4]contribute 2 + 2 + 1. Both triples contain 4 and 7 (2 each), and so does the whole array (2). Total: 4 + 5 + 4 + 2 = 15.
Example 2
- Input:
- categories = [2, 2, 2]
- Output:
- 6
- Explanation
- Every one of the 6 subarrays contains only the category 2, so each contributes 1.
Example 3
- Input:
- categories = [1, 2, 3]
- Output:
- 10
- Explanation
- All values differ, so each subarray contributes its length: 3 * 1 + 2 * 2 + 1 * 3 = 10.
Constraints
0 <= categories.length <= 10^51 <= categories[i] <= 10^9