Maximum Number of Distinct Elements After Operations

Maximum Number of Distinct Elements After Operations

What is this problem about?

The Maximum Number of Distinct Elements After Operations coding problem gives you an array of integers and a value k. For each element, you can change it to any value in the range [element - k, element + k]. Maximize the number of distinct values in the resulting array. Each element is changed independently, but elements with the same target value would not be distinct.

Why is this asked in interviews?

Meta, Amazon, Google, and Bloomberg include this problem because it has a clean greedy solution that requires insight: process elements in sorted order and greedily assign the smallest valid target value that maintains distinctness. Candidates who recognize this greedy is globally optimal (not just locally) demonstrate strong mathematical reasoning.

Algorithmic pattern used

Greedy with sorting: Sort the array. Process elements in sorted order. Maintain prev = the last assigned value (start at -infinity). For each element x:

• The valid range for this element is [x - k, x + k].
• Assign the smallest value in [x - k, x + k] that is greater than prev (to maintain distinctness).
• If x - k > prev + 1: assign x - k (leave a gap, no need to squeeze).
• If prev + 1 <= x + k: assign prev + 1 (squeeze in next consecutive value).
• Else: can't make this element distinct; skip it (it stays non-distinct but we count only distinct).

Count elements successfully assigned distinct values.

Example explanation

Array: [1, 2, 3], k = 2.

• Sorted: [1, 2, 3]. prev = -inf.
• x=1, range=[-1,3]. Assign -1 (smallest valid > -inf). prev=-1. Count=1.
• x=2, range=[0,4]. Assign 0 (prev+1=0, 0 in [0,4]). prev=0. Count=2.
• x=3, range=[1,5]. Assign 1. prev=1. Count=3.
• All 3 distinct. Answer=3.

Array: [1, 1, 1], k = 1.

• Sorted: [1,1,1]. prev=-inf.
• x=1, range=[0,2]. Assign 0. prev=0. Count=1.
• x=1, range=[0,2]. Assign 1. prev=1. Count=2.
• x=1, range=[0,2]. Assign 2. prev=2. Count=3.
• Answer=3.

Common mistakes candidates make

• Not sorting first: Processing in arbitrary order leads to suboptimal assignments where earlier elements block later ones unnecessarily.
• Assigning largest possible value: Greedily assigning the largest (x + k) is wrong — it wastes room for future elements. Always assign the smallest valid value.
• Counting elements that couldn't get distinct values: Only count elements that received a distinct value within their valid range.

Interview preparation tip

For the Array Sorting Greedy interview pattern, the "assign smallest valid distinct value" greedy is a powerful pattern for distinct assignment problems. The key: sorted order + greedy minimum valid assignment = maximum distinct count. Practice on similar problems like "assign unique integers to minimize max" to internalize the technique.