FastPrep
Problem · Array

Sum of Distinct Categories

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

Your team at Amazon wants to develop a service that takes in an array of integers where the ith element represents the category of the product viewed by the customer and returns the sum of the number of distinct categories on all contiguous segments of the array.

Given an array of n integers, categories, find the sum of the numbers of distinct integers over all of its subarrays.

Note: A subarray is a contiguous part of an array.

For example, the subarrays of [1, 2, 3] are [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].

Function

sumOfDistinctCategories(categories: int[]) → int

Complete the function sumOfDistinctCategories in the editor.

sumOfDistinctCategories has the following parameter:

  1. int categories[n]: an array of integers

Returns

int: the sum of the numbers of distinct integers over all subarrays

Examples

Example 1

categories = [1, 2, 1]return = 9
Example 1 illustration

Constraints

  • 1 <= n <= 10^5
  • 1 <= categories[i] <= 10^9

More Amazon problems

drafts saved locally
public int sumOfDistinctCategories(int[] categories) {
  // write your code here
}
categories[1, 2, 1]
expected9
checking account