What is the time complexity of LeetCode 2779. Maximum Beauty of an Array After Applying Operation?

The Python solution on this page runs in O(M + 2 \times k + n).

What is the space complexity of LeetCode 2779. Maximum Beauty of an Array After Applying Operation?

The Python solution on this page uses O(M + 2 \times k) auxiliary space.

Maximum Beauty of an Array After Applying Operation — LeetCode 2779 Python Solution

MediumArrayBinary SearchSortingSliding Window

Problem: #2779
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

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 i that hasn't been chosen before from the range [0, nums.length - 1].

Example

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:

Python solution

Python

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        m = max(nums) + k * 2 + 2
        d = [0] * m
        for x in nums:
            d[x] += 1
            d[x + k * 2 + 1] -= 1
        return max(accumulate(d))

Complexity

Measure	Complexity
Time	O(M + 2 \times k + n)
Space	O(M + 2 \times k) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2779. Maximum Beauty of an Array After Applying Operation is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2779. Maximum Beauty of an Array After Applying Operation?: LeetCode 2779. Maximum Beauty of an Array After Applying Operation is rated Medium on LeetCode.
What is the time complexity of LeetCode 2779. Maximum Beauty of an Array After Applying Operation?: The Python solution on this page runs in O(M + 2 \times k + n).
What is the space complexity of LeetCode 2779. Maximum Beauty of an Array After Applying Operation?: The Python solution on this page uses O(M + 2 \times k) auxiliary space.
What topics does LeetCode 2779. Maximum Beauty of an Array After Applying Operation cover?: LeetCode 2779. Maximum Beauty of an Array After Applying Operation is tagged Array, Binary Search, Sorting and Sliding Window on LeetCode.