15,614,138 members
0.00/5 (No votes)
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 19:09pm
Comments
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 4

Simple. STL will sort it for you.

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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Graeme_Grant 60 OriginalGriff 50 CPallini 50 CHill60 40 Rick York 20
 OriginalGriff 2,866 Richard MacCutchan 1,226 Graeme_Grant 940 Dave Kreskowiak 641 CPallini 330

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