How hard is LeetCode 1167. Minimum Cost to Connect Sticks?

LeetCode 1167. Minimum Cost to Connect Sticks is rated Medium on LeetCode.

What is the time complexity of LeetCode 1167. Minimum Cost to Connect Sticks?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1167. Minimum Cost to Connect Sticks?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1167. Minimum Cost to Connect Sticks cover?

LeetCode 1167. Minimum Cost to Connect Sticks is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.

Is LeetCode 1167. Minimum Cost to Connect Sticks a premium problem?

Yes. LeetCode 1167. Minimum Cost to Connect Sticks is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Minimum Cost to Connect Sticks — LeetCode 1167 Python Solution

MediumLeetCode PremiumGreedyArrayHeap (Priority Queue)

Problem: #1167
Pattern: Heap / Priority Queue
Reading time: 2 min
Source: leetcode.com

The problem

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

Example

Input: sticks = [2,4,3]
Output: 14
Explanation: You start with sticks = [2,4,3].

Python solution

Python

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heapify(sticks)
        ans = 0
        while len(sticks) > 1:
            z = heappop(sticks) + heappop(sticks)
            ans += z
            heappush(sticks, z)
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1167. Minimum Cost to Connect Sticks is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1167. Minimum Cost to Connect Sticks?: LeetCode 1167. Minimum Cost to Connect Sticks is rated Medium on LeetCode.
What is the time complexity of LeetCode 1167. Minimum Cost to Connect Sticks?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1167. Minimum Cost to Connect Sticks?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1167. Minimum Cost to Connect Sticks cover?: LeetCode 1167. Minimum Cost to Connect Sticks is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.
Is LeetCode 1167. Minimum Cost to Connect Sticks a premium problem?: Yes. LeetCode 1167. Minimum Cost to Connect Sticks is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.