Solution to Leetcode 1021: Best Sightseeing Pair

In this Leetcode problem, given an array A, we are asked to return the maximum A[i]+A[j]+i-j with j > i.

In the first approach, I tried all the [i,j], i!= j, with this code:

func maxScoreSightseeingPair(A []int) int {
    res := 0
    for i,v1 := range A {
        val := v1 + i
        for j := i+1; j < len(A); j++ {
            curr := val - j + A[j]
            if curr > res {
                res = curr
            }
        }
    }
    return res
}

However straightforward, I got a time exceeded for the input [1,1,1,…,1] (x50000). Can we do better than O(N²)

What we can notice is that the max value for A is 1000, whereas max length for A is 50000. Using this data, we can transform the code in a O(1000*N) algorithm. Then for A[i], there is really no point checking the indices that are farther than A[i] from i. The second loop becomes for j := i+1; j < len(A) && j < val + 1; j++ ...

This improves the performance to O(max(A) * N), with max(A) ≤ 1000 and N ≤ 50000. Here is the final code:

func maxScoreSightseeingPair(A []int) int {
    res := 0
    for i,v1 := range A {
        val := v1 + i
        for j := i+1; j < len(A) && j < val + 1; j++ {
            curr := val - j + A[j]
            if curr > res {
                res = curr
            }
        }
    }
    return res
}

The performance for tests is the following:

Happy coding :)