Problem of The Day: Maximum Beauty of an Array After Applying Operation

Problem Statement

Brute Force [TLE]

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        intervals = []
        lower, upper = float('inf'), float('-inf')
        beauty = 0
        for num in nums:
            intervals.append([num - k, num + k])
            lower = min(lower, num - k)
            upper = max(upper, num + k)
        intervals.sort()
        for i in range(lower, upper + 1):
            count = 0
            for interval in intervals:
                if i in list(range(interval[0], interval[1] + 1)):
                    count += 1
            beauty = max(beauty, count)
        return beauty

Other Approach [TLE]

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        intervals = []
        lower, upper = float('inf'), float('-inf')
        beauty = 0
        for num in nums:
            intervals.append([num - k, num + k])
            lower = min(lower, num - k)
            upper = max(upper, num + k)
        intervals.sort()
        n = len(intervals)
        for i in range(n):
            start, end = intervals[i]
            count = 0
            for j in range(i + 1, n):
                curr_start, curr_end = intervals[j]
                if curr_start <= end <= curr_end:
                    count += 1
            beauty = max(beauty, count)

        return beauty + 1

Editorial

Approach 2: Sliding Window

class Solution:
    def maximumBeauty(self, nums: list[int], k: int) -> int:
        nums.sort()
        left = 0
        max_beauty = 0

        # Iterate through the array with the right pointer
        for right in range(len(nums)):
            # Move the left pointer to maintain the valid range
            while nums[right] - nums[left] > 2 * k:
                left += 1
            # Update the maximum beauty based on the current range
            # We do not add 1 here as right is already pointing to one position beyond the valid range.
            max_beauty = max(max_beauty, right - left + 1)

        return max_beauty

Sweep line Algorithm

class Solution:
    def maximumBeauty(self, nums: list[int], k: int) -> int:
        # Extend the range for each element in nums
        events = []
        for num in nums:
            events.append((num - k, 1))  # Start of range
            events.append((num + k + 1, -1))  # End of range (exclusive)

        # Sort events by value, and in case of tie, by type of event
        events.sort()

        # Use a sweep line approach to calculate the maximum overlap
        max_beauty = 0
        current_count = 0
        for value, effect in events:
            current_count += effect
            max_beauty = max(max_beauty, current_count)

        return max_beauty