15,614,138 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:

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)

Comments

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

Permalink

Share this answer

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

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

`promotionOrder`

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