Maximum Spending After Buying Items - Practice Coding Problems

Maximum Spending After Buying Items - Problem

You are given a 0-indexed m × n integer matrix values, representing the values of m × n different items in m different shops. Each shop has n items where the j^th item in the i^th shop has a value of values[i][j].

Additionally, the items in the i^th shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.

On each day, you would like to buy a single item from one of the shops. Specifically, on the d^th day you can:

Pick any shop i
Buy the rightmost available item j for the price of values[i][j] × d

That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] × d.

Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.

Return the maximum amount of money that can be spent on buying all m × n products.

Input & Output

Example 1 — Basic 2×2 Matrix

$ Input: values = [[8,5],[9,4]]

› Output: 74

💡 Note: Items available: 8,5,9,4. Optimal strategy: buy smallest items first to save larger values for later days with higher multipliers. Day 1: buy 4×1=4, Day 2: buy 5×2=10, Day 3: buy 8×3=24, Day 4: buy 9×4=36. Total: 4+10+24+36=74

Example 2 — Single Row

$ Input: values = [[10,8,6,4,2]]

› Output: 110

💡 Note: One shop with 5 items in decreasing order. Buy in reverse order: Day 1: buy 2×1=2, Day 2: buy 4×2=8, Day 3: buy 6×3=18, Day 4: buy 8×4=32, Day 5: buy 10×5=50. Total: 2+8+18+32+50=110

Example 3 — Single Column

$ Input: values = [[5],[3],[4]]

› Output: 23

💡 Note: Three shops with one item each: 5,3,4. Sort: [3,4,5]. Day 1: buy 3×1=3, Day 2: buy 4×2=8, Day 3: buy 5×3=15. Total: 3+8+15=26

Constraints

1 ≤ m, n ≤ 1000
1 ≤ values[i][j] ≤ 10⁶
values[i][j] ≥ values[i][j + 1] for all valid i, j

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with item values, each row sorted descending

Strategy

Buy cheapest items first to save expensive items for later days

Result

Maximum total spending achieved

Key Takeaway

🎯 Key Insight: Buy cheapest items first so expensive items get multiplied by larger day numbers

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Meta 18

The key insight is to buy items with smallest values first so that expensive items get multiplied by larger day numbers. Best approach is sort all items then buy in ascending order. Time: O(m×n×log(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Sequences	O((m×n)!)	O(m×n)	Generate all possible buying sequences and find the one with maximum total spending
Greedy - Min Heap Approach	O(m×n×log(m×n))	O(m×n)	Use a min-heap to always buy the smallest available item first, saving larger values for later days
Sort All Items	O(m×n×log(m×n))	O(m×n)	Extract all items into a single array, sort by value, then buy from smallest to largest

Brute Force - Try All Sequences — Algorithm Steps

Step 1: For each day, iterate through all shops and their available rightmost items
Step 2: Recursively try buying each item and explore remaining days
Step 3: Return the maximum total spending among all sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Day 1

Try buying each available item from any shop

Recurse

For each choice, recursively solve remaining days

Maximum

Return the sequence with highest total spending

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_M 10
#define MAX_N 10

long long backtrack(int day, bool purchased[MAX_M][MAX_N], int values[MAX_M][MAX_N], int m, int n, int totalItems) {
    if (day > totalItems) return 0;
    
    long long maxSpending = 0;
    for (int i = 0; i < m; i++) {
        // Find rightmost available item in shop i
        for (int j = n - 1; j >= 0; j--) {
            if (!purchased[i][j]) {
                // Buy this item
                purchased[i][j] = true;
                long long currentSpending = (long long)values[i][j] * day + backtrack(day + 1, purchased, values, m, n, totalItems);
                if (currentSpending > maxSpending) {
                    maxSpending = currentSpending;
                }
                purchased[i][j] = false;
                break;
            }
        }
    }
    return maxSpending;
}

long long solution(int values[MAX_M][MAX_N], int m, int n) {
    int totalItems = m * n;
    bool purchased[MAX_M][MAX_N] = {false};
    return backtrack(1, purchased, values, m, n, totalItems);
}

int main() {
    int values[MAX_M][MAX_N];
    int m = 2, n = 2; // Example dimensions
    values[0][0] = 8; values[0][1] = 5;
    values[1][0] = 9; values[1][1] = 4;
    
    printf("%lld\n", solution(values, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((m×n)!)

For each day we have up to m×n choices, leading to factorial time complexity

✓ Linear Growth

Space Complexity

O(m×n)

Recursion depth is m×n levels deep, plus space to track purchased items

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Sequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler