3347. Maximum Frequency of an Element After Performing Operations II
Approach
Sort; binary search for window boundaries; sliding window over sorted unique targets.
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.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Sort; binary search for window boundaries; sliding window over sorted unique targets.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int MaxFrequency(int[] nums, int k, int numOperations)
{
// Map to store the frequency of each number in the array
Dictionary<int, int> frequencyMap = new Dictionary<int, int>();
// SortedDictionary to track range boundaries and their contributions
// Used for sweep line algorithm to count overlapping ranges
SortedDictionary<int, int> rangeBoundaries = new SortedDictionary<int, int>();
// Process each number in the input array
foreach (int num in nums)
{
// Count frequency of current number
frequencyMap.TryGetValue(num, out int frequency);
frequencyMap[num] = frequency + 1;
// Initialize the number itself as a potential target
if (!rangeBoundaries.ContainsKey(num))
rangeBoundaries[num] = 0;
// Mark the start of range [num - k, num + k] where elements can be changed to num
// Increment at start of range (num - k)
rangeBoundaries.TryGetValue(num - k, out int startCount);
rangeBoundaries[num - k] = startCount + 1;
// Mark the end of range (exclusive) at num + k + 1
// Decrement after end of range
rangeBoundaries.TryGetValue(num + k + 1, out int endCount);
rangeBoundaries[num + k + 1] = endCount - 1;
}
int maxResult = 0;
int currentOverlap = 0; // Running sum of overlapping ranges
// Sweep through all boundary points in sorted order
foreach (KeyValuePair<int, int> entry in rangeBoundaries)
{
int position = entry.Key;
int delta = entry.Value;
// Update the current overlap count
currentOverlap += delta;
// Calculate maximum frequency achievable at this position
// It's the minimum of:
// 1. Total elements that can be changed to this position (currentOverlap)
// 2. Original frequency + allowed operations
frequencyMap.TryGetValue(position, out int originalFrequency);
int achievableFrequency = Math.Min(currentOverlap, originalFrequency + numOperations);
// Update the maximum frequency found so far
maxResult = Math.Max(maxResult, achievableFrequency);
}
return maxResult;
}
}