15,559,275 members
See more:
So I'm trying to sort an vector <string> carInventory based on the order of a vector with 3 elements titled vector <string> promotionOrder.

Ex)

Input:
vector<string> carInventory {"mz", "my", "my", "mx", "mz", "mx", "my", "mz"}
vector<string> promotionOrder {"mz", "mx", "my"}

Output:
{"mz", "mz", "mz", "mx", "mx", "my", "my", "my"} //new carInventory

Here's the function:
```vector<string> SortCar::sortCarInventory(vector<string> carInventory,
vector<string> promotionOrder)

What I have tried:

Currently stuck thinking of a solution with a time complexity of O(N) and <pre>with constant auxiliary space complexity O(1)```
Posted
Updated 9-Oct-22 20:09pm
CPallini 8-Jun-22 4:38am
I don't know any sorting algorithm warranting O(N).
Richard MacCutchan 8-Jun-22 4:43am
You cannot use a sort as the sort order is not fixed. You just need to iterate the `promotionOrder` list and find all the relevant car entries for each one.

## Solution 1

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...

## Solution 4

Simple. STL will sort it for you.

Top Experts
Last 24hrsThis month
 OriginalGriff 65 Richard MacCutchan 25 Richard Deeming 25 CPallini 25 oliver sato (Paytvcard) 20
 OriginalGriff 4,129 Graeme_Grant 1,792 Richard MacCutchan 1,565 CPallini 942 Richard Deeming 805

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900