LeetCode 3626 - Find Stores with Inventory Imbalance

This problem asks us to identify stores with an inventory imbalance. Specifically, for each store, we need to compare the quantity of the most expensive product against the quantity of the cheapest product.

leetcodemedium

LeetCode Problem 3626

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to identify stores with an inventory imbalance. Specifically, for each store, we need to compare the quantity of the most expensive product against the quantity of the cheapest product. A store is considered imbalanced if the most expensive product has fewer units in stock than the cheapest product. Additionally, we need to calculate the imbalance ratio as cheapest_quantity / most_expensive_quantity, rounded to two decimal places. Only stores with three or more distinct products are considered, and the results must be ordered by the imbalance ratio in descending order and then by store name in ascending order.

The input consists of two tables: stores with information about each store, and inventory with details about each product in each store. The problem expects a query or algorithm that identifies the imbalanced stores and calculates the imbalance ratio, including the store name, location, and the names of the most expensive and cheapest products.

Important edge cases include stores with fewer than three products, products with the same price, or products where the most expensive product has a quantity equal to or greater than the cheapest product, which should be excluded. The solution must ensure correct rounding and handle division correctly.

Approaches

A brute-force approach would be to iterate through each store, retrieve all its products, identify the minimum and maximum prices along with their quantities, and then calculate the imbalance ratio if the criteria are met. While this works for small datasets, it can become inefficient for large inventories because it requires scanning all products for each store multiple times.

The optimal approach leverages SQL aggregation and window functions or Python/Go data structures such as dictionaries to group products by store. For each store, we determine the most expensive and cheapest products using MAX and MIN aggregation functions on the price, then retrieve the corresponding quantities. We filter stores with fewer than three products before calculating the imbalance ratio. Sorting is done on the imbalance ratio and store name as per the problem requirements.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(n) Scan each store and all its products individually
Optimal O(n) O(n) Aggregate data per store and compute required quantities efficiently

Here, n is the number of stores and m is the number of products per store.

Algorithm Walkthrough

  1. For each store, count the number of distinct products in the inventory table. Only keep stores with at least three products.
  2. Identify the most expensive product in each store by finding the maximum price. Retrieve both the product name and quantity for this product.
  3. Identify the cheapest product in each store by finding the minimum price. Retrieve both the product name and quantity for this product.
  4. Compare the quantities of the most expensive and cheapest products. Only keep stores where the quantity of the most expensive product is less than the quantity of the cheapest product.
  5. Calculate the imbalance ratio as cheapest_quantity / most_expensive_quantity and round it to two decimal places.
  6. Return the store details, names of the most expensive and cheapest products, and the imbalance ratio. Sort the result first by imbalance ratio in descending order, then by store name in ascending order.

Why it works: The algorithm ensures that each store considered has at least three products, directly identifies the extreme-priced products, and only selects stores meeting the imbalance condition. The grouping and aggregation guarantee correctness, and the final sort ensures the required output ordering.

Python Solution

import pandas as pd

def findStoresWithInventoryImbalance(stores: pd.DataFrame, inventory: pd.DataFrame) -> pd.DataFrame:
    # Count number of distinct products per store
    product_counts = inventory.groupby('store_id')['product_name'].nunique().reset_index()
    product_counts = product_counts[product_counts['product_name'] >= 3]

    # Filter stores with at least 3 products
    inv_filtered = inventory[inventory['store_id'].isin(product_counts['store_id'])]

    # Identify most expensive product per store
    most_exp = inv_filtered.loc[inv_filtered.groupby('store_id')['price'].idxmax()]
    most_exp = most_exp[['store_id', 'product_name', 'quantity']].rename(
        columns={'product_name': 'most_exp_product', 'quantity': 'most_exp_qty'}
    )

    # Identify cheapest product per store
    cheapest = inv_filtered.loc[inv_filtered.groupby('store_id')['price'].idxmin()]
    cheapest = cheapest[['store_id', 'product_name', 'quantity']].rename(
        columns={'product_name': 'cheapest_product', 'quantity': 'cheapest_qty'}
    )

    # Merge store info
    merged = pd.merge(stores, most_exp, on='store_id')
    merged = pd.merge(merged, cheapest, on='store_id')

    # Filter for inventory imbalance
    imbalance = merged[merged['most_exp_qty'] < merged['cheapest_qty']].copy()
    imbalance['imbalance_ratio'] = (imbalance['cheapest_qty'] / imbalance['most_exp_qty']).round(2)

    # Select and order columns
    result = imbalance[['store_id', 'store_name', 'location', 'most_exp_product', 'cheapest_product', 'imbalance_ratio']]
    result = result.sort_values(by=['imbalance_ratio', 'store_name'], ascending=[False, True]).reset_index(drop=True)

    return result

