Beat 100% in time and memory, sliding window, accumulatively update median and absolute deviation.
Intuition\n Describe your first thoughts on how to solve this problem. \nThe median minimize the absolution deviation (l1 dorm deviation). Therefore, we sort nu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe median minimize the absolution deviation (l1 dorm deviation). Therefore, we sort nums, and then use a sliding window of increasing size (max_freq) to check the absolution deviation of the subsequence. \n# Approach\nTo avoid exceeding time limit, we accumulatively update the median value and the absolution deviation. \n\n# Complexity\n- Time complexity:\n$$O(nlog(n))$$\n\n- Space complexity:\n$$O(n)$$ \n\n# Code\n```\n# 2968. Apply Operations to Maximize Frequency Score\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        # It seems that the median minimize the absolution deviation (l1 dorm deviation)\n        # Use a sliding window of increasing size (max_freq) to check the absolution deviation\n        # of the subsequence sorted nums. \n        nums.sort()\n        n = len(nums)\n        max_freq = 1\n        \n        # start at i, length = max_freq\n        for i in range(n): \n            if i == 0: \n                # m_index: index for median, 3.5 if median = (nums[3]+nums[4])/2\n                max_freq = 1\n                m_index = 0\n                mm = 0\n                m = nums[m_index]\n                num_op = 0\n            else: \n                m_index +=0.5\n                num_op -=m-nums[i-1]\n\n            while max_freq<n-i:\n                # m = median[i, i+max_freq-1]\n                max_freq+=1\n                # cumulatively update the index for median\n                m_index +=0.5\n                prev_mm = mm \n                prev_m = m \n                mm = math.floor(m_index)\n                if m_index == mm:\n                    m = nums[mm]\n                else: \n                    m = math.floor((nums[mm]+nums[mm+1])*0.5+0.5)\n                # Need to cumuratively update the absolution deviation\n                prev_num_op = num_op\n                num_op+=(prev_mm-i+1)*(m-prev_m) # nums[j]<=prev_m\n                num_op-= (i+max_freq-mm-2)*(m-prev_m) # nums[j]>=m\n                num_op+=nums[i+max_freq-1]-m \n                for j in range(prev_mm+1,mm+1):\n                    # prev_m <= nums[j] <= m\n                    num_op += -(nums[j]-prev_m) + (m-nums[j])\n                if num_op>k:\n                    max_freq-=1\n                    break\n        return max_freq\n\n        \n```
['Sliding Window', 'Python3']