Leetcode #1167 Minimum cost to connect sticks

Account Login - LeetCode

If you notice the problem closely — what you need is a sorted list of the array everytime. What better data structure to use than a heap?

public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int stick : sticks) {
            pq.offer(stick);
        }
        int cost = 0;
        while(!pq.isEmpty()) {
            if(pq.size() >= 2) {
                int first = pq.poll();
                int second = pq.poll();
                cost += first + second;
                pq.offer(first + second);
            }
            else {
                pq.poll();
            }
        }
        return cost;
    }

Every time we evaluate the cost of the sticks being considered, we add the cost of the first and the second stick polled into the heap again. This continues until there is only one stick left in the heap to be considered.

Time complexity = O(n), space complexity = O(n)