mediumArraysPattern: Basic Traversal
Optimized Linear Displacement Metric Solution
Problem Statement
You are given an integer array `arr`. Your task is to find the maximum value of the expression `(arr[j] - arr[i]) - (j - i)` over all pairs of indices `(i, j)` such that `0 <= i < j < arr.length`. Optimize your solution to run in a single pass with $O(N)$ time complexity and $O(1)$ extra space.
Examples
Example 1:
Input:arr = [10, 2, 6, 8]
Output:undefined
Explanation: Choosing i = 1 and j = 3 gives the expression value (8 - 2) - (3 - 1) = 6 - 2 = 4, which is the maximum possible.
Example 2:
Input:arr = [1, 5, 2]
Output:undefined
Explanation: Choosing i = 0 and j = 1 gives (5 - 1) - (1 - 0) = 4 - 1 = 3.
Constraints
- 2 <= arr.length <= 10^5
- -10^6 <= arr[i] <= 10^6
Time: O(N) Space: O(1)
By algebraically rearranging the expression to (arr[j] - j) - (arr[i] - i), we can decouple the variables. We iterate through the array once while maintaining the minimum value of (arr[i] - i) seen so far to compute the maximum difference 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
import sys
import re
def solve():
input_data = sys.stdin.read()
arr = [int(x) for x in re.sub(r'[^0-9-]', ' ', input_data).split()]
if len(arr) < 2:
return
min_val = arr[0]
max_diff = -float('inf')
for j in range(1, len(arr)):
val_j = arr[j] - j
max_diff = max(max_diff, val_j - min_val)
min_val = min(min_val, val_j)
print(max_diff)
if __name__ == '__main__':
solve()