3434. Maximum Frequency After Subarray Operation - Explanation

Problem Link

Description

You are given an array nums of length n. You are also given an integer k.

You perform the following operation on nums once:

  • Select a subarray nums[i..j] where 0 <= i <= j <= n - 1.
  • Select an integer x and add x to all the elements in nums[i..j].

Find the maximum frequency of the value k after the operation.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,4,5,6], k = 1

Output: 2

Explanation: After adding -5 to nums[2..5], 1 has a frequency of 2 in [1, 2, -2, -1, 0, 1].

Example 2:

Input: nums = [10,2,3,4,5,5,4,3,2,2], k = 10

Output: 4

Explanation: After adding 8 to nums[1..9], 10 has a frequency of 4 in [10, 10, 11, 12, 13, 13, 12, 11, 10, 10].

Constraints:

  • 1 <= nums.length <= 100,000
  • 1 <= nums[i], k <= 50

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        cntK = nums.count(k)
        res = cntK

        for num in range(1, 51):
            if num == k: continue
            for i in range(n):
                tmp, cnt = cntK, 0
                for j in range(i, n):
                    if nums[j] == num:
                        cnt += 1
                    elif nums[j] == k:
                        cntK -= 1
                    res = max(res, cnt + cntK)

                cntK = tmp

        return res

Time & Space Complexity

  • Time complexity: O(50∗n2)O(50 * n ^ 2)
  • Space complexity: O(1)O(1)

2. Kadane's Algorithm - I

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        cntK = nums.count(k)
        res = 0

        for i in range(1, 51):
            if i == k:
                continue
            cnt = 0
            for num in nums:
                if num == i:
                    cnt += 1
                if num == k:
                    cnt -= 1
                cnt = max(cnt, 0)
                res = max(res, cntK + cnt)
        return res

Time & Space Complexity

  • Time complexity: O(50∗n)O(50 * n)
  • Space complexity: O(1)O(1)

3. Kadane's Algorithm - II

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        res = 0
        for num in nums:
            cnt[num] = max(cnt[num], cnt[k]) + 1
            res = max(res, cnt[num] - cnt[k])
        return cnt[k] + res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(50)O(50)