How to optimize subarray transformation for large inputs?

Question

I have a problem where I need to select a contiguous subarray from a list of integers and add any integer z (positive or negative) to all elements in the subarray, such that the frequency of a target integer k is maximized in the list. The operation can only be done once.

Example 1:

list = [2, 3, 2, 4, 3, 2]
k = 2
Answer: 4

Explanation:

We change the subarray [4, 3] and set z = -2, so the list becomes:

[2, 3, 2, (4-2), (3-2), 2] = [2, 3, 2, 2, 1, 2]

The frequency of k = 2 in the final list is 4.

Example 2:

list = [6, 4, 4, 5, 4, 4]
k = 6
Answer: 5

Example 3:

list = [2, 5, 2, 5, 2]
k = 2
Answer: 4

Constraints:

1 <= n <= 2 * 10^5

1 <= list[i] <= 2 * 10^5

1 <= k <= 10^5

Here is the code I have so far:

import java.util.*;

class Main {
    public static int solve(List<Integer> list, int k) {
        int n = list.size();
        int baseCount = 0;

        // Count frequency of `k` in the original list
        for (int num : list) {
            if (num == k) baseCount++;
        }
        
        // Map to track the maximum gain from modifying the list
        Map<Integer, Integer> maxGain = new HashMap<>();
        Map<Integer, Integer> currentGain = new HashMap<>();

        // Traverse the list to compute possible gains
        for (int num : list) {
            if (num == k) {
                // If the number is `k`, we may reduce its frequency (no gain)
                for (int x : currentGain.keySet()) {
                    int gain = currentGain.get(x) - 1;
                    currentGain.put(x, Math.max(gain, 0));
                    maxGain.put(x, Math.max(maxGain.getOrDefault(x, 0), currentGain.get(x)));
                }
            } else {
                // If the number is not `k`, calculate possible gain
                int x = k - num;
                int gain = currentGain.getOrDefault(x, 0) + 1;
                currentGain.put(x, gain);
                maxGain.put(x, Math.max(maxGain.getOrDefault(x, 0), gain));
            }
        }
        
        // Get the best possible gain
        int best = 0;
        for (int g : maxGain.values()) {
            best = Math.max(best, g);
        }

        // Return the sum of original frequency and the best gain
        return baseCount + best;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 3, 2, 4, 3, 2), 2)); // Expected: 4
        System.out.println(solve(Arrays.asList(6, 4, 4, 6, 4, 4), 6)); // Expected: 5
        System.out.println(solve(Arrays.asList(2, 5, 2, 5, 2), 2));    // Expected: 4
    }
}

Problem:

This was asked during an interview on Hackerrank ( I don't have a link for it to share), The solution works for smaller inputs, but when the input list size reaches n = 200,000, it starts to fail with timeout errors.

I am looking for ways to reduce the time complexity of this solution so it can handle large inputs efficiently.

Answer 1

The main slow point in the solution presented is the reduction of all the currentGain values by 1 each time a k is observed in the input. That costs you O(n²), whereas everything else is linear, so that is where you need to focus any algorithmic improvement effort.

So ask yourself a couple questions:

• What if you have a run of consecutive ks? Did you really need to update all the current gains for every one of those?

• What if it turns out that there are no more appearances of a given num in the list at the point where you observe a k. Do you really need to update the current gains for such nums?

In fact, the answer to both of those questions is "no". Consider this enhancement to your current code:

• As you process the list, keep a running count of the number of ks seen. Updating this count is the only thing you need to do when you process a k. Use that count to support ...
• For each number num seen, keep track of the total number of ks that had been seen before last appearance of num. These only need to be updated when you see num, so just one update of one such record per input item.
• For each num (other than k) seen, the previous two items allow you to compute the number of ks between the previous appearance of num and the current one. This number offsets the gain (of 1) associated with the current appearance of num.

That replaces the problematic quadratic update with a single int increment, at the cost of a little more bookkeeping (linear in space and time). Asymptotic complexity drops to O(n).

Here's the main working part of the result:

        Map<Integer, Integer> maxGain = new HashMap<>();
        Map<Integer, Integer> currentGain = new HashMap<>();
        Map<Integer, Integer> ksSeen = new HashMap<>();
        int ks = 0;

        // Traverse the list to compute possible gains
        for (int num : list) {
            if (num == k) {
                ks += 1;
            } else {
                // == ks at the first appearance of each num:
                int ksAtPreviousNum = ksSeen.getOrDefault(num, ks);

                // 0 at the first appearance of each num
                int ksSinceNum = ks - ksAtPreviousNum;

                ksSeen.put(num, ks);

                // gain for 'num' cannot be less than 1 when we're looking at a 'num'
                int gain = Math.max(1, currentGain.getOrDefault(num, 0) + 1 - ksSinceNum);

                currentGain.put(num, gain);
                maxGain.put(num, Math.max(maxGain.getOrDefault(num, 0), gain));
            }
        }