mediumArraysPattern: Basic Traversal
Maximum Position-Adjusted Gain Solution
Problem Statement
You are given an integer array `nums`. Find the maximum value of the expression: `nums[j] - nums[i] - (j - i)` over all pairs of indices `(i, j)` such that `0 <= i < j < nums.length`.
Examples
Example 1:
Input:nums = [10, 11, 14, 12, 18]
Output:5
Explanation: Choosing i = 3 and j = 4 yields nums[4] - nums[3] - (4 - 3) = 18 - 12 - 1 = 5. No other pair produces a larger result.
Example 2:
Input:nums = [1, 5, 2, 8]
Output:5
Explanation: Choosing i = 2 and j = 3 yields nums[3] - nums[2] - (3 - 2) = 8 - 2 - 1 = 5.
Example 3:
Input:nums = [5, 4, 3, 2, 1]
Output:-2
Explanation: Choosing i = 0 and j = 1 yields nums[1] - nums[0] - (1 - 0) = 4 - 5 - 1 = -2.
Constraints
- 2 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Time: O(N) Space: O(1)
By rewriting the expression as (nums[j] - j) - (nums[i] - i), we can solve it in a single pass. As we iterate through the array with pointer j, we track the minimum value of (nums[i] - i) seen so far (where i < j) and calculate the difference to find the maximum possible gain in O(N) time and O(1) space.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
def max_position_adjusted_gain(nums: List[int]) -> int:
max_gain = -10**18
min_val = nums[0]
for j in range(1, len(nums)):
current_val = nums[j] - j
max_gain = max(max_gain, current_val - min_val)
min_val = min(min_val, current_val)
return max_gain