Maximum Beauty of an Array After Applying Operation solution and explanation
Google
9 more videos on this problem
Maximum Beauty of an Array After Applying Operation - Leetcode 2779 - PythonNeetCodeIO · 11:59 · 9K views
Maximum Beauty of an Array After Applying Operation | 3 Approaches | Leetcode 2779 |codestorywithMIKcodestorywithMIK · 58:36 · 9K views
Maximum Beauty of an Array After Applying Operation | Leetcode 2779Techdose · 15:38 · 3K views
2779. Maximum Beauty of an Array After Applying Operation | Prefix Sums | Sliding WindowAryan Mittal · 16:14 · 2K views
2779. Maximum Beauty of an Array After Applying Operation | leetcode daily challenge | shashcode30ShashCode · 17:33 · 1K views
2779. Maximum Beauty of an Array After Applying Operation (Leetcode Medium)Programming Live with Larry · 9:02 · 778 views
Maximum Beauty of an Array After Applying Operation - Leetcode 2779 | Weekly Contest 354Algorithms Casts · 13:34 · 606 views
LeetCode 2779 Maximum Beauty of an Array After Applying Operation | Binary Search | Asked in GoogleCode Harmony · 20:53 · 394 views
Daily Leetcode #1716: Dec 11, 2024 - 2779. Maximum Beauty of an Array After Applying OperationProgramming Live with Larry · 12:26 · 325 views
2779. Maximum Beauty of an Array After Applying Operation | Leetcode Weekly Contest 354 | MediumAman Babu · 5:56 · 143 views
The problem
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
ithat 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 <= 1050 <= nums[i], k <= 105
Approach overview
Problem Overview: You are given an integer array nums and a value k. Each element can be increased or decreased by at most k. After performing the operation on every element, the goal is to maximize the beauty of the array, defined as the largest number of equal elements. The task reduces to finding the largest group of values that can be adjusted to the same number.
Approach 1: Sorting and Two Pointer Technique (O(n log n) time, O(1) space)
Sort the array first using sorting. If two numbers differ by at most 2 * k, they can be adjusted to the same value because each can move within the range [num - k, num + k]. After sorting, use a sliding window with two pointers. Expand the right pointer while the condition nums[right] - nums[left] <= 2 * k holds. If the difference exceeds this limit, move the left pointer forward to shrink the window. The window size represents how many elements can be transformed into the same value. Track the maximum window length during the scan. Sorting costs O(n log n) time and the two-pointer pass is linear.
Approach 2: HashMap Frequency Counting with Range Sweep (O(n log n) time, O(n) space)
Instead of sorting values directly, treat each number as an adjustable interval [num - k, num + k]. Use a HashMap or ordered map to perform a line sweep. Add +1 at num - k and -1 at num + k + 1. After inserting all updates, iterate through the sorted keys and maintain a running prefix sum to compute how many intervals overlap at each point. The highest overlap corresponds to the maximum beauty. This method resembles prefix-difference techniques often used with arrays and interval problems. Sorting the keys leads to O(n log n) time complexity with O(n) extra space.
Recommended for interviews: The sorting + two pointer solution is the most expected answer. It shows strong understanding of sliding window patterns and how value ranges translate into window constraints. The interval sweep idea is also valid, but interviewers typically prefer the two-pointer approach because it is simpler, memory efficient, and easier to implement under time pressure.
Approach 1: Approach 1: Sorting and Two Pointer Technique
In this approach, we first sort the array. The idea is to use a two-pointer technique to choose a number range such that the numbers in this range can be adjusted by k to be the same. We sort the array and then for each element, expand the range using a two-pointer to see how many elements can be adjusted to fall in the range [nums[i]-k, nums[i]+k].
def max_beauty(nums, k):
nums.sort()
max_beauty = 1
i = 0
for j in range(len(nums)):
while nums[j] - nums[i] > 2 * k:
i += 1
max_beauty = max(max_beauty, j - i + 1)
return max_beauty
nums = [4, 6, 1, 2]
k = 2
print(max_beauty(nums, k)) # Output: 3import java.util.Arrays;
public class Solution {
public int maxBeauty(int[] nums, int k) {
Arrays.sort(nums);
int maxBeauty = 1;
int i = 0;
for (int j = 0; j < nums.length; j++) {
while (nums[j] - nums[i] > 2 * k) {
i++;
}
maxBeauty = Math.max(maxBeauty, j - i + 1);
}
return maxBeauty;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 1, 2};
int k = 2;
System.out.println(solution.maxBeauty(nums, k)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxBeauty(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int max_beauty = 1;
int i = 0;
for (int j = 0; j < nums.size(); ++j) {
while (nums[j] - nums[i] > 2 * k) {
++i;
}
max_beauty = std::max(max_beauty, j - i + 1);
}
return max_beauty;
}
int main() {
std::vector<int> nums = {4, 6, 1, 2};
int k = 2;
std::cout << maxBeauty(nums, k) << std::endl; // Output: 3
return 0;
}function maxBeauty(nums, k) {
nums.sort((a, b) => a - b);
let maxBeauty = 1;
let i = 0;
for (let j = 0; j < nums.length; j++) {
while (nums[j] - nums[i] > 2 * k) {
i++;
}
maxBeauty = Math.max(maxBeauty, j - i + 1);
}
return maxBeauty;
}
const nums = [4, 6, 1, 2];
const k = 2;
console.log(maxBeauty(nums, k)); // Output: 3;#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int max_beauty(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
int max_beauty = 1;
int i = 0;
for (int j = 0; j < numsSize; j++) {
while (nums[j] - nums[i] > 2 * k) {
i++;
}
if (j - i + 1 > max_beauty) {
max_beauty = j - i + 1;
}
}
return max_beauty;
}
int main() {
int nums[] = {4, 6, 1, 2};
int k = 2;
int result = max_beauty(nums, 4, k);
printf("%d\n", result); // Output: 3
return 0;
}using System;
public class Solution {
public int MaxBeauty(int[] nums, int k) {
Array.Sort(nums);
int maxBeauty = 1;
int i = 0;
for (int j = 0; j < nums.Length; j++) {
while (nums[j] - nums[i] > 2 * k) {
i++;
}
maxBeauty = Math.Max(maxBeauty, j - i + 1);
}
return maxBeauty;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 1, 2};
int k = 2;
Console.WriteLine(solution.MaxBeauty(nums, k)); // Output: 3
}
}The function sorts the list nums and initializes two pointers: 'i', set to the start of the list, and 'j', which iterates over each element. It verifies conditions with nums[j] and nums[i] within a window dictated by k. The while loop refines this range by moving 'i' forward when the difference breaches 2 * k, allowing for the identification of longest valid subsequence.
Time Complexity: O(n log n) due to sorting and accompanying O(n) pass.
Space Complexity: O(n) for input storage, with constant space for variables.
Approach 2: Approach 2: Using a HashMap for Frequency Counting
In this approach, we use a HashMap to count the occurrences of each element.. Then, for every element in the array, determine how many other elements can be adjusted to equal it given the range constraints. This involves counting up possible element choices within the range [x-k, x+k] for each x after adjusting with known positions.
def max_beauty(nums, k):
freq_map = {}
for num in nums:
freq_map[num - k] = freq_map.get(num - k, 0) + 1
freq_map[num + k + 1] = freq_map.get(num + k + 1, 0) - 1
max_beauty = 0
current = 0
for key in sorted(freq_map.keys()):
current += freq_map[key]
max_beauty = max(max_beauty, current)
return max_beauty
nums = [4, 6, 1, 2]
k = 2
print(max_beauty(nums, k)) # Output: 3import java.util.TreeMap;
public class Solution {
public int maxBeauty(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
map.put(num - k, map.getOrDefault(num - k, 0) + 1);
map.put(num + k + 1, map.getOrDefault(num + k + 1, 0) - 1);
}
int maxBeauty = 0, current = 0;
for (int value : map.values()) {
current += value;
maxBeauty = Math.max(maxBeauty, current);
}
return maxBeauty;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 1, 2};
int k = 2;
System.out.println(solution.maxBeauty(nums, k)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int maxBeauty(std::vector<int>& nums, int k) {
std::unordered_map<int, int> freqMap;
for (int num : nums) {
freqMap[num - k]++;
freqMap[num + k + 1]--;
}
int max_beauty = 0, current = 0;
for (auto& [key, value] : freqMap) {
current += value;
if (current > max_beauty) {
max_beauty = current;
}
}
return max_beauty;
}
int main() {
std::vector<int> nums = {4, 6, 1, 2};
int k = 2;
std::cout << maxBeauty(nums, k) << std::endl; // Output: 3
return 0;
}function maxBeauty(nums, k) {
let freqMap = new Map();
nums.forEach(num => {
freqMap.set(num - k, (freqMap.get(num - k) || 0) + 1);
freqMap.set(num + k + 1, (freqMap.get(num + k + 1) || 0) - 1);
});
let maxBeauty = 0, current = 0;
Array.from(freqMap.keys()).sort((a, b) => a - b).forEach(key => {
current += freqMap.get(key);
maxBeauty = Math.max(maxBeauty, current);
});
return maxBeauty;
}
const nums = [4, 6, 1, 2];
const k = 2;
console.log(maxBeauty(nums, k)); // Output: 3;#include <stdio.h>
#include <string.h>
int max_beauty(int* nums, int numsSize, int k) {
int freq[200001];
memset(freq, 0, sizeof(freq));
for (int i = 0; i < numsSize; i++) {
freq[nums[i] + k]++;
freq[nums[i] - k]--;
}
int max_beauty = 0, current = 0;
for (int i = 0; i < 200001; i++) {
current += freq[i];
if (current > max_beauty) {
max_beauty = current;
}
}
return max_beauty;
}
int main() {
int nums[] = {4, 6, 1, 2};
int k = 2;
int result = max_beauty(nums, 4, k);
printf("%d\n", result); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxBeauty(int[] nums, int k) {
SortedDictionary<int, int> freqMap = new SortedDictionary<int, int>();
foreach (var num in nums) {
if (!freqMap.ContainsKey(num - k))
freqMap[num - k] = 0;
if (!freqMap.ContainsKey(num + k + 1))
freqMap[num + k + 1] = 0;
freqMap[num - k]++;
freqMap[num + k + 1]--;
}
int maxBeauty = 0, current = 0;
foreach (var value in freqMap.Values) {
current += value;
maxBeauty = Math.Max(maxBeauty, current);
}
return maxBeauty;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 1, 2};
int k = 2;
Console.WriteLine(solution.MaxBeauty(nums, k)); // Output: 3
}
}Leveraging an auxiliary hash map and extending into a sorted examination of results affords us calculation in feasible changes. Each movement noted in this construct counts resulting frequency and provides toward maximizing repeats in adjustments.
Time Complexity: O(n log n) primarily caused by sorted keys of hash map.
Space Complexity: O(n); accounted for by hash map.
Approach 3: Difference Array
We notice that for each operation, all elements within the interval [nums[i]-k, nums[i]+k] will increase by 1. Therefore, we can use a difference array to record the contributions of these operations to the beauty value.
In the problem, nums[i]-k might be negative. We add k to all elements to ensure the results are non-negative. Thus, we can create a difference array d with a length of max(nums) + k times 2 + 2.
Next, we iterate through the array nums. For the current element x being iterated, we increase d[x] by 1 and decrease d[x+ktimes2+1] by 1. In this way, we can calculate the prefix sum for each position using the d array, which represents the beauty value for each position. The maximum beauty value can then be found.
The time complexity is O(M + 2 times k + n), and the space complexity is O(M + 2 times k). Here, n is the length of the array nums, and M is the maximum value in the array nums.
function maximumBeauty(nums: number[], k: number): number {
const m = Math.max(...nums) + k * 2 + 2;
const d: number[] = Array(m).fill(0);
for (const x of nums) {
d[x]++;
d[x + k * 2 + 1]--;
}
let ans = 0;
let s = 0;
for (const x of d) {
s += x;
ans = Math.max(ans, s);
}
return ans;
}func maximumBeauty(nums []int, k int) (ans int) {
m := slices.Max(nums)
m += k*2 + 2
d := make([]int, m)
for _, x := range nums {
d[x]++
d[x+k*2+1]--
}
s := 0
for _, x := range d {
s += x
if ans < s {
ans = s
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two Pointer Technique | Time Complexity: O(n log n) due to sorting and accompanying O(n) pass. |
| Approach 2: Using a HashMap for Frequency Counting | Time Complexity: O(n log n) primarily caused by sorted keys of hash map. |
| Difference Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointer Sliding Window | O(n log n) | O(1) | Best general solution; simple implementation and optimal for interviews |
| HashMap Interval Sweep (Prefix Sum) | O(n log n) | O(n) | Useful when modeling the problem as overlapping ranges or interval counting |
Frequently asked questions
Is Maximum Beauty of an Array After Applying Operation easy or hard?
The problem is rated Medium on LeetCode. The challenge lies in recognizing that each value can shift within [num-k, num+k] and translating that into a constraint on sorted differences. Once this observation is made, a sliding window solution becomes straightforward.
Maximum Beauty of an Array After Applying Operation Python/Java solution
Most implementations sort the array and use two pointers to maintain a window where nums[right] - nums[left] <= 2*k. The window length gives the current beauty, and the maximum across all windows is returned. This approach works efficiently in Python, Java, C++, JavaScript, and other languages.
How to solve Maximum Beauty of an Array After Applying Operation in O(n)?
A pure O(n) solution is difficult because the values need ordering or range processing. The closest approach uses interval counting with prefix sums or a HashMap sweep, but sorting the keys usually leads to O(n log n) time. The practical optimal method remains sorting plus a sliding window.
What is the best approach for Maximum Beauty of an Array After Applying Operation?
The most efficient and interview-preferred approach is sorting the array followed by a sliding window (two pointers). After sorting, maintain a window where the difference between the smallest and largest values is at most 2*k. All numbers in that window can be adjusted to the same value. This solution runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximum Beauty of an Array After Applying Operation asked at Google/Amazon/Meta?
This problem follows a common interview pattern combining sorting and sliding window techniques. Similar range-normalization or frequency-maximization problems appear in interviews at companies like Amazon, Google, and Meta when evaluating array manipulation and two-pointer reasoning.
What data structure is used in Maximum Beauty of an Array After Applying Operation?
The main data structures are arrays (for sorting and window scanning) and optionally a HashMap or ordered map for interval sweep counting. The optimal solution primarily relies on sorting and the sliding window two-pointer pattern.
What is the time complexity of Maximum Beauty of an Array After Applying Operation?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a linear sliding window scan computes the maximum valid group in O(n) time. The space complexity is O(1) if sorting is done in place.