624. Maximum Distance in Arrays

Time: O(n)

Space: O(1)

Intuition

Maximize max[i] - min[j] where i≠j. Greedily track running minimum of first elements and maximum of last elements from previous arrays.

Algorithm

1Initialize min_val = first[0], max_val = last[0].
2For each subsequent array i: ans = max(ans, last[i]-min_val, max_val-first[i]).
3Update min_val, max_val with current array.

Common Pitfalls

•Must update answer BEFORE updating min/max to ensure i≠j constraint.

624.cs

// Approach: Single pass — compare each array’s max/min against the running
// global min/max from all previous arrays before updating the trackers.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxDistance(IList<IList<int>> arrays)
    {
        int ans = 0;
        int min = 10000;
        int max = -10000;

        foreach (var array in arrays)
        {
            ans = Math.Max(ans, Math.Max(array[array.Count - 1] - min, max - array[0]));
            min = Math.Min(min, array[0]);
            max = Math.Max(max, array[array.Count - 1]);
        }

        return ans;
    }
}

Was this solution helpful?