Find Most Frequently Purchased Products
The manager of a grocery store tagGrocery wishes to determine which products are most popular with his customers (i.e. which products they purchase most frequently). The manager selects N customers who purchase a shopping bag of items containing M products, each labeled with a productID. By analyzing these M products, the manager wishes to find the productIDs of the distinct products that get purchased most frequently by at least K(given) customers.
Write an algorithm to help the manager find the productIDs of the products that are most frequently purchased by the K customers.
Input
- The first line of the input consists of two space-separated integers -
tag_row,tag_col, representing the number of customers (N), the number of products in the shopping bag of each customer (M). - The next
Nlines consist ofMspace-separated integers -tag[0],tag[1]..........,tag[M-1], representing theproductIDsof the products contained in the shopping bag of each customer. - The last line consists of an integer-
K_input, representing number ofKcustomers who are chosen by the manager (K).
Output
Print space-separated integers representing the lexicographically sorted productIDs of the products that are most frequently purchased by the K customers.
tag = [[1, 2, 3, 2], [2, 3, 4, 8], [8, 3, 11, 12], [2, 3, 6, 8]] K = 3 return = [2, 3, 8]
The products with ProductIDs 2, 3 and 8 are purchased by at least K customers.
So, the output is [2 3 8].
1 <= tag_row <= 10^31 <= tag_col <= 10^31 <= K_input < tag_row0 <= tag[0], tag[1], .........., tag[N-1] <= 10^9
public int[] findMostFrequentlyPurchasedProducts(int[][] tag, int K) {
// write your code here
}