LeetCode 586 - Customer Placing the Largest Number of Orders

LeetCode Problem 586

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Orders with two columns:

Column	Meaning
order_number	Unique identifier for an order
customer_number	Identifier for the customer who placed the order

Each row represents a single order placed by a customer. A customer may appear multiple times because a customer can place multiple orders.

The task is to determine which customer has placed the largest number of orders. The output should contain only the customer_number of that customer.

The problem also guarantees that exactly one customer has strictly more orders than every other customer. This guarantee is important because it means we do not need to handle ties in the main solution.

For example, consider the following rows:

order_number	customer_number
1	1
2	2
3	3
4	3

Customer 3 appears twice, while customers 1 and 2 appear only once. Therefore, customer 3 has the largest number of orders.

This is fundamentally a counting and aggregation problem. We need to count how many times each customer_number appears, then return the customer with the maximum count.

The constraints are small because this is an Easy SQL problem, but even without explicit limits, the natural database approach is efficient. SQL aggregation operations such as COUNT, GROUP BY, and sorting or filtering are designed exactly for this type of query.

There are several edge cases worth recognizing upfront. One important case is when there is only one customer in the table. Another case is when many customers have only one order except one customer with many orders. The problem guarantee eliminates ambiguity caused by ties, but the follow-up question asks how to handle ties if multiple customers share the maximum count.

Approaches

Brute Force Approach

A brute-force strategy would examine each customer individually and repeatedly count how many orders belong to that customer.

Conceptually, the algorithm would work like this:

1. Extract all distinct customers.
2. For each customer, scan the entire table and count matching rows.
3. Keep track of the customer with the highest count.

This approach is correct because every customer's order count is computed exactly. However, it is inefficient because the table is scanned repeatedly.

If there are n rows and k distinct customers, the runtime becomes O(n * k). In the worst case, where every order belongs to a different customer, this approaches O(n^2).

This repeated scanning is unnecessary because SQL aggregation can compute all counts in a single pass.

Optimal Approach

The key insight is that we only need the frequency of each customer_number.

SQL provides GROUP BY, which groups rows sharing the same customer ID. Once grouped, COUNT(*) computes the number of orders for each customer.

After computing these counts, we simply select the customer with the largest count.

There are two common ways to do this:

1. Sort customers by count descending and take the first row.
2. Compute the maximum count and filter customers matching it.

Because the problem guarantees a unique answer, the sorting approach is concise and efficient.

The optimal SQL query is:

SELECT customer_number
FROM Orders
GROUP BY customer_number
ORDER BY COUNT(*) DESC
LIMIT 1;

This works because:

• GROUP BY customer_number creates one group per customer.
• COUNT(*) counts the number of rows in each group.
• ORDER BY COUNT(*) DESC places the largest count first.
• LIMIT 1 returns only the top customer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the table for every customer
Optimal	O(n log n)	O(k)	Uses SQL aggregation and sorting efficiently

The exact complexity of SQL operations depends on the database engine, but logically the aggregation is linear and the sorting step dominates.

Algorithm Walkthrough

1. Group all rows by customer_number.

This step combines all orders belonging to the same customer into a single group. Instead of treating every order independently, we now process customers as aggregated entities. 2. Count the number of rows in each group.

Using COUNT(*), we compute how many orders each customer has placed. This transforms the raw order table into a set of (customer_number, order_count) pairs. 3. Sort the grouped results in descending order of order count.

The customer with the most orders should appear first after sorting. 4. Return the first row.

Since the problem guarantees exactly one customer has the maximum number of orders, the first row is the correct answer.

Why it works

The algorithm works because grouping partitions all rows by customer identity, and counting each partition produces the exact number of orders for that customer. Sorting these counts in descending order guarantees that the customer with the highest frequency appears first. Since the problem guarantees uniqueness, returning the first row always yields the correct answer.

Python Solution

Although this is a SQL problem, the following Python implementation demonstrates the same logic programmatically.

from collections import Counter
from typing import List

class Solution:
    def customerWithMostOrders(self, orders: List[int]) -> int:
        order_counts = Counter(orders)

        most_orders_customer = max(
            order_counts,
            key=order_counts.get
        )

        return most_orders_customer

The implementation uses Python's Counter class to efficiently count how many times each customer appears.

The Counter internally behaves like a hash map where:

• The key is the customer_number
• The value is the number of orders

After building the frequency map, the max() function finds the customer whose count is largest.

This mirrors the SQL aggregation logic:

• Counter corresponds to GROUP BY + COUNT
• max() corresponds to ORDER BY COUNT(*) DESC LIMIT 1

Go Solution

package main

