We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Beauty of an Array After Applying Operation

Number: 2891

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array nums and a non-negative integer k, each element nums[i] can be adjusted exactly once to any integer in the interval [nums[i] - k, nums[i] + k]. The goal is to choose adjustments so that the longest subsequence (not necessarily contiguous) of equal elements is as long as possible. Return the maximum possible length of such a subsequence after performing the allowed operations.

Key Insights

  • Each element can be transformed to any value within an interval [nums[i] - k, nums[i] + k].
  • The problem reduces to finding a value x that lies in as many intervals as possible.
  • This is equivalent to a “range overlap” or “sweep line” problem, where overlapping intervals indicate the number of elements that can be made equal to a specific value.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the start and end events. Space Complexity: O(n) for storing the events.

Solution

The main idea is to view each array element as providing an interval of values [nums[i] - k, nums[i] + k] that it can be transformed into. Our objective is to choose a number x that falls within the maximum number of these intervals.

To do this, we:

  1. Transform each element into an interval.
  2. Use a sweep line algorithm: create events for the start and end of each interval. Specifically, for an interval [L, R], add an event +1 at L and an event -1 at R+1.
  3. Sort all the events by the position, then iterate through them while maintaining a running sum. This sum represents the number of intervals covering the current position.
  4. Track the maximum running sum; this value represents the maximum number of intervals overlapping at any point, which is the maximum beauty of the array.

Code Solutions

# Python code solution with detailed comments

def maximum_beauty(nums, k):
    # List to hold all events (start and end events)
    events = []
    
    # Iterate over each number in nums
    for num in nums:
        start = num - k
        end = num + k
        # Start event: +1 at the beginning of the interval
        events.append((start, 1))
        # End event: -1 after the end of the interval
        events.append((end + 1, -1))
    
    # Sort events by their position
    events.sort()
    
    max_overlap = 0  # Will hold the maximum count of overlapping intervals
    current_overlap = 0  # Current count of overlapping intervals
    
    # Process each event in sorted order
    for position, value in events:
        current_overlap += value  # Update current overlap count
        max_overlap = max(max_overlap, current_overlap)  # Update maximum if necessary
    
    return max_overlap

# Example usage
print(maximum_beauty([4,6,1,2], 2))  # Expected output: 3
← Back to All Questions