How do you solve Restaurant Growth on LeetCode?

Restaurant Growth (LeetCode #1321) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a sliding window can significantly reduce the time complexity of problems involving moving averages.

What is the brute force solution for Restaurant Growth?

The brute force approach for Restaurant Growth is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the moving average for each day by summing the amounts of all customers who visited in the last 7 days and dividing by the number of days. It's straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Restaurant Growth?

Restaurant Growth uses the following concepts: Database. The recommended patterns to study are: Sliding Window, Aggregation.

What are the interview tips for Restaurant Growth?

Always clarify the requirements and constraints before diving into coding. Think about how you can optimize your solution after the brute force approach. Practice writing SQL queries as they can often be a part of technical interviews.

What are common mistakes when solving Restaurant Growth?

Not considering edge cases where fewer than 7 days of data are available. Failing to round the average correctly to two decimal places.

#1321

Restaurant Growth

Medium

DatabaseSliding WindowAggregation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a sliding window technique to maintain a rolling sum of the last 7 days' amounts, allowing us to compute the average in constant time for each day after the initial setup.

⚙️

Algorithm

6 steps

1Step 1: Create a temporary table to store the daily total amounts.
2Step 2: Initialize a variable to keep track of the sum of amounts for the last 7 days.
3Step 3: For each day, add the current day's amount to the sum and subtract the amount from the day that is 7 days before.
4Step 4: Calculate the average using the current sum and the number of days (up to 7).
5Step 5: Round the average to two decimal places.
6Step 6: Store the result and return it ordered by visited_on.

solution.py10 lines

1WITH DailyTotals AS (
2    SELECT visited_on, SUM(amount) AS total_amount
3    FROM Customer
4    GROUP BY visited_on
5)
6SELECT visited_on, ROUND(SUM(total_amount) / LEAST(7, COUNT(*)), 2) AS average_amount
7FROM DailyTotals
8WHERE visited_on >= DATE_SUB(visited_on, INTERVAL 6 DAY)
9GROUP BY visited_on
10ORDER BY visited_on;

ℹ

Complexity note: This complexity is more efficient because we only traverse the data once to compute the daily totals, and then we use a sliding window to compute the averages.

1Using a sliding window can significantly reduce the time complexity of problems involving moving averages.
2Understanding how to aggregate data efficiently in SQL is crucial for performance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.