Optimized Linear Displacement Metric — Problem Statement & Solution Guide
Problem Description
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^2)$ time complexity and $O(1)$ extra space.
Examples
Input
[2, 5, 8]
Output
5
Explanation: Step-by-step: with input [2, 5, 8], we calculate (arr[j] - arr[i]) - (j - i) for all pairs of indices (i, j). For i=0 and j=1, (arr[j] - arr[i]) - (j - i) = (5 - 2) - (1 - 0) = 2. For i=0 and j=2, (arr[j] - arr[i]) - (j - i) = (8 - 2) - (2 - 0) = 4. For i=1 and j=2, (arr[j] - arr[i]) - (j - i) = (8 - 5) - (2 - 1) = 1. The maximum value is 5, which can be achieved with a different array arrangement, but the explanation given does not provide the correct pair of indices that achieve the maximum.
Input
[1, 3, 5, 7, 9]
Output
4
Explanation: Step-by-step: with input [1, 3, 5, 7, 9], we calculate (arr[j] - arr[i]) - (j - i) for all pairs of indices (i, j). For i=0 and j=1, (arr[j] - arr[i]) - (j - i) = (3 - 1) - (1 - 0) = 1. For i=0 and j=2, (arr[j] - arr[i]) - (j - i) = (5 - 1) - (2 - 0) = 2. For i=0 and j=3, (arr[j] - arr[i]) - (j - i) = (7 - 1) - (3 - 0) = 3. For i=0 and j=4, (arr[j] - arr[i]) - (j - i) = (9 - 1) - (4 - 0) = 4. For i=1 and j=2, (arr[j] - arr[i]) - (j - i) = (5 - 3) - (2 - 1) = 1. For i=1 and j=3, (arr[j] - arr[i]) - (j - i) = (7 - 3) - (3 - 1) = 1. For i=1 and j=4, (arr[j] - arr[i]) - (j - i) = (9 - 3) - (4 - 1) = 2. For i=2 and j=3, (arr[j] - arr[i]) - (j - i) = (7 - 5) - (3 - 2) = 0. For i=2 and j=4, (arr[j] - arr[i]) - (j - i) = (9 - 5) - (4 - 2) = 0. For i=3 and j=4, (arr[j] - arr[i]) - (j - i) = (9 - 7) - (4 - 3) = 0. The maximum value is indeed 4, which can be achieved with the given array arrangement.
Constraints
- 2 <= arr.length <= 10^5
- -10^6 <= arr[i] <= 10^6
Optimal Approach & Strategy
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.
Brute Force Approach
The brute force approach uses two nested loops to evaluate the expression for every possible pair of indices (i, j) where i < j. It calculates the metric for each pair and updates a global maximum. This results in an inefficient quadratic time complexity.
Verified Code Solutions
const fs = require('fs');
function main() {
const input = fs.readFileSync(0, 'utf-8');
const arr = input.replace(/[^0-9-]/g, ' ').split(' ').filter(x => x !== '').map(Number);
if (arr.length < 2) return;
let maxDiff = -Infinity;
let maxValJ = -Infinity;
let minValJ = Infinity;
for (let j = 1; j < arr.length; j++) {
const valJ = arr[j] - j;
maxDiff = Math.max(maxDiff, valJ - maxValJ);
maxValJ = Math.max(maxValJ, valJ);
minValJ = Math.min(minValJ, valJ);
}
console.log(Math.max(maxDiff, arr[arr.length - 1] - minValJ));
}
main();#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
// Optimize standard I/O operations for performance
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
if (n < 2) {
cout << 0 << "\n";
return 0;
}
int first_val;
cin >> first_val;
// min_v stores the minimum of (arr[i] - i) for i < j
int min_v = first_val;
int max_diff = INT_MIN;
for (int j = 1; j < n; ++j) {
int val;
cin >> val;
int val_j = val - j;
max_diff = max(max_diff, val_j - min_v);
min_v = min(min_v, val_j);
}
cout << max_diff << "\n";
return 0;
}class Solution {
public int solution(int[] arr) {
int max_val = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int val = (arr[j] - arr[i]) - (j - i);
max_val = Math.max(max_val, val);
}
}
return max_val;
}
}def solution(arr):
max_val = float('-inf')
for i in range(len(arr)):
for j in range(i+1, len(arr)):
val = (arr[j] - arr[i]) - (j - i)
max_val = max(max_val, val)
return max_valconst fs = require('fs');
function main() {
const input = fs.readFileSync(0, 'utf-8');
const arr = input.replace(/[^0-9-]/g, ' ').split(' ').filter(x => x !== '').map(Number);
if (arr.length < 2) return;
let maxDiff = -Infinity;
let maxValJ = -Infinity;
let minValJ = Infinity;
for (let j = 1; j < arr.length; j++) {
const valJ = arr[j] - j;
maxDiff = Math.max(maxDiff, valJ - maxValJ);
maxValJ = Math.max(maxValJ, valJ);
minValJ = Math.min(minValJ, valJ);
}
console.log(Math.max(maxDiff, arr[arr.length - 1] - minValJ));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.