_624. Maximum Distance in Arrays.md

624. Maximum Distance in Arrays

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 16, 2024

Last updated : August 16, 2024

---

Related Topics : Array, Greedy

Acceptance Rate : 45.84 %

---

This version runs with an AC runtime of 99.43% based off of the first run.

The only real limiting factor of the question is that the two values cannot come from the same row. This presents us with 2 cases:

1. The max and min values in the whole matrix aren't from the same row therefore the output is the $max - min$.
2. They ARE from the same row, which means the answer will be one of the following (ensuring that the values don't come from the same row):
   1. Dif of the greatest and 2nd smallest
   2. Dif of the 2nd greatest and the smallest
   3. Dif of the 2nd greatest and the 2nd smallest

This means we simply have to track the 1st and 2nd largest and smallest values, as well as their indicies. Then, we can make a constant time calculation to see which case of the above to follow.

---

Solutions

• m624.py

Python

m624.py

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        min1, min2 = inf, inf
        min1indx, min2indx = -1, -1

        max1, max2 = -inf, -inf
        max1indx, max2indx = -1, -1

        for i, arr in enumerate(arrays) :
            if arr[0] < min1 :
                min1, min2 = arr[0], min1
                min1indx, min2indx = i, min1indx
            elif arr[0] < min2 :
                min2 = arr[0]
                min2indx = i

            if arr[-1] > max1 :
                max1, max2 = arr[-1], max1
                max1indx, max2indx = i, max1indx
            elif arr[-1] > max2 :
                max2 = arr[-1]
                max2indx = i


        # A bit less efficient since I use a list pointer but
        # it simplifies the code a lot and it's a constant cost 
        # since it'll either be the value immediately or it'll be 
        # 1 of 3 possible combinations.
        if min1indx != max1indx :
            return max1 - min1

        outputs = []
        if min1indx != max2indx :
            outputs.append(max2 - min1)
        if min2indx != max1indx :
            outputs.append(max1 - min2)
        if min2indx != max2indx :
            outputs.append(max2 - min2)

        return max(outputs)