Richard has given you a solution of time complexity O(N*M), and auxillary space O(1), where M is the number of entries in the promotionOrder list.

This could be reduced to O(N) with auxiliary space O(M) if we create a hash map where the key is the value of the promotionOrder entry and the mapped value is the position in the promotionOrder table. A set of M counters is initialized to zeroes.

For each carInventory entry:

Look up the position in the hash map

Increment the number of cars in that position.

For all counters:

Insert (counter) entries of the appropriate type into the output.

Reducing the auxiliary space to O(1) is left as an exercise...

15,559,275 members

`promotionOrder`

list and find all the relevant car entries for each one.