Shopping Offers - Practice Coding Problems

Shopping Offers - Problem

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask Medium

In LeetCode Store, there are n items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given an integer array price where price[i] is the price of the i^th item, and an integer array needs where needs[i] is the number of pieces of the i^th item you want to buy.

You are also given an array special where special[i] is of size n + 1 where special[i][j] is the number of pieces of the j^th item in the i^th offer and special[i][n] (i.e., the last integer in the array) is the price of the i^th offer.

Return the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.

Input & Output

Example 1 — Basic Shopping

$ Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]

› Output: 14

💡 Note: Use special offer [3,0,5] to buy 3 items of type 0 for $5, then buy 2 items of type 1 individually for $10. Total: 5 + 10 = 14.

Example 2 — Multiple Offers

$ Input: price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]

› Output: 11

💡 Note: Use offer [1,1,0,4] once and buy remaining items individually: 4 + 3 + 4 = 11. This is cheaper than individual prices (2+6+4=12) or other combinations.

Example 3 — No Beneficial Offers

$ Input: price = [1,1], special = [[2,2,5]], needs = [2,2]

› Output: 4

💡 Note: The special offer costs $5 for [2,2] but buying individually costs only $4 (2×1 + 2×1). Choose individual purchases.

Constraints

n == price.length == needs.length
1 ≤ n ≤ 6
0 ≤ price[i], needs[i] ≤ 10
1 ≤ special.length ≤ 100
special[i].length == n + 1
0 ≤ special[i][j] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Items needed: [3,2], prices: [2,5], offers: [[3,0,5],[1,2,10]]

Decision Tree

Try different combinations of offers vs individual purchases

Optimal Cost

Find minimum: Use offer [3,0,5] + buy 2 type-1 items = 14

Key Takeaway

🎯 Key Insight: Use memoization to cache results for each shopping state and avoid redundant calculations

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to model this as a recursive decision problem where at each state we can either use available special offers or buy items individually. Memoization is crucial to avoid recalculating the same shopping states. The optimal approach uses dynamic programming with memoization. Time: O(k × ∏needs[i]), Space: O(∏needs[i])

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(k^m)	O(m)	Try all possible combinations of offers recursively without optimization
Memoization (Top-Down DP)	O(k × ∏needs[i])	O(∏needs[i])	Cache results for shopping states to avoid redundant calculations

Brute Force Recursion — Algorithm Steps

Step 1: Try each special offer if it doesn't exceed needs
Step 2: Recursively solve for remaining needs
Step 3: Compare with buying all items individually

Visualization

Tap to expand

Step-by-Step Walkthrough

Start State

Begin with original needs [3,2]

Try Offers

Recursively try each valid offer combination

Find Minimum

Return the minimum cost across all possibilities

Code -

solution.c — C

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

int min(int a, int b) {
    return a < b ? a : b;
}

int dfs(int* price, int priceSize, int** special, int specialSize, int* specialColSize, int* curNeeds) {
    // Base case: buy remaining items individually
    int minCost = 0;
    for (int i = 0; i < priceSize; i++) {
        minCost += curNeeds[i] * price[i];
    }
    
    // Try each special offer
    for (int i = 0; i < specialSize; i++) {
        // Check if we can use this offer
        int canUse = 1;
        for (int j = 0; j < priceSize; j++) {
            if (special[i][j] > curNeeds[j]) {
                canUse = 0;
                break;
            }
        }
        
        if (canUse) {
            // Use this offer and recurse
            int* newNeeds = (int*)malloc(priceSize * sizeof(int));
            for (int j = 0; j < priceSize; j++) {
                newNeeds[j] = curNeeds[j] - special[i][j];
            }
            int cost = special[i][specialColSize[i] - 1] + dfs(price, priceSize, special, specialSize, specialColSize, newNeeds);
            minCost = min(minCost, cost);
            free(newNeeds);
        }
    }
    
    return minCost;
}

int solution(int* price, int priceSize, int** special, int specialSize, int* specialColSize, int* needs, int needsSize) {
    return dfs(price, priceSize, special, specialSize, specialColSize, needs);
}

int main() {
    // Simple input parsing for demo
    int price[] = {2, 5};
    int priceSize = 2;
    
    int special0[] = {3, 0, 5};
    int special1[] = {1, 2, 10};
    int* special[] = {special0, special1};
    int specialSize = 2;
    int specialColSize[] = {3, 3};
    
    int needs[] = {3, 2};
    int needsSize = 2;
    
    int result = solution(price, priceSize, special, specialSize, specialColSize, needs, needsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^m)

k offers can be used up to m times where m is max(needs), leading to exponential combinations

✓ Linear Growth

Space Complexity

O(m)

Recursion stack depth up to maximum sum of needs

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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 Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler