Maximum Difference in an Array

You are given an array of integers and must compute the maximum difference between any item and any lower indexed smaller item for the possible pairs, i.e., for a given array a find the maximum value of a[j] – a[i] for all i, j where 0 <= i < j < n and a[i] < a[j]. If no item has smaller item with lower index then return -1.

For example given an array [1, 2, 6, 4]. you will first compare 2 to the elements to its left. 1 is smaller , so calculate the difference 2 – 1 = 1, 6 is bigger than 2 and 1. so calculate the differences 4 and 5, for is only bigger than 2 and 1, and the differences are 2 and 3. The largest difference was 6 – 1 = 5.

Functional Description

Complete the function maxDifference .  The function must return an integer representing the maximum difference in a.

maxDifference  has the following parameter(s): a[a[0],a[1],……a[n-1]]: an array of integers

Constraints 

  • 1 <= n <= 2 x 10^5
  • -10^6 <= a[i] <= 10^ 6

 Solution 

  • One way is to compare every 2 keys and look if this is the maximum difference so far and update max difference. The complexity of this solution will be O(n^2)
  • Another way is to iterate from the beginning and keeping track of maximum difference and minimum value so far if the difference between the current item and the minimum value is more than update maximum. The complexity of this solution will be O(n)

This code was asked in YapStone HackerRank Test. Please comment if you encountered this question somewhere. Mail us Interview questions and Experiences at InterviewInTech@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Bitnami