Katkat
Back

Minimize Replacements So Equal Product Values Are Contiguous

AmazonSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize data transformations by identifying contiguous blocks of identical values, modeled as a shortest-path or dynamic programming problem on a compressed representation of the array.

Problem Statement

You are given an array of integers representing product values. You can perform an operation: choose a value x and change all occurrences of x in the array to y. The cost of this operation is the number of occurrences of x. Your goal is to reach a state where each distinct value remaining in the array occupies a single contiguous block, minimizing the total cost of all operations performed.

Input

  • arr: A list of integers where 1 <= arr[i] <= 10^5 and len(arr) <= 200,000.

Output

  • Return the minimum total cost to make each value contiguous.

Examples

Example 1: Input: [1, 2, 1] Output: 1 Explanation: Change the single 2 to 1 (cost 1). The array becomes [1, 1, 1], which is contiguous.

Example 2: Input: [1, 2, 3, 2, 1] Output: 2 Explanation: Change 2 to 1 (cost 2) to get [1, 1, 3, 1, 1], then change 3 to 1 (cost 1). Total cost 3? No, a better way: change the inner 2 to 3 or change both 2s to 1? Actually, changing the 3 to 2 (cost 1) gives [1, 2, 2, 2, 1], then change 2 to 1 (cost 2) gives [1, 1, 1, 1, 1]. Total 3. Wait, the optimal path is changing 2 to 3 (cost 2) to get [1, 3, 3, 3, 1], then 3 to 1 (cost 1). The goal is to minimize total operations.

Constraints

  • Time Complexity: O(N log N) or O(N)
  • Space Complexity: O(N)

Hints

Hint 1

First, compress the array by merging adjacent identical elements, since adjacent duplicates are already contiguous.

Hint 2

Think of the array as a sequence of blocks; the problem is equivalent to choosing an order of merging blocks until only one type of value remains.

Hint 3

This can be modeled as a graph problem where nodes are distinct values and an edge exists if one value separates another; the goal is to resolve these dependencies with minimum weight.

Follow-up questions

  • How does the complexity change if you are restricted to only merging values that are currently adjacent in the compressed array?
  • Can you solve this using a greedy approach, or does it require dynamic programming/priority queues?
  • What if you were given a limit on how many distinct values can exist in the final array?