## Problem Given an integer array, repeatedly perform the following operation until one element remains: - Find the two smallest elements, remove them, and insert their sum back into the array. Return the total cost (sum of all inserted sums across all operations). This is equivalent to building an optimal merge tree (Huffman-style). ```python from typing import List def array_reduction(nums: List[int]) -> int: # return the total cost of all merge operations pass ``` **Example:** ``` Input: [4, 3, 2, 6] Step 1: merge 2+3=5, cost=5, array=[4,5,6] Step 2: merge 4+5=9, cost=9, array=[6,9] Step 3: merge 6+9=15, cost=15, array=[15] Output: 5+9+15 = 29 ``` ## Approach Use a min-heap. At each step, pop two smallest elements, compute their sum, accumulate cost, and push the sum back. Time: O(n log n). ## Follow-ups 1. Why does a greedy min-heap strategy provably minimize total cost here? 2. What is the worst-case array that maximizes total cost for a fixed sum of elements? 3. How would the answer change if you could merge any k elements (not just 2) at each step? 4. How would you reconstruct the merge tree, not just the cost?

InterviewDB Question

Array Reduction 4: Reduce an Array by Repeatedly Removing the Minimum Pair Sum

Question Details

Problem Given an integer array, repeatedly perform the following operation until one element remains: Find the two smallest elements, remove them, and insert their sum back into the array. Return the total cost (sum of all inserted sums across all operations). This is equivalent to building an optimal merge tree (Huffman-style). Example: Approach Use a min-heap. At each step, pop two smallest elements, compute their sum, accumulate cost, and push the sum back. Time: O(n log n). Follow-ups Why do…

Full Details

🔒

Unlock all Snowflake questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a snowflake interview during the oa round.

It covers the following topics: Heap, Oa, Greedy, Coding, Arrays .

Topics

Heap Oa Greedy Coding Arrays

Array Reduction 4: Reduce an Array by Repeatedly Removing the Minimum Pair Sum

Question Details

Full Details

About This Question

Topics

More Snowflake Interview Questions