DEV Community

Cover image for 624. Maximum Distance in Arrays
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

624. Maximum Distance in Arrays

624. Maximum Distance in Arrays

Difficulty: Medium

Topics: Array, Greedy

You are given m arrays, where each array is sorted in ascending order.

You can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a - b|.

Return the maximum distance.

Example 1:

  • Input: arrays = [[1,2,3],[4,5],[1,2,3]]
  • Output: 4
  • Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Example 2:

  • Input: arrays = [[1],[1]]
  • Output: 0

Constraints:

  • m == arrays.length
  • 2 <= m <= 105
  • 1 <= arrays[i].length <= 500
  • -104 <= arrays[i][j] <= 104
  • arrays[i] is sorted in ascending order.
  • There will be at most 105 integers in all the arrays.

Solution:

We need to calculate the maximum possible distance between two integers, each picked from different arrays. The key observation is that the maximum distance will most likely be between the minimum value of one array and the maximum value of another array.

To solve this problem, we can follow these steps:

  1. Track the minimum value and maximum value as you iterate through the arrays.
  2. For each array, compute the potential maximum distance by comparing the current array's minimum with the global maximum and the current array's maximum with the global minimum.
  3. Update the global minimum and maximum as you proceed.

Let's implement this solution in PHP: 624. Maximum Distance in Arrays

<?php
// Example usage:
$arrays1 = [[1,2,3],[4,5],[1,2,3]];
echo maxDistance($arrays1); // Output: 4

$arrays2 = [[1],[1]];
echo maxDistance($arrays2); // Output: 0
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • min_value and max_value are initialized with the first array’s minimum and maximum values.
  • As we iterate through each array starting from the second one:
    • We calculate the distance by comparing the global minimum with the current array’s maximum and the global maximum with the current array’s minimum.
    • Update the max_distance whenever a larger distance is found.
    • Update min_value and max_value to reflect the minimum and maximum values encountered so far.
  • Finally, the function returns the maximum distance found.

This solution runs in O(m) time, where m is the number of arrays, making it efficient given the problem constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Challenge Submission: SpeechCraft - AI-Powered Speech Analysis for Better Communication

SpeechCraft is an advanced real-time speech analytics platform that transforms spoken words into actionable insights. Using cutting-edge AI technology from AssemblyAI, it provides instant transcription while analyzing multiple dimensions of speech performance.

Read full post

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay