Maximum Absolute Difference

Problem

You are given an array of N integers, A1, A2, .... AN. 

Return the 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 and i != j. 

Problem Constraints

1 <= N <= 100000

-109 <= A[i] <= 109

Example Input

Input 1:

A = [1, 3, -1]

Input 2: 

A = [3, 2, 5, 1]

Example Output

Output 1:

5

Output 2:

4

Explanation

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.

Question Link

https://www.interviewbit.com/problems/maximum-absolute-difference/

Solution

We have to find the maximum value of the function f(i,j) = |A[i]-A[j]| + |i-j|.

Solution 1: Brute Force

A simple solution is to apply two loops and calculate the maximum of the the function f.

Algorithm:

  • Initialize diff=0, res=0, idxDiff=0.
  • Iterate the array from left to right.
    • Iterate the array from left to right.
      • diff = Math.abs(A.get(i)-A.get(j));
      • idxDiff = Math.abs(i-j);
      • res = Math.max(res, diff+idxDiff);
  • return res;
public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int diff = 0;
        int res=0;
        int idxDiff=0;
        
        for(int i=0;i<A.size()-1;i++){
            for(int j=i+1;j<A.size();j++){
                diff = Math.abs(A.get(i)-A.get(j));
                idxDiff = Math.abs(i-j);
                res = Math.max(res, diff+idxDiff);
            }
        }
        return res;
    }
}

Complexity Analysis:

  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Solution 2: Optimal Solution

In brute force solution, we find each pair and then find the maximum among them. We cannot solve this question using sorting because if we sort then the index of the value also changed which we don't want.

Absolute value function:
The absolute value function can be defined as a piece wise function:

Similarly we try to break our equation:

  1. if  A[i] > A[j] and i>j

    =>  A[i] - A[j] + i - j

    =>  A[i] + i  -  (A[j]+j)

  2. if  A[i] > A[j] and j>i

    =>  A[i] - A[j] + j - i

    =>  A[i] - i - (A[j] - j)

  3. if  A[j] > A[i] and i > j

    => A[j] - A[i] + i - j

    => A[j] - j - (A[i] - i)

  4. if  A[j] > A[i] and j > i

    => A[j] - A[i] + j - i

    => A[j] + j -(A[i] + i)

From the above four equation which we got after removing mod from the equation. we observe a pattern that the equation(1) and equation(4) are same i.e Element of array + index. equation(1) is the reciprocal of the equation(4). the equation(2) and equation(3) are same i.e element of array - index. equation(2) is the reciprocal of the equation(3).

So, we conclude that we have two equations:  

  1. A[i] + i - (A[j] + j)
  2. A[i] - i - (A[j] - j)

Maximum of above two equation will give us the answer.

To find the maximum, we also need to maximize the both equation.

To maximize the equation:

  1. A[i] + i - (A[j] + j)

    we need to maximize the 1st part i.e (A[i] + i) and minimize the 2nd part i.e (A[j] + j).

    we need to find the maximum and minimum value of the (element of array + index) .

  2.  A[i] - i - (A[j] - j)

        we need to maximize the 1st part i.e (A[i] - i) and minimize the 2nd part i.e (A[j] - j).

        we need to find the maximum and minimum value of the (element of array - index).

As we can see, we have two equations A[i] + i and A[i] - i and find the maximum and minimum of these two.

Algorithm:

  • Initialize the max1 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, 
    • max2 = Integer.MIN_VALUE, min2 = Integer.MAX_VALUE, val1 = 0, val2= 0.
  • Iterate from left to right.
    • val1 = A.get(i) + i.
    • max1 = Math.max(max1,val1);
    • min1 = Math.min(min1, val1);
    • val2 = A.get(i) - i.
    • max2 = Math.max(max2, val2);
    • min2 = Math.min(min2, val2);
  • ans1 = max1 - min1.
  • ans2 = max2 - min2.
  • return Math.max(ans1, ans2). 

Here is the solution:

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int max1 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int max2 = Integer.MIN_VALUE;
        int min2 = Integer.MAX_VALUE;
        int val1=0,val2=0;
        for(int i=0;i<A.size();i++){
            val1 = A.get(i)+i;
            max1 = Math.max(max1,val1);
            min1 = Math.min(min1,val1);
            val2 = A.get(i)-i;
            max2 = Math.max(max2,val2);
            min2 = Math.min(min2,val2);
        }
        int ans1 = max1-min1;
        int ans2 = max2-min2;
        return Math.max(ans1,ans2);
    }
}

Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Comments

Post a Comment

Popular posts from this blog

Beggars Outside Temple

Problem There are   N   ( N > 0 ) beggars sitting in a row outside a temple. Each beggar initially has an empty pot. When the devotees come to the temple, they donate some amount of coins to these beggars. Each devotee gives a fixed amount of coin(according to his faith and ability) to some   K   beggars sitting next to each other. Given the amount donated by each devotee to the beggars ranging from   i   to   j   index, where   1   <=   i   <=   j   <=   N , find out the final amount of money in each beggar's pot at the end of the day, provided they don't fill their pots by any other means. Example Input: N = 5, D = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] Return: [10, 55, 45, 25, 25] Explanation: => First devotee donated 10 coins to beggars ranging from 1 to 2. Final amount in each beggars pot after first devotee: [10, 10, 0, 0, 0] => Second devotee donated 20 coins to beggars ranging from 2 to...
Read more

Difference between Static Array and Dynamic Array

Image
  An array is a collection of similar types of data. Each data item present in the array is called the element of the array. The elements of the array share the same variable name but each element has a different index number. Arrays used to organize data and provide operations such as searching and sorting of data. There are two types of arrays: Static Arrays Dynamic Arrays Static Arrays Static Arrays is a collection of similar types of data stored at contiguous memory location. Store multiple item of a same type together. In Java:  char[] arr = new char[size of Array]; To access element: 0 based indexing. arr[0] - 1st element of the array. Size of arr = arr.length; last element of the array = arr[arr.length-1]; Dynamic Arrays: In dynamic array, we store the collection of similar types of element but we cannot define the size of the array. In Java dynamic array is created using ArrayList which is the implementation of List interface. When we declare the ArrayList, it creates ...
Read more

Rain Water Trapped

Problem Given an array arr[]  of N non-negative integers representing height of blocks at index i as A i where the width of each block is 1. Compute how much water can be trapped in between blocks after raining. Problem Constraints 1 <=   |arr|   <= 100000 Example Input Input 1: A = [0, 1, 0, 2] Input 2:  A = [1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Example Output Output 1: 1 Output 2: 6  Question Link https://leetcode.com/problems/trapping-rain-water/ https://practice.geeksforgeeks.org/problems/trapping-rain-water/0   Solution We have to calculate the amount of water to be stored in between the blocks. Solution 1: Brute Force In Brute force approach, We do what it says in the question. For each element in the array, we find the maximum amount of water it can trap. we calculate the minimum of the maximum of left side and right side of the element. Algorithm Initialize res = 0 ; Iterate the array from left to right : Initialize left_max = Integer.MIN_VAL...
Read more