Restaurant Growth - Solution & Explanation
Problem Statement
Table: Customer
+---------------+---------+ | Column Name | Type | +---------------+---------+ | customer_id | int | | name | varchar | | visited_on | date | | amount | int | +---------------+---------+ In SQL,(customer_id, visited_on) is the primary key for this table. This table contains data about customer transactions in a restaurant. visited_on is the date on which the customer with ID (customer_id) has visited the restaurant. amount is the total paid by a customer.
You are the restaurant owner and you want to analyze a possible expansion (there will be at least one customer every day).
Compute the moving average of how much the customer paid in a seven days window (i.e., current day + 6 days before). average_amount should be rounded to two decimal places.
Return the result table ordered by visited_on in ascending order.
The result format is in the following example.
Example 1:
Input: Customer table: +-------------+--------------+--------------+-------------+ | customer_id | name | visited_on | amount | +-------------+--------------+--------------+-------------+ | 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 | +-------------+--------------+--------------+-------------+ Output: +--------------+--------------+----------------+ | visited_on | amount | average_amount | +--------------+--------------+----------------+ | 2019-01-07 | 860 | 122.86 | | 2019-01-08 | 840 | 120 | | 2019-01-09 | 840 | 120 | | 2019-01-10 | 1000 | 142.86 | +--------------+--------------+----------------+ Explanation: 1st moving average from 2019-01-01 to 2019-01-07 has an average_amount of (100 + 110 + 120 + 130 + 110 + 140 + 150)/7 = 122.86 2nd moving average from 2019-01-02 to 2019-01-08 has an average_amount of (110 + 120 + 130 + 110 + 140 + 150 + 80)/7 = 120 3rd moving average from 2019-01-03 to 2019-01-09 has an average_amount of (120 + 130 + 110 + 140 + 150 + 80 + 110)/7 = 120 4th moving average from 2019-01-04 to 2019-01-10 has an average_amount of (130 + 110 + 140 + 150 + 80 + 110 + 130 + 150)/7 = 142.86
Approach Overview
Problem Overview: The table records how much money customers spent at a restaurant on each day. The task is to compute a 7‑day rolling revenue: for every day starting from the 7th recorded day, calculate the total amount spent in the last 7 days and the average daily revenue for that window.
Approach 1: Sliding Window Aggregation (O(n) time, O(1) extra space)
Think of the data as a time‑ordered list of daily revenue values. First aggregate the table by visited_on so each row represents the total revenue for that day. Then maintain a 7‑day window that slides forward one day at a time. When the window moves, subtract the revenue that falls out of the window and add the new day’s revenue. This avoids recomputing the full 7‑day sum every time. The running sum directly gives the total amount, and dividing by 7 produces the average. This pattern is a classic sliding window technique used for fixed‑length range calculations.
Approach 2: SQL Window Function (O(n) time, O(1) extra space)
Modern SQL engines support window functions that compute rolling aggregates efficiently. After grouping the table by visited_on, apply SUM(amount) OVER (ORDER BY visited_on ROWS BETWEEN 6 PRECEDING AND CURRENT ROW). This automatically computes the 7‑day rolling total for each row. The average is simply that sum divided by 7, usually formatted with ROUND(..., 2). Finally filter out rows that don’t have a full 7‑day window. This approach is concise and optimized by the database query planner, making it the preferred solution for problems involving time‑based analytics in SQL or general database queries.
Recommended for interviews: Interviewers typically expect you to recognize the rolling‑window pattern. Explaining the manual sliding window demonstrates algorithmic thinking and shows you understand how repeated range sums can be optimized from O(n*k) to O(n). In database interviews or SQL rounds, the window function solution is the cleanest and most production‑ready approach because it expresses the rolling computation declaratively.
Approach 1: Sliding Window Approach
This approach is based on the sliding window technique where we maintain a sum of a fixed 'window' of 7 days as we iterate through the dataset. For each day starting from the 7th day, we can calculate the moving average by simply adding the new day's amount to the moving sum and subtracting the oldest day's amount that just slid out of the window.
The C implementation uses an array `amounts` to represent the transaction amounts sorted by visit dates. The function `calculateMovingAverage` calculates a 7-day moving average. Initially, it calculates the sum of the first 7 elements (days) as it prepares the first window. Then it iterates through the array starting from the 8th element, updating the window sum by subtracting the element that slides out of the window and adding the new element. The average is printed for each window.
Complexity
Time Complexity: O(n), where n is the number of entries.
Space Complexity: O(1), only a constant amount of extra space is used.
Approach 2: SQL Window Function Approach
In the SQL approach, window functions like SUM() are utilized with a PARTITION BY and ORDER BY clause to calculate the moving sum over the window. Additionally, the row number or other similar functions might be useful to facilitate rolling calculations directly within SQL.
The given SQL query accomplishes the moving average by utilizing a window function. The SUM() function computes the total over the specified 7-day window, with the results partitioned by ordering the entries by `visited_on`. The `ROWS BETWEEN 6 PRECEDING AND CURRENT ROW` clause ensures that the window includes the current row and the six preceding days. The computation begins only after at least 7 distinct days' data is available due to the WHERE clause assuming that a date constraint ensures sufficient data.
Code
SQL
Complexity
Time Complexity: O(n), where n involves the number of records due to the need to evaluate each row and its calculated window.
Space Complexity: O(1), as it doesn't involve storing large amounts of extra data beyond the query and window setup.
Approach 3: Default Approach
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the number of entries. |
| SQL Window Function Approach | Time Complexity: O(n), where n involves the number of records due to the need to evaluate each row and its calculated window. Space Complexity: O(1), as it doesn't involve storing large amounts of extra data beyond the query and window setup. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Aggregation | O(n) | O(1) | When implementing the logic in general programming languages like Python, Java, or C++ |
| SQL Window Function | O(n) | O(1) | Best for database queries where rolling aggregates can be expressed directly in SQL |
Video Solution
Restaurant Growth| Leetcode 1321 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 14,209 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Restaurant Growth easy or hard?
Restaurant Growth Python/Java solution
How to solve Restaurant Growth in O(n)?
What is the best approach for Restaurant Growth?
Is Restaurant Growth asked at Google/Amazon/Meta?
What data structure is used in Restaurant Growth?
What is the time complexity of Restaurant Growth?
Ready to solve this problem?
Practice Restaurant Growth with our built-in code editor and test cases.
Practice on FleetCode