We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Spending After Buying Items

Number: 3107

Difficulty: Hard

Paid? No

Companies: Zomato

Problem Description

Given an m * n matrix "values" where each row represents a shop's items sorted in non-increasing order, you must purchase one item per day from any shop. On the dth day you select a shop and buy the rightmost (cheapest in that shop) available item at a cost equal to values[i][j] * d. The goal is to maximize the total spending when buying all m * n items.

Key Insights

  • Each shop’s items are sorted in non-increasing order so the rightmost available item is always the smallest remaining one.
  • To maximize spending, you want to delay buying higher-valued items to later days when the day multiplier is larger.
  • A greedy strategy can be employed: always purchase the current smallest available item across all shops, which defers the more expensive items.
  • A min-heap (priority queue) efficiently retrieves the shop with the smallest current item.

Space and Time Complexity

Time Complexity: O(m * n * log m) since there are m*n purchases and each heap operation on a heap of size m takes O(log m).
Space Complexity: O(m) for maintaining the min-heap.

Solution

The solution uses a greedy approach with a min-heap. Initially, insert the rightmost available item (the cheapest item) from each shop into the min-heap. Then, for each day from 1 to m*n, extract the smallest value from the heap and pay its cost multiplied by the current day. After each purchase, if the corresponding shop has another item available (to the left of the one just purchased), insert that next item into the heap. This ensures that expensive items are bought later when the day multiplier is higher.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

import heapq

def maximumSpending(values):
    m = len(values)
    n = len(values[0])
    # Heap stores tuple: (item_value, shop_index, item_index)
    heap = []
    # Push the rightmost (cheapest) item from each shop
    for shop in range(m):
        heapq.heappush(heap, (values[shop][n-1], shop, n-1))
    
    total_cost = 0
    day = 1
    
    # For each day, buy the cheapest available item.
    while heap:
        current_value, shop, index = heapq.heappop(heap)
        total_cost += current_value * day
        day += 1
        # If there is a next available item in the same shop, push it
        if index - 1 >= 0:
            heapq.heappush(heap, (values[shop][index-1], shop, index-1))
    
    return total_cost

# Example usage:
values = [[8,5,2], [6,4,1], [9,7,3]]
print(maximumSpending(values))  # Expected Output: 285
← Back to All Questions