func customerWithMostOrders(orders []int) int {
	orderCounts := make(map[int]int)

	for _, customer := range orders {
		orderCounts[customer]++
	}

	maxCustomer := -1
	maxOrders := 0

	for customer, count := range orderCounts {
		if count > maxOrders {
			maxOrders = count
			maxCustomer = customer
		}
	}

	return maxCustomer
}

The Go implementation uses a map from int to int to store order frequencies.

Unlike Python's Counter, Go does not provide a built-in frequency-counting utility, so the counts are maintained manually.

The logic is otherwise identical:

• Iterate through orders and update counts.
• Track the customer with the maximum count.
• Return that customer.

There are no concerns about integer overflow here because order counts are well within standard integer limits for realistic problem constraints.

SQL Solution

SELECT customer_number
FROM Orders
GROUP BY customer_number
ORDER BY COUNT(*) DESC
LIMIT 1;

This is the intended LeetCode database solution.

The query groups rows by customer, counts the number of orders per customer, sorts customers by order count in descending order, and returns the top customer.

Follow Up Solution

If multiple customers can share the maximum number of orders, we must return all such customers.

In that case, sorting and limiting to one row is insufficient. Instead, we compute the maximum order count and return every customer matching that value.

SELECT customer_number
FROM Orders
GROUP BY customer_number
HAVING COUNT(*) = (
    SELECT COUNT(*)
    FROM Orders
    GROUP BY customer_number
    ORDER BY COUNT(*) DESC
    LIMIT 1
);

This query first determines the largest order count, then filters grouped customers to only those matching that maximum.

Worked Examples

Example 1

Input table:

order_number	customer_number
1	1
2	2
3	3
4	3

Step 1: Group by customer

customer_number	Orders
1	[1]
2	[2]
3	[3, 4]

Step 2: Count orders

customer_number	order_count
1	1
2	1
3	2

Step 3: Sort descending by count

customer_number	order_count
3	2
1	1
2	1

Step 4: Return first row

Result:

customer_number
3

Customer 3 has the highest order count, so the answer is 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Aggregation is linear, sorting grouped counts dominates
Space	O(k)	Stores counts for each distinct customer

Here, n is the number of orders and k is the number of distinct customers.

The grouping step processes each row once, which is effectively linear. The sorting operation on grouped customers introduces the logarithmic factor.

If the database engine uses hashing and optimized aggregation internally, practical performance is very efficient.

Test Cases

from collections import Counter

def customer_with_most_orders(orders):
    counts = Counter(orders)
    return max(counts, key=counts.get)

# Basic example from the prompt
assert customer_with_most_orders([1, 2, 3, 3]) == 3

# Single customer only
assert customer_with_most_orders([5]) == 5

# One customer dominates heavily
assert customer_with_most_orders([1, 1, 1, 2, 3]) == 1

# Larger distribution
assert customer_with_most_orders([4, 4, 2, 2, 2, 3, 3]) == 2

# Customer appears non-consecutively
assert customer_with_most_orders([7, 1, 7, 2, 7, 3]) == 7

# Large customer IDs
assert customer_with_most_orders([1000, 2000, 1000]) == 1000

# Multiple customers with different counts
assert customer_with_most_orders([9, 9, 8, 8, 8, 7]) == 8

Test Case Summary

Test	Why
[1, 2, 3, 3]	Verifies the provided example
[5]	Tests single-customer input
[1, 1, 1, 2, 3]	Tests clear dominant customer
[4, 4, 2, 2, 2, 3, 3]	Tests multiple frequencies
[7, 1, 7, 2, 7, 3]	Ensures ordering in input does not matter
[1000, 2000, 1000]	Tests large customer IDs
[9, 9, 8, 8, 8, 7]	Tests correct maximum detection

Edge Cases

One important edge case is when the table contains only a single order. In this scenario, there is only one customer, so that customer must necessarily have the largest number of orders. The implementation handles this naturally because grouping creates exactly one group and the query returns it.

Another important case is when orders for the same customer are scattered throughout the table rather than appearing consecutively. A naive implementation that assumes adjacent rows belong together could fail. The aggregation approach avoids this issue entirely because GROUP BY collects rows logically rather than relying on physical order.

A third edge case involves very large customer ID values. Since customer IDs are treated purely as identifiers and not array indices, the implementation works correctly regardless of numeric magnitude. Both SQL grouping and hash map based solutions handle sparse or large identifiers naturally.

Finally, the follow-up introduces ties for the maximum number of orders. The original query uses LIMIT 1, which would incorrectly discard other valid customers in that scenario. The follow-up solution addresses this by explicitly filtering all customers whose order count equals the global maximum.