Maximum absolute difference in an array

Question

I came across this algorithm question. I was able to implement a O(n^2) solution. Is there a better way of doing this in O(n) time?

Question:

You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N. f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Example:

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

So, we return 5.

My Answer:

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int maxSum = 0;

        for(int i=1; i<=A.size()-1; i++){
            for(int j=i+1; j<=A.size(); j++){
                int tempSum = sum(A.get(i-1), A.get(j-1), i, j);

                if(tempSum > maxSum) {
                    maxSum = tempSum;
                }
            }
        }

        return maxSum;
    }

    public int sum(int Ai, int Aj, int i, int j) {
        return Math.abs(Ai-Aj) + Math.abs(i-j);
    }
}

Also in my solution the inner loop runs from i + 1 to N, so the worst case is N-1 for that loop. Is my overall solution still O(n^2)?

Answer 1

This's also fine, to reduce extra lines of last step:

      int n=A.size(),max1=INT_MIN,max2=INT_MIN,min1=INT_MAX,min2=INT_MAX,ans=INT_MIN;
  for(int i=0;i<n;i++){
        max1=max(max1, A[i]+i);
        min1=min(min1, A[i]+i);
        max2=max(max2, -A[i]+i);
        min2=min(min2, -A[i]+i);
  }
  ans = max((max1-min1), (max2 - min2));
return ans;

Answer 2

conceptually speaking i can think of a very simple solution:

Here we are given that we need to maximize the |A[i] - A[j]| + |i - j| What does this mean ? => if you think of the numbers on a number line along the x-axis it will help with visualization.

Lets think of the second part: |i-j| => if you think about this - it represent distance between any two points. the distance will always be fixed too.

Now if we can think of a way to add this distance to our array such that the it increases the distance A[i] - A[j] by a fixed amount - half of our problem is solved.

Here comes three things in consideration:

1. What if both are positive
2. What if both are negative
3. What if one is positive and one is negative

Remember you gotta increase the distance between A[i] and A[j] by fixed amount. for 1 and 3 if you shift both the numbers in positive direction by the amount of their indices i.e. i and j. your problem is solved.

for 2 you gotta shift the number towards more negative.

now all we need is find difference of min and max separately for both the arrays, one with larger absolute value will be the answer.

Answer 3

O(N) Time Complexity and O(1) Space complexity solution

This question can be solved in O(N) Time and O(1) space complexity by using simple mathematics concepts of absolute operator.

We can deduce this express into 4 different forms after removing the absolute operator and applying specific conditions.

Cases can be A[i]>A[j] or A[i]<=A[j] and simultaneously i>j and i<=j can be the cases so using these conditions we can formulate 4 different expressions which eliminate use of absolute operator.

After that we just need to find the maximum value possible through each expression by iterating on array of numbers only once.

If you still face any difficulties while solving this question then you can refer to the video solution

Video Link:- https://youtu.be/Ov4weYCIipg

Answer 4

I am not sure if we require 4 cases. If we open the mod, there are 4 cases:

 a) (A[j]-j)-(A[i]-i)
 b) (A[j]+j)-(A[i]+i)
 c) (A[i]+i)-(A[j]+j)
 d) (A[i]-i)-(A[j]-j)

But (a) and (d) are same. So are (b) and (c). Hence the problem melts to 2 cases.

int max1 = INT_MIN , max2 = INT_MIN , min1 = INT_MAX , min2 = INT_MAX;

for(int i = 0; i < A.size(); i++)
{
    max1 = max(max1 , A[i] + i);
    min1 = min(min1 , A[i] + i);
    max2 = max(max2 , A[i] - i);
    min2 = min(min2 , A[i] - i);
}

return max(max1 - min1 , max2 - min2);

Answer 5

We can surely use some math here. Try to Expand the Function you are trying to maximise. F(i,j) = |A[i] - A[j]| + |i - j| Expanding it will give us 4 values of F.

 1. A[i] - A[j] + i - j   equals to [A[i] + i] - [A[j]+j]
 2. -A[i] + A[j] + i - j  equals to [-A[i] + i] - [-A[j]+j]
 3. A[i] - A[j] + j - i   equals to [A[i] - i] - [A[j]-j]
 4. -A[i] + A[j] + j - i  equals to [-A[i] - i] - [-A[j]-j]

Compute the Maximum and Minimum Value of [A[i] + i],[-A[i] + i],[A[i] - i],[-A[i] - i] for all elements in vector/array. call it max1,max2,max3,max4 and min1,min2,min3,min4.

Your Answer is Max((max1-min1),(max2-min2),(max3-min3),(max4-min4)).

Here is the Problem Link if anyone is interested :- Problem Link

Below is my implementation in c++

