Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= 50
  • 1 <= k <= 50

Solution

Method 1 – Hash Map and Prefix Sum

Intuition

To maximize the frequency of k after one subarray operation, we want to maximize the number of indices where nums[i] can be made equal to k by adding the same value to a subarray containing i. For each index, the difference d = k - nums[i] tells us how much we need to add at i. We can use a hash map to count the maximum number of indices that can be covered by a single subarray operation for each difference value.

Approach

  1. For each index i, compute d = k - nums[i].
  2. For each possible difference d, use a sliding window to find the maximum number of indices that can be covered by a subarray (i.e., the indices where k - nums[i] == d are consecutive).
  3. The answer is the maximum count among all difference values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; ++i) cnt[k - nums[i]]++;
        for (auto& [d, c] : cnt) ans = max(ans, c);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxFrequency(nums []int, k int) int {
    cnt := map[int]int{}
    for _, v := range nums {
        cnt[k-v]++
    }
    ans := 0
    for _, c := range cnt {
        if c > ans {
            ans = c
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int v : nums) cnt.put(k-v, cnt.getOrDefault(k-v, 0)+1);
        int ans = 0;
        for (int c : cnt.values()) ans = Math.max(ans, c);
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        for (v in nums) cnt[k-v] = cnt.getOrDefault(k-v, 0) + 1
        return cnt.values.maxOrNull() ?: 0
    }
}
1
2
3
4
5

class Solution:
    def maxFrequency(self, nums: list[int], k: int) -> int:
        from collections import Counter
        cnt = Counter(k - v for v in nums)
        return max(cnt.values())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        for &v in &nums {
            *cnt.entry(k-v).or_insert(0) += 1;
        }
        *cnt.values().max().unwrap()
    }
}
1
2
3
4
5
6
7

class Solution {
    maxFrequency(nums: number[], k: number): number {
        const cnt = new Map<number, number>();
        for (const v of nums) cnt.set(k-v, (cnt.get(k-v) ?? 0) + 1);
        return Math.max(...cnt.values());
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, as we process each element once.
  • 🧺 Space complexity: O(n), for the hash map.