SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem involves minimizing the total cost of selecting a set of items from two ends of an array. Given an array of costs, the task is to choose exactly k items with the smallest possible total cost. You can select items from either end of the array, but after selecting an item, that end's boundary will move inward. The challenge is to efficiently manage the selection process while ensuring that the chosen items yield the minimum total cost.

Intuition

The key intuition is to leverage a priority queue (min-heap) to always pick the smallest available cost from either end of the array. By considering only a limited number of candidates from both ends (based on the candidates parameter), we can efficiently manage the selection process. As we move inward after each selection, we need to maintain the priority queue to reflect the current smallest choices from the remaining candidates.

Approach

1. Initialize the Priority Queue: Start by initializing a priority queue (min-heap) that will store pairs of costs and their respective indices.

2. Add Initial Candidates: Add the initial candidates number of elements from both the left and right ends of the array to the priority queue. These will be the potential items to consider for selection.

3. Iteratively Select Items: For each of the k selections:

   • Pop the smallest element from the priority queue.
   • Add its cost to the total cost.
   • Depending on whether the popped element was from the left or right, move the boundary inward and add the new boundary element to the priority queue.

4. Return the Result: After k iterations, return the accumulated total cost as the result.

Complexity

Time Complexity:

O(k * log(candidates)). Adding and removing elements from the priority queue (min-heap) takes O(log(candidates)) time, and we perform this operation k times.

Space Complexity:

O(candidates). The space is primarily used by the priority queue, which at most will contain candidates elements.

Code

C++

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        long long total = 0;
        int n = costs.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        int left = 0;
        int right = n - 1;

        for (int i = 0; i < candidates; ++i) {
            if (left <= right) {
                pq.emplace(costs[left], left);
                ++left;
            }
            if (left <= right) {
                pq.emplace(costs[right], right);
                --right;
            }
        }

        for (int i = 0; i < k; ++i) {
            auto [cost, index] = pq.top();
            pq.pop();
            total += cost;

            if (index < left) {
                if (left <= right) {
                    pq.emplace(costs[left], left);
                    ++left;
                }
            } else {
                if (left <= right) {
                    pq.emplace(costs[right], right);
                    --right;
                }
            }
        }

        return total;
    }
};

Python

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        total = 0
        pq = []
        
        left = 0
        right = n - 1
        
        for i in range(candidates):
            if left <= right:
                heapq.heappush(pq, (costs[left], left))
                left += 1
            if left <= right:
                heapq.heappush(pq, (costs[right], right))
                right -= 1

        for i in range(k):
            cost, index = heapq.heappop(pq)
            total += cost

            if index < left:
                if left <= right:
                    heapq.heappush(pq, (costs[left], left))
                    left += 1
            else:
                if left <= right:
                    heapq.heappush(pq, (costs[right], right))
                    right -= 1

        return total

Java

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        long total = 0;
        int n = costs.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        int left = 0;
        int right = n - 1;

        for (int i = 0; i < candidates; i++) {
            if (left <= right) {
                pq.add(new int[]{costs[left], left});
                left++;
            }
            if (left <= right) {
                pq.add(new int[]{costs[right], right});
                right--;
            }
        }

        for (int i = 0; i < k; i++) {
            int[] top = pq.poll();
            int cost = top[0];
            int index = top[1];
            total += cost;

            if (index < left) {
                if (left <= right) {
                    pq.add(new int[]{costs[left], left});
                    left++;
                }
            } else {
                if (left <= right) {
                    pq.add(new int[]{costs[right], right});
                    right--;
                }
            }
        }

        return total;
    }
}

JavaScript

var totalCost = function (costs, k, candidates) {
    let n = costs.length;
    let total = 0;
    let queue = new PriorityQueue({compare: (a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return a[0] - b[0];
    }});

    let left = 0;
    let right = n - 1;

    for (let i = 0; i < candidates; i++) {
        if (left <= right) {
            queue.enqueue([costs[left], left]);
            left++;
        }
        if (left <= right) {
            queue.enqueue([costs[right], right]);
            right--;
        }
    }
    for (let i = 0; i < k; i++) {
        let [cost, index] = queue.dequeue();
        total += cost;

        if (index < left) {
            if (left <= right) {
                queue.enqueue([costs[left], left]);
                left++;
            }
        } else {
            if (left <= right) {
                queue.enqueue([costs[right], right]);
                right--;
            }
        }
    }
    return total;
};