Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Amazon OA for a SWE role, one algorithmic problem about maximizing the minimum value in an array after repeated increment/decrement operations. Pretty clean problem statement but the constraints tripped me up a bit.

Questions Asked (1)

You have an array of positive integers and two values, one for incrementing and one for decrementing (increment is always less than or equal to decrement). You can pick any two distinct indices any number of times, add the increment to one and subtract the decrement from the other. After all operations, every element must remain strictly positive. What is the maximum possible value of the minimum element in the array?

Algorithms & Data Structures

Author's notes

Spent way too long trying to simulate this before realizing it's a binary search on the answer.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and constraints, then derive the feasibility condition for a target minimum value using binary search. For a given target, compute the total increments needed and check if the total decrements available (without violating positivity) can cover it, considering the increment/decrement values.

Pro tip: Mention that the answer is monotonic, so binary search is optimal, and always test edge cases like increment equals decrement or when the array has only two elements.

1. Clarify and restate

Confirm the operation: pick two distinct indices, add increment to one and subtract decrement from the other, ensuring all elements stay strictly positive. Restate the goal: maximize the minimum element after any number of operations.

2. Identify monotonicity

Recognize that if a minimum value X is achievable, any value less than X is also achievable. This monotonic property allows binary search on the answer.

3. Feasibility check for a target

For a target minimum M, compute the total increments needed to raise all elements below M to at least M. Also compute the maximum total decrements that can be applied without making any element non-positive, considering the decrement value.

4. Compare and decide

If the total increments needed is less than or equal to the total decrements available (adjusted by the ratio of increment to decrement), then M is feasible; otherwise, it is not.

5. Binary search and return

Perform binary search over the possible range of minimum values (from 1 to max possible) using the feasibility check, and return the maximum feasible M.

Key Points to Mention

Binary search on the answer due to monotonicity.
Feasibility condition: total increments needed ≤ total decrements available (considering increment and decrement values).
Maintaining strict positivity: each element must remain > 0 after all operations.
Handling edge cases: increment equals decrement, array size 2, large values.
Time complexity: O(n log(max_value)) with O(n) feasibility check.
Space complexity: O(1) extra space.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.