Published 2024-08-16

0624. Maximum Distance in Arrays

leetcode

Problem

Given a list of arrays, each individual array is sorted in non-decreasing order. Write a function to find the maximum distance between any pair of elements where the first element is taken from one array, and the second is taken from another array. The distance is defined as the absolute difference between the two elements.

Example input:

  • arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]

Output:

  • The function should return 4 because the maximum distance can be achieved by taking 1 from the first array and 5 from the second array.

Solution Description

To implement the solution, we need to:

  1. Track the minimum and maximum values across the arrays as we iterate through them.
  2. For each array, consider the possible distances with the current global minimum and maximum values found so far.
  3. Update the global minimum and maximum values after considering the current array.
  4. Calculate the distances and track the maximum distance encountered.

The approach ensures that we efficiently find the maximum distance without checking every possible pair of elements, resulting in a time complexity of O(n), where n is the number of arrays. The space complexity is O(1) as we are using a fixed amount of additional space.

Example

Consider the arrays [[1, 2, 3], [4, 5], [1, 2, 3]]:

  1. Initialize globalmin with the last element of the first array (1) and globalmax with the first element of the first array (3).
  2. Iterate through each array:
    • For the second array [4, 5], calculate the distances with globalmin (1) and globalmax (3). Update the maximum distance to 4 (|1-5|).
    • Update globalmin to 1 (unchanged) and globalmax to 5.
    • Process the remaining arrays similarly.

References

No specific algorithms required, but understanding of array processing and iteration is essential.

Solution

// Define logger functions for standalone testing and use in platforms where they are undefined.

/**
 * @param {number[][]} arrays - A list of sorted arrays.
 * @return {number} - The maximum distance between any pair of elements where the elements are from different arrays.
 */
function maximumDistance(arrays) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    let gMin = arrays[0][0];
    let gMax = arrays[0][arrays[0].length - 1];
    let maxD = 0;

    log(`#   Initial gMin='${gMin}', gMax='${gMax}'`);

    for (let i = 1; i < arrays.length; i++) {
        const c = arrays[i];
        const cMin = c[0];
        const cMax = c[c.length - 1];

        log(`#     Array ${i}: cMin='${cMin}', cMax='${cMax}'`);

        const oldMaxD = maxD;

        maxD = Math.max(maxD,
                        Math.abs(gMax - cMin),
                        Math.abs(cMax - gMin));

        log(`#     oldMaxD='${oldMaxD}'; new maxD='${maxD}';`)

        gMin = Math.min(gMin, cMin);
        gMax = Math.max(gMax, cMax);

        log(`#     Updated gMin='${gMin}', gMax='${gMax}'`);
    }

    log(`#  return ${maxD}`);

    return maxD;
}

// Test cases array, structure with input data and expected results.
const testCases = [
    { arrays: [[1, 2, 3], [4, 5], [1, 2, 3]], expected: 4 },
    { arrays: [[1], [1]], expected: 0 },
    { arrays: [[1,4], [0,5], [3,6]], expected: 6 },
    { arrays: [[2, 3, 4], [1, 2, 3, 4, 5, 6], [7, 8]], expected: 7 },
    { arrays: [[0, 10, 20], [3, 9, 30], [11, 14]], expected: 30 },
];

// Execute and display test results
testCases.forEach((test, index) => {
    const result = maximumDistance(test.arrays);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});
© d)zharii. sitemap