Play with a scan function/method in Java

I wasn't sure what title to chose for this article; I considered: 'wonky implementation of scan' or 'play with minScan'.
Anyway, you are warned, code here is for fun and to throw away.
Don't use that in production!!

I was once inspired by a video comparing solving a given problem in multiple programming languages.
The video compared a typical 'imperative approach' and alternatives in functional and array languages.
Java wasn't one of those languages explored (however the imperative implementation would have been identical in Java).
Nonetheless, in this article we are going to play around implementing a solution in Java.

Problem statement

The problem is the leetcode '2016. Maximum Difference Between Increasing Elements':

Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j]

Solutions were explored in a video from "code_report".

The problem is explained in 'plain English' in the video (feel free to watch it).
There are also examples, on leetcode, to help understanding the statement.

An imperative solution

The video explored first a typical 'imperative' solution.
The implementation would look the same in all 'imperative' languages, however, examples were given in C and Python.
I can read C or Python but I cannot write in these languages.
However, the solution looked like this:

    private int maximumDifference(int[] ints) {
        var result = -1;
        int minSoFar = Integer.MAX_VALUE;

        for (int value : ints) {
            minSoFar = min(value, minSoFar);
            if (value != minSoFar) {
                result = max(result, value - minSoFar);
            }
        }
        return result;
    }

The functional solution

The above mentioned video explores a couple of solutions with functional languages; in particular Haskell and Scala.
In those 2 languages, the solution used the 'scan left' and 'zip' functions.

The solution could be translated: "scan left with the 'min' operation, zip with the 'minus' operation, filter out 0 values, fold left and return -1 as the default value."

We are going to try to do something similar in Java :-).

As far as I'm aware, there are no 'scan left' in Java.
There might be libraries to do it however I don't know any.
Therefore, we are going to implement methods to mimic the Scala solution.
It's going to be longer, in term of lines of code, than the imperative or Scala solutions, but, it's for fun.
We can throw away the code at the end, therefore, let's definitely try to have fun along the way.

A simple Java 'min scan'

For an array of int, a 'min scan' could look like below.
Note, we have a helper function 'addMinToArray', in which we mutate the accumulator.

    private int[] minScan(int[] numbers) {
        return IntStream.range(0, numbers.length)
                .collect(() -> new int[numbers.length],
                        (acc, i) -> addMinToArray(i, acc, numbers),
                        (a, b) -> {
                            throw new UnsupportedOperationException();
                        });

    }

    private int[] addMinToArray(int i, int[] accumulator, int[] numbers) {
        if (i == 0) {
            accumulator[i] = numbers[i];
        } else {
            accumulator[i] = min(accumulator[i-1], numbers[i]);
        }
        return accumulator;
    }

We also need a way to 'zip' the initial array with the one obtained from minScan.
We could use something like this:

    private int[] zipWithMinus(int[] numbers, int[] scanned) {
        return IntStream.range(0, numbers.length)
                .collect(()-> new int[numbers.length],
                        (acc,i)-> zipWithMinus(i, acc, numbers, scanned),
                        (a,b)-> {throw new UnsupportedOperationException();});
    }

    private int[] zipWithMinus(int i, int[] accumulator, int[] numbers, int[] scanned) {
        accumulator[i] = numbers[i] - scanned[i];
        return accumulator;
    }

Note: the minus operation is 'built in' zipWithMinus, we have not separated it out (i.e. we have not used zip(array1, array2, operation)).

And finally, we want the max from the result of the zipped arrays.
We need to filter out 0 values and return -1 if there is no max.

    private int getTheMax(int[] numbers) {
        return IntStream.range(0, numbers.length)
                .filter(i -> numbers[i] != 0)
                .max().orElse(-1);
    }

Putting it all together

The full code is below.
It is in a test class because that allows me to quickly test with the IDE.

import org.junit.jupiter.api.Test;

import java.util.stream.IntStream;

import static java.lang.Math.min;

public class ArrayMinScanTest {

    @Test
    void testMinScanArray() {
        int[] numbers = {1, 5, 0, 2, 3};
        int[] minScanned = minScan(numbers);
        int[] zippedWithMinus = zipWithMinus(numbers, minScanned);
        int theMax = getTheMax(zippedWithMinus);
        assert 0 != theMax;
    }

    private int[] minScan(int[] numbers) {
        return IntStream.range(0, numbers.length)
                .collect(() -> new int[numbers.length],
                        (acc, i) -> addMinToArray(i, acc, numbers),
                        (a, b) -> {
                            throw new UnsupportedOperationException();
                        });

    }

    private int[] addMinToArray(int i, int[] accumulator, int[] numbers) {
        if (i == 0) {
            accumulator[i] = numbers[i];
        } else {
            accumulator[i] = min(accumulator[i-1], numbers[i]);
        }
        return accumulator;
    }

    private int[] zipWithMinus(int[] numbers, int[] scanned) {
        return IntStream.range(0, numbers.length)
                .collect(()-> new int[numbers.length],
                        (acc,i)-> zipWithMinus(i, acc, numbers, scanned),
                        (a,b)-> {throw new UnsupportedOperationException();});
    }

    private int[] zipWithMinus(int i, int[] accumulator, int[] numbers, int[] scanned) {
        accumulator[i] = numbers[i] - scanned[i];
        return accumulator;
    }

    private int getTheMax(int[] numbers) {
        return IntStream.range(0, numbers.length)
                .filter(i -> numbers[i] != 0)
                .max().orElse(-1);
    }
}

There are no checks about parameters passed to methods, for example for null(s) or to assert arrays zipped have the same size.
However, that will do.

Honorable mention

The imperative solution could also used reduce, which makes it look more like a 'scan from the left'.
However, reduce still uses the imperative algorithm.
Below is an attempt; don't mind the fact that I use a stream of Integer and that there is some boxing/unboxing going on.
We also mutate the accumulator (as opposed to creating a new one).

    void imperativeSolution() {
        var input = Stream.of(1, 5, 0, 2, 3);
        int[] minAndMax = {Integer.MAX_VALUE, -1};
        int[] result = input.reduce(minAndMax,
                this::computeNewMinMax,
                (a, b) -> {
                    throw new RuntimeException();
                });

        System.out.println(Arrays.toString(result));
    }

    private int[] computeNewMinMax(int[] accumulator, Integer item) {
        accumulator[0] = min(accumulator[0], item);
        if (item != accumulator[0]) {
            accumulator[1] = max(accumulator[1], item - accumulator[0]);
        }
        return accumulator;
    }

Summary

We explored a way to mimic, in Java, a functional solution to the problem 'Maximum Difference Between Increasing Elements'.
To that effect we've implemented a simple 'minScan', 'zipWithMinus' and 'getTheMax'.
These are minimal (and questionable :-) implementations, operating on arrays.
The full code is longer than an imperative solution.
It's also not quite the same as the solution in a functional language; for example the are no function composition and/or combination.
However the goal was to play around and, I hope, you had fun.