LeetCode 1321 - Restaurant Growth

LeetCode Problem 1321

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute a rolling seven day summary of restaurant revenue. The input table stores individual customer transactions. Each row represents how much a single customer spent on a specific date.

The important detail is that multiple customers may visit on the same day, which means we cannot directly apply a moving average on the raw rows. Instead, we first need to aggregate all customer spending per day.

For every day starting from the seventh available day, we must compute:

• The total amount spent during the current day and the previous six days
• The average daily revenue across those seven days
• The average rounded to two decimal places

The result should contain:

• visited_on, the ending date of the seven day window
• amount, the total revenue across the entire seven day window
• average_amount, the seven day average revenue

The output must be ordered chronologically by visited_on.

The problem guarantees that there is at least one customer every day. This guarantee is extremely important because it means there are no missing dates in the timeline. Without this guarantee, we would need additional logic to generate missing calendar dates before computing rolling windows.

Consider the example carefully. On 2019-01-10, there are two customer transactions:

• 130 from customer 1
• 150 from customer 3

The daily revenue for 2019-01-10 is therefore:

130 + 150 = 280

The seven day window from 2019-01-04 through 2019-01-10 becomes:

130 + 110 + 140 + 150 + 80 + 110 + 280 = 1000

Then the average is:

1000 / 7 = 142.857...

Rounded to two decimal places:

142.86

A naive implementation can easily make mistakes in several places:

• Forgetting to aggregate multiple transactions occurring on the same day
• Using seven rows instead of seven distinct dates
• Starting output before a full seven day window exists
• Forgetting to round the average properly
• Mishandling ordering of dates

The input guarantees continuous dates, which simplifies the sliding window computation significantly.

Approaches

Brute Force Approach

The brute force solution begins by aggregating daily revenue for every date. After that, for each eligible day, we recompute the total revenue for the previous seven days from scratch.

Suppose we have n distinct days. For every day starting at index 6, we iterate backward across the previous seven days and sum their revenues manually.

This approach is correct because every seven day window is independently computed using the exact definition from the problem statement. However, it performs redundant work. Consecutive windows overlap heavily. When moving from one window to the next, six out of seven days remain the same, yet the brute force solution recalculates everything again.

Although seven is technically constant, the general pattern is inefficient and does not scale well for larger window sizes.

Optimal Approach

The key observation is that adjacent seven day windows differ by only two values:

• One day leaves the window
• One new day enters the window

Instead of recomputing the entire sum every time, we maintain a running window total.

This is a classic sliding window technique.

We first aggregate daily revenue by date. Then we iterate through dates in chronological order while maintaining:

• The current seven day sum
• The current window boundaries

When the window grows beyond seven days, we subtract the oldest day's revenue. This allows every new result to be computed in constant time.

This avoids repeated summation work and produces an efficient linear solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 7)	O(n)	Recomputes each seven day window independently
Optimal	O(n)	O(n)	Uses a sliding window with running totals

Algorithm Walkthrough

Step 1: Aggregate revenue by date

The raw table contains customer level transactions, but the problem requires day level revenue.

We first group rows by visited_on and compute:

daily_total[date] = sum(amounts for that date)

For example:

Date	Daily Revenue
2019-01-01	100
2019-01-02	110
2019-01-03	120
...	...

This transformation is necessary because the rolling window operates on days, not individual customers.

Step 2: Sort dates chronologically

The sliding window only works correctly when dates are processed in ascending order.

We sort all distinct dates.

Step 3: Initialize the sliding window

We maintain:

• window_sum, the total revenue inside the current seven day window
• A left pointer representing the oldest day in the window

Initially, both pointers start at the beginning.

Step 4: Expand the window one day at a time

As we iterate through dates:

• Add the current day's revenue to window_sum
• Include the current date in the active window

Step 5: Shrink the window if it exceeds seven days

If the window becomes larger than seven days:

• Remove the oldest day's revenue
• Move the left pointer forward

This guarantees the window always contains at most seven days.

Step 6: Record results once the window size reaches seven

Whenever the window contains exactly seven days:

• amount = window_sum
• average_amount = round(window_sum / 7, 2)

Store:

(current_date, amount, average_amount)

Step 7: Return results ordered by date

Because we processed dates chronologically, the results are already sorted correctly.

Why it works

The sliding window always maintains the exact revenue total for the current seven day interval.

At every step:

• New days are added exactly once
• Old days are removed exactly once
• The window never contains fewer or more than seven days when producing output

