How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: []

Expected Output: [0, 0, -1, 0]

Explanation: Empty array: max frequency 0, sentinel no-op window (l=0, r=-1).

Input: [3, 3, 3]

Expected Output: [3, 0, 0, 0]

Explanation: All equal already; no-op gives frequency 3.

Input: [1, 2, 3, 4, 5]

Expected Output: [2, 1, 1, -1]

Explanation: Shift A[1..1]=[2] by -1 -> [1,1,3,4,5], two 1s. No operation can exceed 2 since at most two equal values can be aligned at once here.

Input: [-1, -1, 2, -1]

Expected Output: [4, 2, 2, -3]

Explanation: Shift A[2..2]=[2] by -3 -> [-1,-1,-1,-1], four -1s (negative delta and negatives handled).

Input: [0, 0, 0, 0]

Expected Output: [4, 0, 0, 0]

Explanation: Already all zeros; no-op gives frequency 4.

Input: [10, 20, 10, 30, 10, 20]

Expected Output: [4, 1, 1, -10]

Explanation: Three 10s already; shift A[1..1]=[20] by -10 -> a fourth 10. Max frequency 4.

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.

Quick Overview

This question evaluates a candidate's understanding of array manipulation, frequency analysis, range-update reasoning, and optimization under a single contiguous subarray operation.