We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Connect Sticks

Number: 1126

Difficulty: Medium

Paid? Yes

Companies: Amazon, J.P. Morgan, Google

Problem Description

Given an array of stick lengths, the goal is to connect all the sticks into one stick. At each step, you can connect any two sticks with lengths x and y at a cost of x + y. The task is to determine the minimum total cost required to connect all the sticks.

Key Insights

  • Always connect the two smallest sticks available to minimize the incremental cost.
  • A min-heap (or priority queue) is an ideal data structure to efficiently retrieve the smallest sticks.
  • The process continues until only one stick remains.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of sticks (due to heap insertion and removal operations). Space Complexity: O(n), for storing the sticks in the heap.

Solution

The solution uses a greedy algorithm with a min-heap:

  1. Insert all stick lengths into a min-heap.
  2. While there are at least two sticks in the heap:
    • Extract the two smallest sticks.
    • Compute the cost of connecting them (sum the two lengths).
    • Add this cost to the total result.
    • Push the combined stick (with length equal to their sum) back into the heap.
  3. Once the heap is reduced to one element, return the total cost.

This approach ensures that at every connection, the smallest possible sticks are merged, which leads to the minimum overall cost.

Code Solutions

import heapq

def connectSticks(sticks):
    # Initialize the heap with the provided stick lengths
    heapq.heapify(sticks)
    
    # Initialize total cost to 0
    total_cost = 0
    
    # Continue connecting sticks until there is only one left
    while len(sticks) > 1:
        # Extract the two smallest sticks
        stick1 = heapq.heappop(sticks)
        stick2 = heapq.heappop(sticks)
        # Calculate the cost to connect these two sticks
        cost = stick1 + stick2
        # Add the cost to the total cost
        total_cost += cost
        # Push the combined stick back into the heap
        heapq.heappush(sticks, cost)
    
    return total_cost

# Example usage:
# print(connectSticks([2, 4, 3]))  # Output: 14
← Back to All Questions