Skip to content

624. Maximum Distance in Arrays 👍

Approach 1: Greedy

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int mxDistance(vector<vector<int>>& arrays) {
    int ans = 0;
    int mn = 10000;
    int mx = -10000;

    for (const vector<int>& A : arrays) {
      ans = max({ans, A.back() - mn, mx - A.front()});
      mn = min(mn, A.front());
      mx = max(mx, A.back());
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int maxDistance(List<List<Integer>> arrays) {
    int ans = 0;
    int mn = 10000;
    int mx = -10000;

    for (List<Integer> A : arrays) {
      ans = Math.max(ans, Math.max(A.get(A.size() - 1) - mn, mx - A.get(0)));
      mn = Math.min(mn, A.get(0));
      mx = Math.max(mx, A.get(A.size() - 1));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def maxDistance(self, arrays: list[list[int]]) -> int:
    ans = 0
    mn = 10000
    mx = -10000

    for A in arrays:
      ans = max(ans, A[-1] - mn, mx - A[0])
      mn = min(mn, A[0])
      mx = max(mx, A[-1])

    return ans

Approach 2: Pythonic

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def maxDistance(self, arrays: list[list[int]]) -> int:
    min1, index_min1 = min((A[0], i) for i, A in enumerate(arrays))
    max1, index_max1 = max((A[-1], i) for i, A in enumerate(arrays))
    if index_min1 != index_max1:
      return max1 - min1

    min2, index_min2 = min((A[0], i)
                           for i, A in enumerate(arrays) if i != index_min1)
    max2, index_min2 = max((A[-1], i)
                           for i, A in enumerate(arrays) if i != index_max1)
    return max(max1 - min2, max2 - min1)