Customer Placing the Largest Number of Orders

Difficulty: Easy | Acceptance: 64.40% | Paid: No Topics: Database

Table: Orders +---------------+---------+ | Column Name | Type | +---------------+---------+ | order_number | int | | customer_number | int | +---------------+---------+ order_number is the primary key of this table. This table contains information about the order ID and the customer ID.

Write a solution to find the customer_number for the customer who has placed the largest number of orders.

The test cases are generated so that exactly one customer will have placed the largest number of orders.

• Examples
• Constraints
• Approach 1: Hash Map (Frequency Count)
• Approach 2: Sorting

Examples

Example 1

Input: Orders table: +--------------+-----------------+ | order_number | customer_number | +--------------+-----------------+ | 1 | 1 | | 2 | 2 | | 3 | 3 | | 4 | 3 | +--------------+-----------------+

Output: +-----------------+ | customer_number | +-----------------+ | 3 | +-----------------+

Explanation: Customer 3 has placed the most orders, which is 2 orders.

Constraints

- 1 <= Orders table rows <= 1000

Approach 1: Hash Map (Frequency Count)

Intuition We can iterate through the list of orders and use a hash map to count the frequency of each customer number. Then, we find the customer with the maximum count.

Steps

• Initialize a hash map (dictionary) to store customer counts.
• Iterate through each order record.
• For each record, extract the customer_number and increment its count in the map.
• Iterate through the map to find the customer with the highest count.
• Return the customer_number.

from typing import List
from collections import Counter

class Solution:
    def largestOrders(self, orders: List[List[int]]) -> int:
        counts = Counter()
        for _, cust in orders:
            counts[cust] += 1
        return max(counts.items(), key=lambda x: x[1])[0]

Complexity

• Time: O(n), where n is the number of orders. We iterate through the list once to build the map and once through the map to find the max.
• Space: O(k), where k is the number of unique customers. In the worst case, this is O(n).
• Notes: This is the most efficient approach for unsorted data.

Approach 2: Sorting

Intuition If we sort the list of orders by customer_number, identical customer numbers will be adjacent. We can then iterate through the sorted list, counting consecutive occurrences to find the maximum frequency.

Steps

• Sort the list of orders based on customer_number.
• Initialize variables to track the current customer, current count, max customer, and max count.
• Iterate through the sorted list.
• If the current customer is the same as the previous one, increment the current count.
• If the customer changes, compare the current count with the max count and update if necessary, then reset the current count.
• After the loop, perform a final check for the last customer segment.
• Return the customer with the maximum count.

from typing import List

class Solution:
    def largestOrders(self, orders: List[List[int]]) -> int:
        if not orders:
            return -1
        orders.sort(key=lambda x: x[1])
        max_cust = orders[0][1]
        max_count = 1
        curr_count = 1
        for i in range(1, len(orders)):
            if orders[i][1] == orders[i-1][1]:
                curr_count += 1
            else:
                if curr_count > max_count:
                    max_count = curr_count
                    max_cust = orders[i-1][1]
                curr_count = 1
        if curr_count > max_count:
            max_cust = orders[-1][1]
        return max_cust

Complexity

• Time: O(n log n) due to the sorting step, where n is the number of orders.
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity (e.g., O(log n) for quicksort stack space).
• Notes: Sorting is less efficient than the hash map approach for this specific problem but is a valid alternative.