12 September 2025

Challenge 338

Vectored Max

• Task 1: Highest Row
• Task 2: Max Distance

Task 1: Highest Row

Submitted by: Mohammad Sajid Anwar

---

You are given a m x n matrix.

Write a script to find the highest row sum in the given matrix.

Example 1

Input: @matrix = ([4,  4, 4, 4],
                  [10, 0, 0, 0],
                  [2,  2, 2, 9])
Output: 16

Row 1: 4  + 4 + 4 + 4 => 16
Row 2: 10 + 0 + 0 + 0 => 10
Row 3: 2  + 2 + 2 + 9 => 15

Example 2

Input: @matrix = ([1, 5],
                  [7, 3],
                  [3, 5])
Output: 10

Example 3

Input: @matrix = ([1, 2, 3],
                  [3, 2, 1])
Output: 6

Example 4

Input: @matrix = ([2, 8, 7],
                  [7, 1, 3],
                  [1, 9, 5])
Output: 17

Example 5

Input: @matrix = ([10, 20,  30],
                  [5,  5,   5],
                  [0,  100, 0],
                  [25, 25,  25])
Output: 100

---

Solution

The task can be translated literally to PDL:

use strict;
use warnings;
use PDL;

sub highest_row {
    max sumover pdl @_;
}

See the full solution to task 1.

Task 2: Max Distance

Submitted by: Mohammad Sajid Anwar

---

You are given two integer arrays, @arr1 and @arr2.

Write a script to find the maximum difference between any pair of values from both arrays.

Example 1

Input: @arr1 = (4, 5, 7)
       @arr2 = (9, 1, 3, 4)
Output: 6

With element $arr1[0] = 4
| 4 - 9 | = 5
| 4 - 1 | = 3
| 4 - 3 | = 1
| 4 - 4 | = 0
max distance = 5

With element $arr1[1] = 5
| 5 - 9 | = 4
| 5 - 1 | = 4
| 5 - 3 | = 2
| 5 - 4 | = 1
max distance = 4

With element $arr1[2] = 7
| 7 - 9 | = 2
| 7 - 1 | = 6
| 7 - 3 | = 4
| 7 - 4 | = 4
max distance = 6

max (5, 6, 6) = 6

Example 2

Input: @arr1 = (2, 3, 5, 4)
       @arr2 = (3, 2, 5, 5, 8, 7)
Output: 6

With element $arr1[0] = 2
| 2 - 3 | = 1
| 2 - 2 | = 0
| 2 - 5 | = 3
| 2 - 5 | = 3
| 2 - 8 | = 6
| 2 - 7 | = 5
max distance = 6

With element $arr1[1] = 3
| 3 - 3 | = 0
| 3 - 2 | = 1
| 3 - 5 | = 2
| 3 - 5 | = 2
| 3 - 8 | = 5
| 3 - 7 | = 4
max distance = 5

With element $arr1[2] = 5
| 5 - 3 | = 2
| 5 - 2 | = 3
| 5 - 5 | = 0
| 5 - 5 | = 0
| 5 - 8 | = 3
| 5 - 7 | = 2
max distance = 3

With element $arr1[3] = 4
| 4 - 3 | = 1
| 4 - 2 | = 2
| 4 - 5 | = 1
| 4 - 5 | = 1
| 4 - 8 | = 4
| 4 - 7 | = 3
max distance = 4

max (5, 6, 3, 4) = 6

Example 3

Input: @arr1 = (2, 1, 11, 3)
       @arr2 = (2, 5, 10, 2)
Output: 9

With element $arr1[0] = 2
| 2 - 2  | = 0
| 2 - 5  | = 3
| 2 - 10 | = 8
| 2 - 2  | = 0
max distance = 8

With element $arr1[1] = 1
| 1 - 2  | = 1
| 1 - 5  | = 4
| 1 - 10 | = 9
| 1 - 2  | = 1
max distance = 9

With element $arr1[2] = 11
| 11 - 2  | = 9
| 11 - 5  | = 6
| 11 - 10 | = 1
| 11 - 2  | = 9
max distance = 9

With element $arr1[3] = 3
| 3 - 2  | = 1
| 3 - 5  | = 2
| 3 - 10 | = 7
| 3 - 2  | = 1
max distance = 7

max (8, 9, 9, 7) = 9

Example 4

Input: @arr1 = (1, 2, 3)
       @arr2 = (3, 2, 1)
Output: 2

With element $arr1[0] = 1
| 1 - 3 | = 2
| 1 - 2 | = 1
| 1 - 1 | = 0
max distance = 2

With element $arr1[1] = 2
| 2 - 3 | = 1
| 2 - 2 | = 0
| 2 - 1 | = 1
max distance = 1

