class Solution {
public:
long long totalCost(vector<int>& cost, int k, int c) {
priority_queue<pair<int,int>>pq; // Priority queue to store costs in descending order along with their corresponding type
map<int,int>m; // Map to keep track of the occurrences of each type
for(int i=0;i<c;i++){
m[i]++; // Increment the occurrence count of type i
pq.push({-cost[i],1}); // Push the cost with its type into the priority queue
}
int i=cost.size()-1;
// Iterate until the desired number of candidates is reached
for(int j=0;j<c;j++){
// Check if the type of the element at index i is already included
if(m[i]==0){
m[i]++; // Increment the occurrence count of type i
pq.push({-cost[i],0}); // Push the cost with its type into the priority queue
i--; // Move to the next element from the end
}
else break;
}
int l = c; // Pointer to track the left side of the sliding window
int r = cost.size()-1-c; // Pointer to track the right side of the sliding window
long long ans=0; // Variable to store the total cost
// Iterate until the desired number of candidates is reached
for(int j=0;j<k;j++){
ans += abs(pq.top().first); // Add the absolute value of the cost to the total cost
int h = pq.top().second; // Get the type of the cost
pq.pop(); // Remove the top element from the priority queue
// Depending on whether the type was from the left or right side of the sliding window
if(h){
// Check if the type on the left side is already included and if we have not reached the end of the array
if(m[l]==0 && l<cost.size()){
m[l]++; // Increment the occurrence count of type l
pq.push({-cost[l],1}); // Push the cost with its type into the priority queue
l++; // Move to the next element from the left side
}
}
else{
// Check if the type on the right side is already included and if we have not reached the start of the array
if(m[r]==0 && r>=0){
m[r]++; // Increment the occurrence count of type r
pq.push({-cost[r],0}); // Push the cost with its type into the priority queue
r--; // Move to the next element from the right side
}
}
}
return ans; // Return the total cost
}
};
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
long long ans = 0; // Variable to store the total cost
// Priority queue to store the lowest costs from the beginning of the array
priority_queue<int, vector<int>, greater<int>> q1;
// Priority queue to store the highest costs from the end of the array
priority_queue<int, vector<int>, greater<int>> q2;
int low = 0; // Pointer to track the beginning of the array
// Insert 'candidates' number of costs into q1
while (low < candidates) {
q1.push(costs[low]);
low++;
}
int cnt = 0;
int high = (int)costs.size() - 1; // Pointer to track the end of the array
// Adjust 'candidates' if it is greater than the number of elements from the end of the array
if (candidates > costs.size() - candidates) {
candidates = costs.size() - candidates;
}
// Insert 'candidates' number of costs into q2 from the end of the array
while (cnt < candidates) {
q2.push(costs[high]);
cnt++;
high--;
}
// Perform k iterations
while (k--) {
if (q1.empty()) { // If q1 is empty, take the lowest cost from q2
ans += q2.top(); // Add the top element from q2 to the total cost
q2.pop(); // Remove the top element from q2
if (low <= high) {
q2.push(costs[high]); // Push the next element from the end of the array to q2
high--; // Move the high pointer
}
} else if (q2.empty()) { // If q2 is empty, take the lowest cost from q1
ans += q1.top(); // Add the top element from q1 to the total cost
q1.pop(); // Remove the top element from q1
if (low <= high) {
q1.push(costs[low]); // Push the next element from the beginning of the array to q1
low++; // Move the low pointer
}
} else if (q1.top() <= q2.top()) { // If the lowest cost in q1 is less than or equal to the lowest cost in q2, take the lowest cost from q1
ans += q1.top(); // Add the top element from q1 to the total cost
q1.pop(); // Remove the top element from q1
if (low <= high) {
q1.push(costs[low]); // Push the next element from the beginning of the array to q1
low++; // Move the low pointer
}
} else { // If the lowest cost in q2 is less than the lowest cost in q1, take the lowest cost from q2
ans += q2.top(); // Add the top element from q2 to the total cost
q2.pop(); // Remove the top element from q2
if (low <= high) {
q2.push(costs[high]); // Push the next element from the end of the array to q2
high--; // Move the high pointer
}
}
}
return ans; // Return the total cost
}
};
Now, let's provide a table to outline the key takeaways of the differences:
<td><code style="color:orang; font-weight:900";>priority_queue</code>, `map`</td>
<td><code style="color:green; font-weight:900";>O(c)</code> - <code style="color:orang; font-weight:900";>priority_queue</code> and `map` are used to store c elements</td>
<td><code style="color:green; font-weight:900";>O(k * log(c))</code> - Multiple operations on <code style="color:orang; font-weight:900";>priority_queue</code></td>
<td>- Uses `map` to keep track of element occurrences<br>- Pushes elements with negative costs (reversed order) into the <code style="color:orang; font-weight:900";>priority_queue</code><br>- Considers left and right pointers to keep track of unused elements from the beginning and end of the array</td>
| Data Structures Used | Space Complexity | Time Complexity | Key Differences | Takeaways |
|---|---|---|---|---|
priority_queue |
O(candidates) - priority_queue |
O(k * log(k) + c * log(candidates)) |
- Uses two separate priority_queue queues, one to store lowest costs from the beginning of the array, and the other to store highest costs from the end of the array.- Pushes costs normally into the priority_queue.- Handles unused elements by adjusting the number of candidates and conditionally pushing them into the appropriate priority_queue. |
| First Approach | Second Approach | |
|---|---|---|
| Data Structures Used | priority_queue, map |
priority_queue |
| Space Complexity | O(c) - priority_queue and map are used to store c elements |
O(candidates) - priority_queue |
| Time Complexity | O(k * log(c)) - Multiple operations on priority_queue |
O(k * log(k) + c * log(candidates)) |
| Key Differences | - Uses map to keep track of element occurrences |
- Uses two separate priority_queue queues, one to store lowest costs from the beginning of the array, and the other to store highest costs from the end of the array. |
- Pushes elements with negative costs (reversed order) into the priority_queue |
- Pushes costs normally into the priority_queue |
|
| - Considers left and right pointers to keep track of unused elements from the beginning and end of the array | - Handles unused elements by adjusting the number of candidates and condi- tionally pushing them into the appropriate priority_queue |
|
| Conclusion | The first approach uses a combination of priority_queue and map to manage costs and element occurrences. However, it can have higher space complexity because of the additional overhead of map. The second approach simplifies the process by using two separate priority_queue queues and pointers to track unused elements, resulting in better space complexity and potentially better time complexity. While the second approach has a slightly more complex implementation, it offers improved efficiency compared to the first approach. |
function totalCost(costs, k, candidates) {
let ans = 0; // Variable to store the total cost
const q1 = []; // Array to store the lowest costs from the beginning of the array
const q2 = []; // Array to store the highest costs from the end of the array
let low = 0; // Pointer to track the beginning of the array
// Insert 'candidates' number of costs into q1
while (low < candidates) {
q1.push(costs[low]);
low++;
}
let cnt = 0;
let high = costs.length - 1; // Pointer to track the end of the array
// Adjust 'candidates' if it is greater than the number of elements from the end of the array
if (candidates > costs.length - candidates) {
candidates = costs.length - candidates;
}
// Insert 'candidates' number of costs into q2 from the end of the array
while (cnt < candidates) {
q2.push(costs[high]);
cnt++;
high--;
}
// Perform k iterations
while (k--) {
if (q1.length === 0) { // If q1 is empty, take the lowest cost from q2
ans += q2[0]; // Add the first element from q2 to the total cost
q2.shift(); // Remove the first element from q2
if (low <= high) {
q2.push(costs[high]); // Push the next element from the end of the array to q2
high--; // Move the high pointer
}
} else if (q2.length === 0) { // If q2 is empty, take the lowest cost from q1
ans += q1[0]; // Add the first element from q1 to the total cost
q1.shift(); // Remove the first element from q1
if (low <= high) {
q1.push(costs[low]); // Push the next element from the beginning of the array to q1
low++; // Move the low pointer
}
} else if (q1[0] <= q2[0]) { // If the first cost in q1 is less than or equal to the first cost in q2, take the first cost from q1
ans += q1[0]; // Add the first element from q1 to the total cost
q1.shift(); // Remove the first element from q1
if (low <= high) {
q1.push(costs[low]); // Push the next element from the beginning of the array to q1
low++; // Move the low pointer
}
} else { // If the first cost in q2 is less than the first cost in q1, take the first cost from q2
ans += q2[0]; // Add the first element from q2 to the total cost
q2.shift(); // Remove the first element from q2
if (low <= high) {
q2.push(costs[high]); // Push the next element from the end of the array to q2
high--; // Move the high pointer
}
}
}
return ans; // Return the total cost
}import heapq
def total_cost(costs, k, candidates):
ans = 0 # Variable to store the total cost
q1 = [] # List to store the lowest costs from the beginning of the array
q2 = [] # List to store the highest costs from the end of the array
low = 0 # Pointer to track the beginning of the array
# Insert 'candidates' number of costs into q1
while low < candidates:
heapq.heappush(q1, costs[low])
low += 1
cnt = 0
high = len(costs) - 1 # Pointer to track the end of the array
# Adjust 'candidates' if it is greater than the number of elements from the end of the array
if candidates > len(costs) - candidates:
candidates = len(costs) - candidates
# Insert 'candidates' number of costs into q2 from the end of the array
while cnt < candidates:
heapq.heappush(q2, -costs[high])
cnt += 1
high -= 1
# Perform k iterations
while k > 0:
if len(q1) == 0: # If q1 is empty, take the lowest cost from q2
ans += -heapq.heappop(q2) # Add the popped element from q2 to the total cost
if low <= high:
heapq.heappush(q2, -costs[high]) # Push the next element from the end of the array to q2
high -= 1
elif len(q2) == 0: # If q2 is empty, take the lowest cost from q1
ans += heapq.heappop(q1) # Add the popped element from q1 to the total cost
if low <= high:
heapq.heappush(q1, costs[low]) # Push the next element from the beginning of the array to q1
low += 1
elif q1[0] <= -q2[0]: # If the first cost in q1 is less than or equal to the first cost in q2, take the first cost from q1
ans += heapq.heappop(q1) # Add the popped element from q1 to the total cost
if low <= high:
heapq.heappush(q1, costs[low]) # Push the next element from the beginning of the array to q1
low += 1
else: # If the first cost in q2 is less than the first cost in q1, take the first cost from q2
ans += -heapq.heappop(q2) # Add the popped element from q2 to the total cost
if low <= high:
heapq.heappush(q2, -costs[high]) # Push the next element from the end of the array to q2
high -= 1
k -= 1
return ans # Return the total costimport java.util.PriorityQueue;
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
long ans = 0; // Variable to store the total cost
PriorityQueue<Integer> q1 = new PriorityQueue<>(); // Priority queue to store the lowest costs from the beginning of the array
PriorityQueue<Integer> q2 = new PriorityQueue<>(); // Priority queue to store the highest costs from the end of the array
int low = 0; // Pointer to track the beginning of the array
// Insert 'candidates' number of costs into q1
while (low < candidates) {
q1.offer(costs[low]);
low++;
}
int cnt = 0;
int high = costs.length - 1; // Pointer to track the end of the array
// Adjust 'candidates' if it is greater than the number of elements from the end of the array
if (candidates > costs.length - candidates) {
candidates = costs.length - candidates;
}
// Insert 'candidates' number of costs into q2 from the end of the array
while (cnt < candidates) {
q2.offer(-costs[high]);
cnt++;
high--;
}
// Perform k iterations
while (k > 0) {
if (q1.isEmpty()) { // If q1 is empty, take the lowest cost from q2
ans += -q2.poll(); // Add the polled element from q2 to the total cost
if (low <= high) {
q2.offer(-costs[high]); // Push the next element from the end of the array to q2
high--;
}
} else if (q2.isEmpty()) { // If q2 is empty, take the lowest cost from q1
ans += q1.poll(); // Add the polled element from q1 to the total cost
if (low <= high) {
q1.offer(costs[low]); // Push the next element from the beginning of the array to q1
low++;
}
} else if (q1.peek() <= -q2.peek()) { // If the lowest cost in q1 is less than or equal to the lowest cost in q2, take the lowest cost from q1
ans += q1.poll(); // Add the polled element from q1 to the total cost
if (low <= high) {
q1.offer(costs[low]); // Push the next element from the beginning of the array to q1
low++;
}
} else { // If the lowest cost in q2 is less than the lowest cost in q1, take the lowest cost from q2
ans += -q2.poll(); // Add the polled element from q2 to the total cost
if (low <= high) {
q2.offer(-costs[high]); // Push the next element from the end of the array to q2
high--;
}
}
k--;
}
return ans; // Return the total cost
}
}