Supermarket Savings

Overview

The problem asks us to compare two different shopping strategies:

1. Sequential Strategy: Following the shoppingList exactly as written.
2. Grouped Strategy: Grouping all items by their department so that each unique department is visited exactly once.

A "visit" occurs when you enter a department. If two consecutive items on your list are in the same department, it only counts as one visit. The goal is to calculate the difference in the number of visits between these two strategies.

Brute Force

In a brute force approach, we can directly simulate the shopping process. To do this efficiently, we first need a way to quickly look up which department a product belongs to. We can use a dictionary to map each productName to its department.

For the Sequential Strategy, we iterate through the shoppingList and keep track of the "current" department. Every time the department changes from the previous item, we increment our visit counter.

For the Grouped Strategy, the problem statement simplifies this: we visit each unique department exactly once. Therefore, the number of visits is simply the count of unique departments present in the shoppingList.

def supermarket_savings(products: list[list[str]], shoppingList: list[str]) -> int:
    # Map products to departments
    prod_to_dept = {}
    for name, dept in products:
        prod_to_dept[name] = dept
        
    # Calculate Sequential visits
    sequential_visits = 0
    last_dept = None
    
    # We need to find the departments for each item in the shopping list
    dept_sequence = []
    for item in shoppingList:
        dept_sequence.append(prod_to_dept[item])
        
    for dept in dept_sequence:
        if dept != last_dept:
            sequential_visits += 1
            last_dept = dept
            
    # Calculate Grouped visits (number of unique departments in the shopping list)
    unique_depts = set(dept_sequence)
    grouped_visits = len(unique_depts)
    
    return sequential_visits - grouped_visits

Time complexity: O(N + M) — Where N is the number of products and M is the length of the shopping list; we iterate through both lists to build the map and the department sequence. Space complexity: O(N + M) — We store a dictionary of N products and a sequence list of M departments.

Optimal Approach

The optimal approach follows the same logic as the brute force but focuses on memory efficiency and clean iteration. We don't need to store the entire dept_sequence list. Instead, we can calculate the sequential_visits and identify unique departments in a single pass over the shoppingList.

1. Map Creation: Create a hash map (dictionary) for $O(1)$ lookups of department names.
2. Single Pass: Iterate through the shoppingList.
   • Maintain a set to track unique departments encountered.
   • Compare the current item's department with the previous_dept variable to count transitions.
3. Result: Subtract the size of the unique departments set from the sequential visit count.

def supermarket_savings(products: list[list[str]], shoppingList: list[str]) -> int:
    # Quick lookup for product departments
    mapping = {name: dept for name, dept in products}
    
    sequential_visits = 0
    unique_depts = set()
    prev_dept = None
    
    for item in shoppingList:
        current_dept = mapping[item]
        
        # Track unique departments for the Grouped Strategy
        unique_depts.add(current_dept)
        
        # Increment visits only if we switch departments
        if current_dept != prev_dept:
            sequential_visits += 1
            prev_dept = current_dept
            
    return sequential_visits - len(unique_depts)

Time complexity: O(N + M) — We perform one pass over the products list to create the map and one pass over the shopping list. Space complexity: O(N + D) — We store N products in the dictionary and D unique departments in a set (where D ≤ M).

Why this works

The logic relies on the definition of a "visit." In the sequential version, the sequence ["Dairy", "Dairy", "Produce"] results in 2 visits because the transition from Dairy to Dairy is ignored. Mathematically, this is equivalent to counting blocks of identical consecutive elements. In the grouped version, we are guaranteed the minimum possible visits, which is exactly one visit per unique department required.

Fast