Therefore, every computed sum and average corresponds precisely to the required seven day period.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def restaurantGrowth(self, customer: List[List]) -> List[List]:
        daily_revenue = defaultdict(int)

        # Aggregate revenue by date
        for _, _, visited_on, amount in customer:
            daily_revenue[visited_on] += amount

        # Sort dates
        sorted_dates = sorted(daily_revenue.keys())

        result = []

        left = 0
        window_sum = 0

        for right in range(len(sorted_dates)):
            current_date = sorted_dates[right]
            window_sum += daily_revenue[current_date]

            # Maintain exactly 7 days in the window
            if right - left + 1 > 7:
                oldest_date = sorted_dates[left]
                window_sum -= daily_revenue[oldest_date]
                left += 1

            # Record result when window size becomes 7
            if right - left + 1 == 7:
                average_amount = round(window_sum / 7, 2)

                result.append([
                    current_date,
                    window_sum,
                    average_amount
                ])

        return result

The implementation begins with a defaultdict(int) to aggregate daily revenue. This is necessary because multiple customers can appear on the same date.

After aggregation, the dates are sorted so the sliding window processes days in chronological order.

The variables left and right define the active seven day window. As the right pointer advances, the current day's revenue is added to window_sum.

Whenever the window grows larger than seven days, the oldest day's revenue is removed and the left pointer advances. This ensures the window always represents the correct rolling interval.

Once the window reaches exactly seven days, the algorithm computes the average and appends the result.

The solution performs only constant work per day, making it highly efficient.

Go Solution

package main

import (
	"math"
	"sort"
)