int Solution::maxArr(vector<int> &A) {
int max1 = INT_MIN,max2 = INT_MIN,max3 = INT_MIN,max4 = INT_MIN,ans = INT_MIN;
int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX,min4 = INT_MAX;
for(int i=0;i<A.size();i++){
    max1 = max(max1,A[i] + i);
    max2 = max(max2,A[i] - i);
    max3 = max(max3,-A[i]+i);
    max4 = max(max4,-A[i]-i);

    min1 = min(min1,A[i] + i);
    min2 = min(min2,A[i] - i);
    min3 = min(min3,-A[i]+i);
    min4 = min(min4,-A[i]-i);

}


    ans = max(ans,max1 - min1);
    ans = max(ans,max2 - min2);
    ans = max(ans,max3 - min3);
    ans = max(ans,max4 - min4);

return ans;

}

Answer 6

Implementation reference

int Solution::maxArr(vector<int> &A) {
    int max1 , max2 , min1 , min2;
    max1 = max2 = INT_MIN;
    min1 = min2 = INT_MAX;
    int N = A.size();
    for(int i=0;i<N;i++){
        max1 = max(max1,A[i]+i);
        max2 = max(max2,A[i]-i);
        min1 = min(min1,A[i]+i);
        min2 = min(min2,A[i]-i);
    }
    int ans = 0;
    ans = max(ans,max1-min1);
    ans = max(ans,max2-min2);
    return ans;
}

Answer 7

f(i, j) = |A[i] - A[j]| + |i - j| can be simplified in the following ways (based on definition of abs() ):

a) (A[j]-j)-(A[i]-i)
b) (A[j]+j)-(A[i]+i)
c) (A[i]+i)-(A[j]+j)
d) (A[i]-i)-(A[j]-j)

for 0< i,j < N - a & d are similar, as well as b & c. So if we can calculate an array of A[i]-i and A[i]+i and find max difference within it, we will have the answer.

  public class Solution {
        public int maxArr(ArrayList<Integer> A) {
            int n = A.size();
            int max = 0;
            int []a = new int [n];
            int []b = new int [n];
            for(int i=0;i<n;i++){
                a[i]=A.get(i)-i;
                b[i]=A.get(i)+i;
            }
            Arrays.sort(a);
            Arrays.sort(b);
            max = Math.max(a[n-1]-a[0], b[n-1]-b[0]);
            return max;
        }
    }

Answer 8

As described by Kraskevich, I applied the same algorithm. The complexity of the code is O(4*n)+O(4*n), thus making the overall complexity O(n).

Here is the code.

int Solution::maxArr(vector<int> &A) {
int n=A.size(),max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,max4=INT_MIN,ans=INT_MIN;
for(int i=0;i<n;i++){
    max1=max(max1,A[i]+i);
    max2=max(max2,-A[i]+i);
    max3=max(max3,A[i]-i);
    max4=max(max4,-A[i]-i);
}
for(int i=0;i<n;i++){
    ans=max(ans,max1-A[i]-i);
    ans=max(ans,max2+A[i]-i);
    ans=max(ans,max3-A[i]+i);
    ans=max(ans,max4+A[i]+i);
}
return ans;
}

Answer 9

This is the java solution to your problem.

public class Solution {
public int maxArr(ArrayList<Integer> A) {
    if(A.size() < 2) return 0;
    int res =Integer.MIN_VALUE;
    int max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,min1 = Integer.MAX_VALUE,min2=Integer.MAX_VALUE;
    for(int i =0; i < A.size(); ++i){
        max1 = Math.max(A.get(i) + i, max1);
        min1 = Math.min(A.get(i) + i, min1);

        max2 = Math.max(A.get(i) - i, max2);
        min2 = Math.min(A.get(i) - i, min2);
    }

    res = Math.max(max1-min1, res);
    res = Math.max(max2-min2, res);
    return res;
  }                    
}

Answer 10

public int maxArr(ArrayList<Integer> A) 
{    
  int n=A.size(),max1=A.get(0),max2=A.get(0),int min1=A.get(0),min2=A.get(0),ans=0;

  for(int i=0;i<n; i++){
    max1=max(max1, A.get(i)+i);
    max2=max(max2, A.get(i)-i);
    min1=min(min1,  A.get(i)+i);
    min2=min(min2, A.get(i)-i);
  }

   ans = max(ans, (max2 - min2));
   ans = max(ans, (max1 - min1));

   return ans;
}

Here

int max1 = INT_MIN, max2 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;

Answer 11

Yes, your solution is still O(N^2) as (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

I'll show how to solve a more general problem in linear time: give a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).

1. Let's find the following points: max(x[i] + y[i]), max(-x[i] + y[i]), max(-y[i] + x[i]) and max(-x[i] - y[i]) among all i.

2. Let's compute the distance between every point in the list and the four points chosen during the previous step and pick the largest one. This algorithm clearly works in linear time as it considers 4 * N pairs of points. I claim that it's correct.

3. Why? Let's fix a point (x[k], y[k]) and try to find the farthest one from it. Consider an arbitrary point (x[i], y[i]). Let's expand the absolute value of differences between their coordinates. Let's assume that it's x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]. The first term is a constant. If x[i] + y[i] is not maximum among all i, (x[i], y[i]) cannot be the farthest. The three other cases (depending on the sign of x[i] and y[i] in the expansion) are handled in the same manner.