Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Apr 2026

Summary

Amazon coding round for a software engineer role. One algorithmic problem, fairly involved, left me second-guessing my approach the whole time.

Questions Asked (1)

Given an integer array, you can pick any two values x and y and replace every occurrence of x with y in one operation. What is the minimum number of such operations to make the array 'contiguous', meaning no two equal values are separated by a different value?

Algorithms & Data Structures

Author's notes

Took me a while to even understand what 'contiguous' meant in this context.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimum number of value replacements to make each distinct value occupy a contiguous block. This is equivalent to finding the maximum number of distinct values that can remain unchanged, which can be solved by finding the longest subsequence of distinct values that appear in order without interleaving. Use a greedy or dynamic programming approach to compute the minimum operations.

Pro tip: Clarify with the interviewer whether the array can be modified in place and if the operations are independent. Also, consider edge cases like arrays with all identical elements or all distinct elements, as they often reveal the core logic.

1. Understand the problem

Restate the problem in your own words: we can replace all occurrences of one value with another, and we want the final array to have each value in a single contiguous block. The goal is to minimize the number of such replacements.

2. Identify the invariant

Recognize that the relative order of distinct values in the array cannot be changed by replacements; only their grouping can be altered. The problem reduces to finding the minimum number of values to remove (by merging) so that the remaining values appear in contiguous blocks.

3. Formulate as a graph or sequence problem

Construct a graph where nodes are distinct values and edges represent interleaving (i.e., if two values appear alternately, they cannot both remain). The goal is to find the maximum independent set, which is equivalent to the longest subsequence of distinct values that appear in order without interleaving.

4. Design an algorithm

Use dynamic programming or greedy scanning: iterate through the array, track the last occurrence of each value, and compute the longest valid subsequence of distinct values. The minimum operations is (number of distinct values) minus (length of this subsequence).

5. Analyze complexity and test

The algorithm should run in O(n) time and O(k) space, where n is array length and k is number of distinct values. Test with examples like [1,2,1,3] and [1,2,3,1,2] to verify correctness.

Key Points to Mention

The problem is equivalent to finding the minimum number of value replacements to make each distinct value contiguous.
The relative order of distinct values is invariant; only grouping changes.
The maximum number of values that can remain unchanged is the length of the longest subsequence of distinct values that appear in order without interleaving.
This can be solved by dynamic programming or greedy scanning in O(n) time.
Edge cases: all elements same (0 operations), all distinct (n-1 operations if n>1).
The answer is (number of distinct values) minus (length of longest valid subsequence).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.