With element $arr1[2] = 3
| 3 - 3 | = 0
| 3 - 2 | = 1
| 3 - 1 | = 2
max distance = 2

max (2, 1, 2) = 2

Example 5

Input: @arr1 = (1, 0, 2, 3)
       @arr2 = (5, 0)
Output: 5

With element $arr1[0] = 1
| 1 - 5 | = 4
| 1 - 0 | = 1
max distance = 4

With element $arr1[1] = 0
| 0 - 5 | = 5
| 0 - 0 | = 0
max distance = 5

With element $arr1[2] = 2
| 2 - 5 | = 3
| 2 - 0 | = 2
max distance = 3

With element $arr1[3] = 3
| 3 - 5 | = 2
| 3 - 0 | = 3
max distance = 3

max (4, 5, 3, 3) = 5

---

Solution

Procedure

A pair (x, y) that provides the maximum distance |x - y| must be in the form x - y, where x is the maximum over one array and y is the minimum over the other. Taking this fact into account, each array can be reduced to its minimum and maximum values.

Find the first and second lowest and highest elements from the minimum and maximum of the arrays. Let these be \(l_1, l_2, h_1 \text{ and } h_2\). From these four values there are three pairs that are candidates for the maximum distance: \(h_1 - l_1\), \(h_1 - l_2\) and \(h_2 - l_1\), where a pair is valid only if the values stem from different arrays. As \(l_1\) and \(l_2\) as well as \(h_1\) and \(h_2\) cannot stem from the same array, there is always at least one valid pair.

Select the largest valid distance as the result.

In the above consideration the number of given arrays is not limited to two, so this approach can be used unmodified on any number of at least two arrays.

With \(n\) as the array size and \(k\) as the number of arrays, the approach has a complexity of \(\mathcal{O}(n k)\), which could be considered as optimal.

Implementation details

• As the arrays may be of different size, some fiddling is required to represent these in a 2-d ndarray. Set undefval to BAD and enable BAD values for the ndarray.

• The position of the minimum in a list can be found as the position of the maximum with changed signs.

• The difference of two numbers can be calculated as a vector product: \(y - x = (x, y) \cdot (-1, 1)\) The difference of all pairs within an n-dimensional structure can be calculated in a single operation with this approach.

Example

Consider example 1 with an additional (irrelevant) array (6, 5) for easier distinction of dimensions.

Create a “change sign” constant vector, a “candidate selector” constant matrix and the input matrix:

pdl> do_print 1
1
pdl> $diff = long -1, 1
[-1 1]

pdl> $sel = indx [0, 1, 0], [0, 0, 1]

[
 [0 1 0]
 [0 0 1]
]

pdl> $PDL::undefval = badvalue long
-2147483648

pdl> $m = long [4, 5, 7], [6, 5], [9, 1, 3, 4]

[
 [          4           5           7 -2147483648]
 [          6           5 -2147483648 -2147483648]
 [          9           1           3           4]
]

pdl> $m->badflag(1)
1
pdl> $m

[
 [  4   5   7 BAD]
 [  6   5 BAD BAD]
 [  9   1   3   4]
]

Create a matrix holding the minimum and maximum of each array:

pdl> $mm = cat +($m->minmaximum)[0, 1]

[
 [4 5 1]
 [7 6 9]
]

Find the indices of the first and second minimum (with changed signs) and maximum :

pdl> $mm2 = maximum_n_ind $mm * $diff(*1), 2

[
 [2 0]
 [2 0]
]

Combine indices with their corresponding values:

pdl> $stack = $mm2->cat($mm->index1d($mm2))

[
 [
  [2 0]
  [2 0]
 ]
 [
  [1 4]
  [9 7]
 ]
]

Select candidate pairs:

pdl> $pairs = $stack->index1d($sel)

[
 [
  [2 0 2]
  [2 2 0]
 ]
 [
  [1 4 1]
  [9 9 7]
 ]
]

Calculate the differences of all pairs:

pdl> $cand = $pairs->xchg(0, 1)->inner($diff)

[
 [ 0  2 -2]
 [ 8  5  6]
]

Select the maximum value-difference corresponding to a non-zero index-difference.

pdl> $cand(,1)->where($cand(,0))->max
6

Implementation

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

sub max_distance {
    state $diff = long -1, 1;
    state $sel = indx [0, 1, 0], [0, 0, 1];
    $PDL::undefval = badvalue long;
    (my $m = long @_)->badflag(1);
    my $mm = cat +($m->minmaximum)[0, 1];
    my $mm2 = maximum_n_ind $mm * $diff(*1), 2;
    my $cand = $mm2->cat($mm->index1d($mm2))
        ->index1d($sel)->xchg(0, 1)->inner($diff);

    $cand(,1)->where($cand(,0))->max;
}

See the full solution to task 2.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.