3397. Maximum Number of Distinct Elements After Operations
Approach
Sort; greedy assign each element the smallest available value ≥ nums[i]-k.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Sort; greedy assign each element the smallest available value ≥ nums[i]-k.
// Time: O(n log n) Space: O(1)
public class Solution
{
public int MaxDistinctElements(int[] nums, int k)
{
Array.Sort(nums);
int n = nums.Length;
int distinctCount = 0;
int previousValue = int.MinValue;
foreach (int currentNum in nums)
{
int optimalValue = Math.Min(currentNum + k, Math.Max(currentNum - k, previousValue + 1));
if (optimalValue > previousValue)
{
distinctCount++;
previousValue = optimalValue;
}
}
return distinctCount;
}
}