Maximize equal values via one subarray shift
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an integer array A of length n, you may perform at most one operation: choose any contiguous subarray A[l..r] and add an integer Δ (which may be negative, zero, or positive) to every element in A[l..r]. After the operation (or choosing not to use it), what is the maximum possible frequency of any value in the array? Also return one optimal choice of (l, r, Δ) that achieves this maximum. For example, for A = [2, 4, 6, 2, 4, 7], selecting subarray [4,6,2,4] and adding Δ = −2 yields [2, 2, 4, 0, 2, 7], producing three 2s.
Quick Answer: This question evaluates a candidate's understanding of array manipulation, frequency analysis, range-update reasoning, and optimization under a single contiguous subarray operation.
Given an integer array `A` of length `n`, you may perform **at most one** operation: choose any contiguous subarray `A[l..r]` and add an integer `delta` (which may be negative, zero, or positive) to every element of that subarray. After the operation (or after choosing not to use it), return the **maximum possible frequency** of any single value in the array, together with **one** optimal choice of `(l, r, delta)` that achieves it.\n\nReturn the answer as a list `[max_frequency, l, r, delta]` using 0-based, inclusive indices `l <= r`. If no operation helps, return the no-op choice `[max_frequency, 0, 0, 0]` (applying `delta = 0` changes nothing).\n\n**Example:** For `A = [2, 4, 6, 2, 4, 7]`, selecting the subarray `A[1..1] = [4]` and adding `delta = -2` yields `[2, 2, 6, 2, 4, 7]`, producing three 2s, so the maximum frequency is `3` and one valid answer is `[3, 1, 1, -2]`.\n\n(In the original problem statement, shifting the subarray `[4,6,2,4]` by `delta = -2` is one alternative optimum that also yields three 2s.)
Constraints
- 1 <= n <= 10^4 (n may also be 0; return [0, 0, -1, 0] for an empty array).
- -10^9 <= A[i] <= 10^9.
- delta may be any integer (negative, zero, or positive).
- Indices are 0-based and inclusive: 0 <= l <= r < n.
- If multiple (l, r, delta) achieve the maximum frequency, returning any one is acceptable; the max frequency itself is unique.
Examples
Input: [2, 4, 6, 2, 4, 7]
Expected Output: [3, 1, 1, -2]
Explanation: Shift A[1..1]=[4] by -2 -> [2,2,6,2,4,7], three 2s. Max frequency 3.
Input: [5]
Expected Output: [1, 0, 0, 0]
Explanation: Single element already has frequency 1; no-op is optimal.
Hints
- Fix a target value V you want to appear most often. Outside the shifted window, every V already present still counts; inside the window, you can only turn one source value W into V by choosing delta = V - W (so all W's inside become V, and any V's inside are lost).
- For a fixed (V, W) pair, the net change to the count of V over a window equals (#W in window) - (#V in window). Assign score +1 to positions equal to W, -1 to positions equal to V, 0 otherwise, then take the maximum-sum contiguous subarray (Kadane) to pick the best window.
- The final answer for a pair is totalCount(V) + bestKadaneSum. Iterate over all ordered distinct pairs (V, W), keep the no-op baseline (max raw frequency), and track the (l, r, delta = V - W) that produced the best window.