Implementation Explanation: The code first filters stores with at least three products. Then, it uses groupby and idxmax/idxmin to retrieve the most expensive and cheapest products efficiently. Merging with the stores table ensures that store names and locations are included. The final filter checks for inventory imbalance and calculates the ratio, rounding to two decimal places. Sorting produces the final output in the desired order.

Go Solution

package main

import (
    "fmt"
    "math"
    "sort"
)

type Store struct {
    StoreID   int
    StoreName string
    Location  string
}

type Inventory struct {
    InventoryID int
    StoreID     int
    ProductName string
    Quantity    int
    Price       float64
}

type Result struct {
    StoreID        int
    StoreName      string
    Location       string
    MostExpProduct string
    CheapestProduct string
    ImbalanceRatio float64
}

func findStoresWithInventoryImbalance(stores []Store, inventory []Inventory) []Result {
    // Count products per store
    productCount := make(map[int]int)
    storeInventory := make(map[int][]Inventory)
    for _, inv := range inventory {
        productCount[inv.StoreID]++
        storeInventory[inv.StoreID] = append(storeInventory[inv.StoreID], inv)
    }

    results := []Result{}
    for _, store := range stores {
        if productCount[store.StoreID] < 3 {
            continue
        }
        products := storeInventory[store.StoreID]

        var maxPriceInv, minPriceInv Inventory
        maxPrice := -1.0
        minPrice := math.MaxFloat64
        for _, p := range products {
            if p.Price > maxPrice {
                maxPrice = p.Price
                maxPriceInv = p
            }
            if p.Price < minPrice {
                minPrice = p.Price
                minPriceInv = p
            }
        }

        if maxPriceInv.Quantity < minPriceInv.Quantity {
            ratio := float64(minPriceInv.Quantity) / float64(maxPriceInv.Quantity)
            ratio = math.Round(ratio*100) / 100
            results = append(results, Result{
                StoreID:        store.StoreID,
                StoreName:      store.StoreName,
                Location:       store.Location,
                MostExpProduct: maxPriceInv.ProductName,
                CheapestProduct: minPriceInv.ProductName,
                ImbalanceRatio: ratio,
            })
        }
    }

    // Sort by imbalance_ratio descending, then store_name ascending
    sort.Slice(results, func(i, j int) bool {
        if results[i].ImbalanceRatio == results[j].ImbalanceRatio {
            return results[i].StoreName < results[j].StoreName
        }
        return results[i].ImbalanceRatio > results[j].ImbalanceRatio
    })

    return results
}

Go Implementation Notes: The Go solution uses maps to group inventories by store and count products. Since Go does not have built-in DataFrame operations, we iterate manually to find max/min priced products and calculate the imbalance ratio. Sorting is done using sort.Slice, which allows custom multi-key sorting. Care is taken with float rounding to two decimal places.

Worked Examples

Consider City Center (store_id 3):

  • Products: Tablet (2 units, $499.99), Stylus (80 units, $29.99), Cover (60 units, $39.99)
  • Max price product: Tablet, 2 units
  • Min price product: Stylus, 80 units
  • Imbalance ratio: 80 / 2 = 40.00
  • Meets minimum 3 product requirement
  • Included in result

For Corner Shop (store_id 4):

  • Only 2 products: does not meet 3 product requirement
  • Excluded

This is repeated for all stores, resulting in the output table as shown in the problem statement.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) n stores, m inventory records; each record processed once for aggregation and max/min search
Space O(n + m) Storing grouped inventories and intermediate results per store