Amazon SDE Intern Online Assessment Question — Minimum Cost to Make All Array Elements Equal

149
Aug 29, 2026

I encountered this problem in the Amazon SDE Intern Online Assessment. Sharing it here because I found the key observation interesting and it may help others preparing for Amazon OAs.

Problem Description

You are given an integer array arr of length n, representing target display values at n Amazon fulfillment stations arranged in a line from left to right.

You can perform the following operations any number of times:

  1. Left Operation

Choose an index i such that:

1 <= i <= n - 1

Set all positions:

0, 1, ..., i - 1

to arr[i].

The cost of this operation is:

i * arr[i]
2. Right Operation

Choose an index i such that:

0 <= i <= n - 2

Set all positions:

i + 1, i + 2, ..., n - 1

to arr[i].

The cost is:

(n - 1 - i) * arr[i]

The operations can be performed any number of times, including zero.

Find the minimum total cost required to make all elements of the array equal.

Example
arr = [3, 1, 4, 2]

One optimal sequence is:

Step 1

Choose i = 1.

arr[1] = 1

Apply the left operation:

[3, 1, 4, 2]
↓
[1, 1, 4, 2]

Cost:

1 * 1 = 1
Step 2

Choose i = 1 again.

Apply the right operation:

[1, 1, 4, 2]
↓
[1, 1, 1, 1]

Cost:

(4 - 1 - 1) * 1 = 2

Therefore:

Total Cost = 1 + 2 = 3

Answer: 3

Sample Case 0
arr = [1, 1, 2, 1, 1]

The existing 1s form a prefix and suffix.

Choose i = 1:

[1, 1, 2, 1, 1]
↓
[1, 1, 1, 1, 1]

Cost:

(5 - 1 - 1) * 1 = 3

Answer: 3

Sample Case 1
arr = [1, 1, 3]

Choose i = 1 and apply the right operation:

[1, 1, 3]
↓
[1, 1, 1]

Cost:

(3 - 1 - 1) * 1 = 1

Answer: 1

Key Observation

The important part is to look at contiguous runs of the same value.

Suppose a value v appears continuously from index l to index r:

... v v v v ...
l r

We can use this existing block as the source of v.

To make the entire array equal to v:

Use a Left Operation at index l to change everything before the block.

Cost:

l * v
Use a Right Operation at index r to change everything after the block.

Cost:

(n - 1 - r) * v

Therefore, the total cost for this block is:

l * v + (n - 1 - r) * v

or:

(l + n - 1 - r) * v

We simply need to examine every contiguous block and take the minimum cost.

Example

For:

arr = [3, 1, 1, 4, 2]

The block:

1 1

is from l = 1 to r = 2.

Cost:

1 * 1 + (4 - 2) * 1
= 1 + 2
= 3
O(n) Approach

We scan the array once.

For every contiguous block:

Store its starting index l.
Find its ending index r.
Let v = arr[l].
Calculate:
cost = (l + n - 1 - r) * v
Update the minimum answer.

No extra array is required.

Python Solution
def getMinCost(arr):
n = len(arr)

if n <= 1:
    return 0

ans = float('inf')
l = 0

while l < n:
    r = l

    # Find the end of the current contiguous block
    while r + 1 < n and arr[r + 1] == arr[l]:
        r += 1

    v = arr[l]

    # Cost to fill everything outside this block
    cost = (l + (n - 1 - r)) * v

    ans = min(ans, cost)

    l = r + 1

return ans

Complexity
Time Complexity: O(n)
Space Complexity: O(1)

Since every element belongs to exactly one contiguous block, the total number of iterations is O(n).

One thing I'd like to confirm

This was asked in the Amazon SDE Intern Online Assessment, and the problem statement above is from the assessment screen.

If anyone has encountered the same problem, please share if there is another way to derive the solution or a different interpretation of the operations.

Comments (1)