Minimum Machines to Maintain Efficiency

Problem Description

Note: This is a reconstructed version of an Amazon online assessment question titled “Minimum Machines to Maintain Efficiency”, based on partial public descriptions. Exact original wording and constraints may differ.

A production line consists of n machines arranged in a fixed linear order. Each machine has an integer capacity machines[i]. The efficiency of the line is defined as the sum of absolute differences of capacities between every pair of adjacent machines:

$$ \text{efficiency}(machines) = \sum_{i=0}^{n-2} |machines[i] - machines[i+1]| $$

You are allowed to remove machines from the line (i.e., delete elements from the array), but you must keep the relative order of the remaining machines. The goal is to remove as many machines as possible without changing the total efficiency of the line.

Compute the minimum number of machines that must remain in the line such that the efficiency of the resulting sequence is exactly equal to the efficiency of the original sequence.

Return this minimum number of remaining machines.

Input / Output Format

You can assume the problem is provided as a function to implement:

text int minimumMachinesToMaintainEfficiency(int[] machines)

• Input

  • machines: an array of integers of length n (n ≥ 1), where machines[i] is the capacity of the i‑th machine in the line.

• Output

  • An integer representing the minimum number of machines that must remain so that the efficiency of the line (sum of absolute differences between adjacent capacities) stays unchanged from the original configuration.

Examples

Example 1

Input

text machines = [1, 2, 2, 1, 1]

Step 1 – Original efficiency

$$ |1 - 2| + |2 - 2| + |2 - 1| + |1 - 1| = 1 + 0 + 1 + 0 = 2 $$

Step 2 – Remove machines while preserving efficiency

One valid way:

• Remove the second 2 and one of the trailing 1s (indices 2 and 4 in the original array).
• Remaining machines: [1, 2, 1].

New efficiency:

$$ |1 - 2| + |2 - 1| = 1 + 1 = 2 $$

The efficiency is still 2, the same as the original.

Step 3 – Check minimality

• If only 2 machines remain, the efficiency becomes a single absolute difference, which cannot be 2 for this data while respecting the original order.
• So it is not possible to keep efficiency 2 with fewer than 3 machines.

Output

text 3

Explanation: The minimum number of machines that can remain while maintaining the same efficiency is 3 (for example, [1, 2, 1]).

Example 2

Input

text machines = [5, 4, 4, 4, 3]

Step 1 – Original efficiency

$$ |5 - 4| + |4 - 4| + |4 - 4| + |4 - 3| = 1 + 0 + 0 + 1 = 2 $$

Step 2 – Consider which machines can be removed

Check internal machines (indices 1, 2, 3):

• Index 1: values (5, 4, 4)
  $$ |5 - 4| + |4 - 4| = 1 + 0 = 1,\quad |5 - 4| = 1 $$
  Removing the first 4 (index 1) does not change the contribution of these positions to total efficiency, so it is removable.

• After removing index 1, array becomes [5, 4, 4, 3].

Now check index 1 (new middle value 4 between 5 and 4):

$$ |5 - 4| + |4 - 4| = 1 + 0 = 1,\quad |5 - 4| = 1 $$

So this second 4 is also removable.

• Remove that as well → array becomes [5, 4, 3].

Check efficiency:

$$ |5 - 4| + |4 - 3| = 1 + 1 = 2 $$

The efficiency is still 2.

Step 3 – Check minimality

Can we go down to 2 machines?

• Any 2‑machine subsequence (respecting order) has efficiency |a - b|.
  There is no 2‑element subsequence whose single absolute difference is 2 and that can result from multiple deletions while preserving order and starting from this particular array without reordering in a way that keeps the original total variation; systematically removing “flat” internal points already yielded the best compression [5, 4, 3].

Thus, the minimal number of machines to maintain efficiency 2 here is 3.

Output

text 3

Constraints

Since the exact OA statement is not publicly available, the following are typical and reasonable constraints consistent with how this problem is discussed:

• 1 ≤ n ≤ 2 * 10^5 (number of machines)
• -10^9 ≤ machines[i] ≤ 10^9 (machine capacities can be large in magnitude; often they are non‑negative, but the algorithm does not require that)
• Time complexity target: O(n) or O(n log n); an O(n) greedy/DP solution is expected.
• Space complexity target: O(1) or O(n) extra space, depending on whether you modify in place or just count.

Solution Hint

Observe how removing a middle machine b between neighbors a and c changes the local contribution to efficiency: originally it is |a - b| + |b - c|, and after removal it becomes |a - c|. This value stays the same if and only if b lies between a and c on the number line (i.e., a ≤ b ≤ c or a ≥ b ≥ c). Use this to greedily remove all such “non‑extreme” internal machines and count only the endpoints plus the machines that are strict local minima or maxima.