Maximum difference in an Array not passing all test cases in HackerRank

Question

I applied for a job, and the prospective employer sent me the following HackerRank problem, which cannot be found in the public area.

Give an array of integers, compute the maximum difference between any item and any lower indexed smaller item for all possible pairs. In other words, for the array arr, find the maximum value of arr[j] - arr[i] for all i, j where 0 <= i < j < n and arr[i] < arr[j]. If no item has a smaller item with a lower index, then return -1.

For example, given arr = [1,2,6,4], 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 difference 6 - 2 = 4 and 6 - 1 = 5. The last element, 4, is only bigger than 2 and 1, and the difference are 4 - 2 = 2 and 4 - 1 = 3. The largest difference is 6 - 1 = 5.

Function Description

Complete the function maxDifference. The function must return an integer that represents the maximum difference in arr.

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

Constraints

• 1 <= n <= 2*10^5
• -10^6 <= arr[i] <= 10^6 where [0, n-1]

Solution

fun maxDifference(arr: Array<Int>): Int {

    var min: Pair<Int, Int> = Pair(0, 0)
    var max: Pair<Int, Int> = Pair(0, 0)
    var result = -1

    for(i in 0 until arr.size) {
        when {
            i == 0 -> {
                min = Pair(i, arr[i])
                max = Pair(i, arr[i])
            }
            min.second > arr[i] -> min = Pair(i, arr[i])
            max.second < arr[i] -> max = Pair(i, arr[i])
        }

        if(max.first > min.first && max.second > min.second)
            result = kotlin.math.max(result, max.second - min.second)
    }

    return result
}

The problem

For some reason solution above not passing all test cases in the HackerRank. Unfortunately employer who sent this test not willing to disclose test cases to see where is the issue. The code itself works correct.

Test cases

1. [2,3,10,2,4,8,1] - (expected result is 8)
2. [7,9,5,6,3,2] - (expected result is 2)
3. [3] - (expected result is -1)
4. [-3, -2] - (expected result is 1)

Solution 1

As already mentioned in this answer by @Tom about failing tests, I feel your solution is rather complicated since you try to maintain a pair. I have simplified this as below(Not a kotlin dev, so below is in Javascript):

var arr = [1, 2, 6, 4];

var min = arr[0];
var diff = -1;

for (var i = 1; i < arr.length; ++i) {
  if (arr[i] > min) diff = Math.max(arr[i] - min, diff);
  min = Math.min(min, arr[i]);
}

console.log(diff);

• Well, the conditions say that 0 <= i < j < n and arr[i] < arr[j]. This calls for a greedy approach which points us towards the fact that we just need to maintain the min value when we move from left to right in the array.

• Just maintaining the min value takes us in the correct path because there would be several arr[i] less than the current arr[j], but taking the minimum among all previous i for the current arr[j] will obviously give us the maximum difference.

Solution 2

Your init is wrong - you should hardcode min/max to ±10⁶
Also isn't min/max useless ? Should not you work with min/max of difference ?
Example here should be 4 - 3 = 1, but not found (suppose your code work exactly same as this):

function maxDifference(arr) {
    var min = [0,0];
    var max = [0,0];
    var result = -1

    for(var i in arr) {
        if(i == 0) {
            min = [i, arr[i]];
            max = [i, arr[i]];
        }
        if(min[1] > arr[i]) min = [i, arr[i]];
        if(max[1] < arr[i]) max = [i, arr[i]];

        if(max[0] > min[0] && max[1] > min[1])
            result = Math.max(result, max[1] - min[1])
    }

    return result
}
var a = prompt("Enter data:","9,7,5,6,3,4");
console.log("Array:",a);
console.log(maxDifference(a.split(',')));

Comments

[Tom]

Also 7,9,5,6,3,9 returns 2, but should not be 6 ?

[nice_dev]

Why does 9,7,5,6,3,4 return -1 in your case? Shouldn't it be 1?

[Tom]

It is just translation - not any fix - meant to test/find possibly failed TCs.

[nice_dev]

Ohh, I get it now.

[Arsenius]

Thanks for the better solution! I got where is my bug. Here is updated code gist.github.com/atonamy/a3800fdf89e06bf726b1a16f1a6a5601 But yours one is more elegant and clean.