Maximum Frequency After Subarray Operation

Maximum Frequency After Subarray Operation - Problem

Array Hash Table Dynamic Programming Greedy Enumeration Prefix Sum Medium

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.

Input & Output

Example 1 — Basic Transformation

$ Input: nums = [1,2,4,2], k = 4

› Output: 3

💡 Note: Select subarray [1,3] and add x=2. Array becomes [1,4,4,4]. The frequency of 4 is 3.

Example 2 — No Transformation Needed

$ Input: nums = [1,4,4,2,4], k = 4

› Output: 4

💡 Note: Select subarray [3,3] and add x=2. Array becomes [1,4,4,4,4]. The frequency of 4 is 4.

Example 3 — Single Element

$ Input: nums = [5], k = 3

› Output: 1

💡 Note: Select subarray [0,0] and add x=-2. Array becomes [3]. The frequency of 3 is 1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i], k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,4,2] with target k=4

Transform

Add x=2 to subarray [1,3]: elements 2→4, 4→6, 2→4

Result

Array becomes [1,4,6,4], but better choice gives [1,4,4,4]

Key Takeaway

🎯 Key Insight: Try all meaningful transformations on all subarrays to maximize target frequency

Asked in

G Google 12 M Microsoft 8 a Amazon 15

The key insight is that we can transform any subarray by adding the same value to all elements. We need to find the transformation that maximizes the frequency of target k. The optimal approach systematically tries all meaningful transformations on all possible subarrays. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Enumeration	O(n³)	O(n)	Efficiently enumerate all meaningful transformations without redundant calculations
Frequency Count Optimization	O(n²)	O(n)	Group elements by their required transformation value and count efficiently
Brute Force - Try All Subarrays	O(n³)	O(1)	Try every possible subarray and calculate the maximum frequency of k

Optimized Enumeration — Algorithm Steps

Count initial frequency of k
For each unique element value, calculate required transformation
For each transformation, try all possible subarrays
Track maximum frequency achieved

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Unique Transformations

Calculate k - nums[i] for all unique values

Apply Each Transformation

Try each transformation on all subarrays

Track Maximum

Keep track of highest frequency achieved

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int maxFreq = 0;
    
    // Count initial frequency
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == k) maxFreq++;
    }
    
    // Get unique transformation values
    int transformations[2000]; // Assuming reasonable range
    int transformCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int x = k - nums[i];
        if (x == 0) continue;
        
        // Check if already exists
        int exists = 0;
        for (int j = 0; j < transformCount; j++) {
            if (transformations[j] == x) {
                exists = 1;
                break;
            }
        }
        
        if (!exists) {
            transformations[transformCount++] = x;
        }
    }
    
    // Try each transformation with all possible subarrays
    for (int t = 0; t < transformCount; t++) {
        int x = transformations[t];
        
        // Try all subarrays [i,j]
        for (int i = 0; i < numsSize; i++) {
            for (int j = i; j < numsSize; j++) {
                // Count frequency of k after applying transformation x to [i,j]
                int freq = 0;
                for (int idx = 0; idx < numsSize; idx++) {
                    if (i <= idx && idx <= j) {
                        // Element in subarray: nums[idx] + x
                        if (nums[idx] + x == k) {
                            freq++;
                        }
                    } else {
                        // Element outside subarray: nums[idx]
                        if (nums[idx] == k) {
                            freq++;
                        }
                    }
                }
                
                if (freq > maxFreq) {
                    maxFreq = freq;
                }
            }
        }
    }
    
    return maxFreq;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n) unique values × O(n²) subarrays × O(n) to count frequency

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store unique transformation values

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

180 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler