2779. Maximum Beauty of an Array After Applying Operation

Maximum Beauty of an Array After Applying Operation (LeetCode 2779) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

How to solve Maximum Beauty of an Array After Applying Operation

Maximum Beauty of an Array After Applying Operation is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Work towards the solution in these steps:

1. Sort the array.
2. The problem becomes the following: find maximum subarray A[i … j] such that A[j] - A[i] ≤ 2 * k.

The reference solution runs in O(nlogn) time and O(1) space.

The Maximum Beauty of an Array After Applying Operation solution and editorial walks through the full approach with reference code.

Problem statement

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

- Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].

- Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].

The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return the maximum possible beauty of the array nums after applying the operation any number of times.

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

Example 1:

Input: nums = [4,6,1,2], k = 2 Output: 3 Explanation: In this example, we apply the following operations: - Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2]. - Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4]. After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3). It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10 Output: 4 Explanation: In this example we don't have to apply any operations. The beauty of the array nums is 4 (whole array).

Constraints:

- 1 <= nums.length <= 105

- 0 <= nums[i], k <= 105

Topics and companies

Topics: Array, Binary Search, Sliding Window, Sorting.

How to practise Maximum Beauty of an Array After Applying Operation on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(1) space.

Open Maximum Beauty of an Array After Applying Operation in the code editor, or read the Maximum Beauty of an Array After Applying Operation editorial for a worked solution with its approach and complexity analysis.

Where Maximum Beauty of an Array After Applying Operation sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet

Problems related to Maximum Beauty of an Array After Applying Operation

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Frequency of the Most Frequent Element — Medium, same subpattern
• Fruit Into Baskets — Medium, same subpattern
• Jump Game VII — Medium, same subpattern

Maximum Beauty of an Array After Applying Operation FAQ