DDSA Solutions

2779. Maximum Beauty of an Array After Applying Operation

UnknownView on LeetCode
ArrayBinary SearchSorting
Time: O(n log n)
Space: O(1)

Problem Overview

Maximum beauty of array: change each element by at most k, then find longest equal-element subarray.

Intuition

Maximum beauty of array: change each element by at most k, then find longest equal-element subarray. Each element can become any value in [nums[i]-k, nums[i]+k]. Find max overlapping intervals.

Algorithm

  1. 1Sort. Sliding window: window valid if nums[r] - nums[l] <= 2k.

Common Pitfalls

  • •After sorting, a valid window is where max - min <= 2k. Simple sliding window after sort.
2779.cs
C#
// Approach: Sort; sliding window maintaining max - min ≤ 2k; length is beauty.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int MaximumBeauty(int[] nums, int k)
    {
        int ans = 0;

        Array.Sort(nums);

        for (int l = 0, r = 0; r < nums.Length; ++r)
        {
            while (nums[r] - nums[l] > 2 * k)
                ++l;
            ans = Math.Max(ans, r - l + 1);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems