Maximum Distance in Arrays

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given arrays, a list of m non-empty integer arrays, each sorted in ascending order. Choose two numbers that come from **two different arrays** (different positions in arrays, even if their contents happen to be equal). Their distance is the absolute value of their difference. Return the largest distance you can get. Aim for O(m) time.

Examples

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4
Take `1` from the first array and `5` from the second.
Input: arrays = [[1],[1]]
Output: 0
The only possible pair is `1` and `1`.
Input: arrays = [[1,5],[3,4]]
Output: 3
`1` and `5` are in the same array, so the best cross-array pair is `1` and `4`.

Constraints

  • `2 <= arrays.length <= 10^5`
  • `1 <= arrays[i].length <= 500`
  • `-10^4 <= arrays[i][j] <= 10^4`
  • Each `arrays[i]` is sorted in ascending order
  • The total number of integers is at most `10^5`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems