LeetCode Entry

1014. Best Sightseeing Pair

27.12.2024 medium 2024 kotlin rust

Max (a[i] + a[j] + i - j), i > j

1014. Best Sightseeing Pair medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/845

Problem TLDR

Max (a[i] + a[j] + i - j), i > j #medium #arithmetics

Intuition

Let’s move the pointers and observe:

    // 0 1 2 3
    // 3 1 2 5
    // j
    //       i    5 - (3 - 0) + 3 = 5 - 3   +  0 + 3
    //            5 - (3 - 1) + 1 = 5 - 3   +  1 + 1
    //            5 - (3 - 2) + 2 = 5 - 3   +  2 + 2

Each time we move i, all possible previous sums are decreased by distance of 1. By writing down a[i] - (i - j) + a[j] in another way: (a[i] - i) + (a[j] + j) we derive the total sum is independent of the distance, always peek the max of a[j] + j from the previous.

Some other things I’ve considered are: sorting, monotonic stack. But didn’t see any good use of them.

Approach

• the first previous value can be 0 instead of values[0]

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun maxScoreSightseeingPair(values: IntArray): Int {
        var p = 0
        return values.withIndex().maxOf { (i, n) ->
            (n - i + p).also { p = max(p, i + n) }
        }
    }

    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
        let mut p = 0;
        values.iter().enumerate().map(|(i, n)| {
            let c = n - i as i32 + p; p = p.max(i as i32 + n); c
        }).max().unwrap()
    }

    int maxScoreSightseeingPair(vector<int>& values) {
        int res = 0;
        for (int i = 0, p = 0; i < values.size(); ++i)
            res = max(res, values[i] - i + p), p = max(p, values[i] + i);
        return res;
    }