func restaurantGrowth(customer [][]interface{}) [][]interface{} {
	dailyRevenue := make(map[string]int)

	// Aggregate revenue by date
	for _, row := range customer {
		visitedOn := row[2].(string)
		amount := row[3].(int)

		dailyRevenue[visitedOn] += amount
	}

	// Sort dates
	var dates []string
	for date := range dailyRevenue {
		dates = append(dates, date)
	}

	sort.Strings(dates)

	var result [][]interface{}

	left := 0
	windowSum := 0

	for right := 0; right < len(dates); right++ {
		currentDate := dates[right]
		windowSum += dailyRevenue[currentDate]

		// Keep window size at most 7
		if right-left+1 > 7 {
			oldestDate := dates[left]
			windowSum -= dailyRevenue[oldestDate]
			left++
		}

		// Record result for valid 7-day windows
		if right-left+1 == 7 {
			average := math.Round((float64(windowSum)/7.0)*100) / 100

			result = append(result, []interface{}{
				currentDate,
				windowSum,
				average,
			})
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version, but there are several language specific details.

Go does not have Python style dynamic dictionaries with automatic defaults, so a standard map is used for aggregation.

Dates are stored as strings because ISO formatted dates sort correctly lexicographically.

Floating point rounding requires explicit handling using math.Round.

The result type uses [][]interface{} because the rows contain mixed types, strings and numeric values.

Worked Examples

Example 1

Input daily revenue after aggregation:

Date	Revenue
2019-01-01	100
2019-01-02	110
2019-01-03	120
2019-01-04	130
2019-01-05	110
2019-01-06	140
2019-01-07	150
2019-01-08	80
2019-01-09	110
2019-01-10	280

Now trace the sliding window:

Right Date	Window Dates	Window Sum	Output?
2019-01-01	01-01	100	No
2019-01-02	01-01 to 01-02	210	No
2019-01-03	01-01 to 01-03	330	No
2019-01-04	01-01 to 01-04	460	No
2019-01-05	01-01 to 01-05	570	No
2019-01-06	01-01 to 01-06	710	No
2019-01-07	01-01 to 01-07	860	Yes
2019-01-08	01-02 to 01-08	840	Yes
2019-01-09	01-03 to 01-09	840	Yes
2019-01-10	01-04 to 01-10	1000	Yes

For 2019-01-07:

average = 860 / 7 = 122.857...

Rounded:

122.86

For 2019-01-10:

average = 1000 / 7 = 142.857...

Rounded:

142.86

Final output:

visited_on	amount	average_amount
2019-01-07	860	122.86
2019-01-08	840	120.00
2019-01-09	840	120.00
2019-01-10	1000	142.86

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each date enters and leaves the sliding window once
Space	O(n)	Stores aggregated daily revenue

The aggregation phase processes each row once. The sliding window also processes each distinct date once. Since every date is added and removed from the window at most one time, the overall runtime is linear.

The auxiliary space comes primarily from storing daily aggregated revenue.

Test Cases

from collections import defaultdict

class Solution:
    def restaurantGrowth(self, customer):
        daily_revenue = defaultdict(int)

        for _, _, visited_on, amount in customer:
            daily_revenue[visited_on] += amount

        sorted_dates = sorted(daily_revenue.keys())

        result = []

        left = 0
        window_sum = 0

        for right in range(len(sorted_dates)):
            current_date = sorted_dates[right]
            window_sum += daily_revenue[current_date]

            if right - left + 1 > 7:
                oldest_date = sorted_dates[left]
                window_sum -= daily_revenue[oldest_date]
                left += 1

            if right - left + 1 == 7:
                result.append([
                    current_date,
                    window_sum,
                    round(window_sum / 7, 2)
                ])

        return result

solution = Solution()

# Basic example from problem statement
assert solution.restaurantGrowth([
    [1, "Jhon", "2019-01-01", 100],
    [2, "Daniel", "2019-01-02", 110],
    [3, "Jade", "2019-01-03", 120],
    [4, "Khaled", "2019-01-04", 130],
    [5, "Winston", "2019-01-05", 110],
    [6, "Elvis", "2019-01-06", 140],
    [7, "Anna", "2019-01-07", 150],
    [8, "Maria", "2019-01-08", 80],
    [9, "Jaze", "2019-01-09", 110],
    [1, "Jhon", "2019-01-10", 130],
    [3, "Jade", "2019-01-10", 150],
]) == [
    ["2019-01-07", 860, 122.86],
    ["2019-01-08", 840, 120.0],
    ["2019-01-09", 840, 120.0],
    ["2019-01-10", 1000, 142.86],
]  # standard rolling window test

# Exactly seven days
assert solution.restaurantGrowth([
    [1, "A", "2020-01-01", 10],
    [2, "B", "2020-01-02", 20],
    [3, "C", "2020-01-03", 30],
    [4, "D", "2020-01-04", 40],
    [5, "E", "2020-01-05", 50],
    [6, "F", "2020-01-06", 60],
    [7, "G", "2020-01-07", 70],
]) == [
    ["2020-01-07", 280, 40.0]
]  # smallest valid output

# Multiple customers on same day
assert solution.restaurantGrowth([
    [1, "A", "2020-01-01", 100],
    [2, "B", "2020-01-01", 200],
    [3, "C", "2020-01-02", 100],
    [4, "D", "2020-01-03", 100],
    [5, "E", "2020-01-04", 100],
    [6, "F", "2020-01-05", 100],
    [7, "G", "2020-01-06", 100],
    [8, "H", "2020-01-07", 100],
]) == [
    ["2020-01-07", 900, 128.57]
]  # verifies aggregation by date

# Uniform revenue every day
assert solution.restaurantGrowth([
    [i, str(i), f"2020-01-0{i}", 50]
    for i in range(1, 8)
]) == [
    ["2020-01-07", 350, 50.0]
]  # constant rolling average

# Large revenue values
assert solution.restaurantGrowth([
    [1, "A", "2020-01-01", 1000000],
    [2, "B", "2020-01-02", 1000000],
    [3, "C", "2020-01-03", 1000000],
    [4, "D", "2020-01-04", 1000000],
    [5, "E", "2020-01-05", 1000000],
    [6, "F", "2020-01-06", 1000000],
    [7, "G", "2020-01-07", 1000000],
]) == [
    ["2020-01-07", 7000000, 1000000.0]
]  # tests large sums

Test	Why
Problem statement example	Validates standard rolling window behavior
Exactly seven days	Ensures first valid window works correctly
Multiple customers same day	Verifies daily aggregation logic
Uniform revenue	Checks stable averages
Large revenue values	Ensures large sums are handled correctly

Edge Cases

Multiple transactions on the same date

One of the easiest mistakes is treating each row as a separate day. The input table stores customer transactions, not daily summaries.

If multiple customers visit on the same date, their amounts must be combined before sliding window computation begins.

The implementation handles this correctly using:

daily_revenue[visited_on] += amount

This guarantees every date contributes exactly one aggregated value to the rolling window.

Exactly seven distinct days

If the input contains exactly seven days, there is only one valid output row.

Some implementations incorrectly require more than seven days before generating results. Others accidentally produce no output.

The sliding window logic explicitly checks:

if right - left + 1 == 7

This ensures the first valid window is produced immediately once seven days are available.

Large daily revenue values

Revenue totals may become very large when many customers spend large amounts over seven days.

An implementation using small integer types could overflow in some languages.

Python integers automatically expand to arbitrary precision, so the Python solution is naturally safe. In Go, standard int values are sufficient for typical LeetCode constraints, but using integer arithmetic carefully still matters.

The algorithm stores running sums incrementally, avoiding unnecessary recomputation and minimizing arithmetic risk.