Compute sum of minima with removals
Overview
This question evaluates algorithmic problem-solving, array manipulation, and handling dynamic removals and indexing within the Coding & Algorithms domain. It is commonly asked to assess the ability to design efficient procedures, reason about edge cases and time complexity, and focuses on practical application and implementation skills rather than purely conceptual theory.
You are given an array weights[0..n-1] of positive integers representing product weights in a line. Repeat until no products remain: choose the lightest remaining product (if multiple, choose the one with the smallest current index), add its weight to a running total, and remove it along with up to its two current neighbors—one on the left and one on the right if they still exist. If only one neighbor exists, remove just that neighbor. Return the final total. Example: weights = [4, 3, 2, 1] -> choose 1 (remove 2 and 1), remaining [4, 3]; choose 3 (remove 3 and 4); total = 1 + 3 = 4. Implement a function that returns this total for any input array.