Leetcode

Maximum Distance in Arrays

Approach 1: Greedy

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  int maxDistance(vector<vector<int>>& arrays) {
    int ans = 0;
    int min = 10000;
    int max = -10000;

    for (const auto& A : arrays) {
      ans = std::max({ans, A.back() - min, max - A.front()});
      min = std::min(min, A.front());
      max = std::max(max, A.back());
    }

    return ans;
  }
};

JAVA

class Solution {
  public int maxDistance(List<List<Integer>> arrays) {
    int ans = 0;
    int min = 10000;
    int max = -10000;

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

    return ans;
  }
}

Python

class Solution:
  def maxDistance(self, arrays: List[List[int]]) -> int:
    ans = 0
    mini = 10000
    maxi = -10000

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

    return ans

Approach 2: Pythonic

  • Time:O(n)
  • Space:O(1)

C++

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)