Maximum Distance in Array

Difficulty Level Easy
Frequently asked in Adobe Amazon Google Oracle
Array HashViews 2498

The problem “Maximum Distance in Array” states that you are given “n” no. of arrays and all the arrays are given in ascending order. Your task is to find the maximum difference/absolute difference of two numbers in an array and we can define the maximum distance between two numbers as abs|a-b|. You can choose two numbers to form different arrays and find the abs|a-b| as the maximum difference.

Example

[  [1,2,3],
[0,2,3],
[1,4,5] ]
5

Explanation

Because the number ‘0’ in the second array and number ‘5’ in the third array gives the maximum absolute difference in the whole array.

Algorithm

  1. Declare a variable output and set it to 0.
  2. Set the value of minimum as varray[0][0].
  3. Set the value of maximum varray’s first row length i.e., maximum=varray[0][0th row length-1].
  4. Find the max value of the difference between the first array’s first element and second array last element and the difference between the first array’s last element and the second array’s first element
  5. So, Find the max value between the value produced from the above line and output and store it to output.
  6. Find the smaller value between varray[i][0] and minimum and set it to the minimum.
  7. Find the bigger value between varray[i][row_size-1] and maximum and set it to the maximum.
  8. Repeat the above process until the end of the array.
  9. Return output.

An explanation for Maximum Distance in Array

Our task is to find the maximum absolute difference between the two numbers in different arrays. We can simply use nested ‘for loop’ and make it easy by finding out the maximum difference of all the numbers.

But instead of using nested loops and traversing all the elements of the array. We can use a simple one for loop and have an efficient solution. Since all the elements are sorted in ascending order in the input array. We just need to find the differences between the last and first elements of different arrays. Because only these two positioned numbers can give the maximum difference. After all, each array is sorted and the first element is always the least or minimum among others. And last element will be the largest number of the array.

So let us here take an example and solve it :

Input: arr[][]={{0,2,4},{2,3},{4,5,6}};

Output=0,maximum =4, minimum=0, i=1

output=std::max(output,

std::max( abs( varray[i][varray[i].size()-1] – minimum ),

abs(maximum-varray[i][0]) ) )

Output is store as 3

maximum remains as it is 4, minimum remains as it is 0,i=2

output=std::max(output,

std::max( abs( varray[i][varray[i].size()-1] – minimum ),

abs(maximum-varray[i][0]) ) )

the differences between the last and first element of different arrays

0 and 6 and out of which 6 is the maximum difference so output will become 6

And return 6.

Maximum Distance in Array

C++ Program for Maximum Distance in Array

#include <iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int getMaxDistance(vector<vector <int>> varray)
{
    int output=0;
    int minimum=varray[0][0];
    int maximum=varray[0][varray[0].size()-1];

    for(int i = 1 ; i < varray.size() ; i++ )
    {
        output=std::max(output, std::max( abs( varray[i][varray[i].size()-1] - minimum ), abs(maximum-varray[i][0]) ) );
        minimum=std::min( minimum, varray[i][0] );
        maximum=std::max( maximum, varray[i][varray[i].size()-1]);
    }
    return output;

}
int main()
{
    vector<vector<int>> vec= {{0,2,4},{2,3,4},{4,5,6}};
    cout<<"Maximum distance is:"<<getMaxDistance(vec);
    return 0;
}

Maximum distance is: 6

Java Program for Maximum Distance in Array

import java.util.*;
import java.io.*;

class maximumDistance
{
    public static int getMaxDistance(int array[][])
    {
        int output=0;
        int minimum=array[0][0];
        int maximum=array[0][array[0].length-1];

        for(int i = 1 ; i < array.length ; i++ )
        {
            output=Math.max(output, Math.max(Math.abs( array[i][array[i].length-1] - minimum ), Math.abs(maximum-array[i][0]) ) );
            minimum=Math.min( minimum, array[i][0] );
            maximum=Math.max( maximum, array[i][array[i].length-1]);
        }
        return output;

    }
    public static void main(String args[])
    {
        int arr[][]= {{0,2,4},{2,3},{4,5,6}};
        System.out.println("Maximum distance is:"+(getMaxDistance(arr)));
    }
}

Maximum distance is: 6

Complexity Analysis

Time Complexity

O(n) where n is the number of elements in the array. Because we were just traversing over the rows of 2D array or matrix. But we never traversed the columns of our input matrix.

Space Complexity

O(1) as we used a constant space. Since we have used only constant number of variables. The approach has constant space complexity.

References

Translate »