Iterating Java Arrays in Java 8

Question

So here's a simple algorithmic problem,

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6].

Here's my solution,

public static int[] productExceptSelf(int[] nums) {

    int[] result = new int[nums.length];

    int leftProduct = 1;
    int rightProduct = 1;

    for(int i = 0; i < result.length; i++){
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }

    for(int i=nums.length -1; i >= 0; i --){
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    return result;
}

public static void main(String[] args) {
    int[] output = productExceptSelf(new int[]{1, 2, 3, 4});
    Arrays.stream(output).forEach(System.out::println);
}

This works fine. What I'm trying to learn is how to rewrite this code in Java 8. As in what the different options with the loops in Java 8.

@JoeC I kinda know that, my point is how can I rewrite the code using Java 8 functional constructs. — Melissa Stewart
– Melissa Stewart, Commented Oct 29, 2017 at 17:30
To be totally honest, this particular example is one which I would not attempt to do this. This is largely because you are manipulating multiple variables inside your loop, and the Stream API is not designed very well for this. — Joe C
– Joe C, Commented Oct 29, 2017 at 17:32
Streams are not very suited (as they are now) to let temporary results flow into the further stream IMHO - an unfortunate waste of time for everybody.. Tip: System.out.println(Arrays.toString(output)); is nicer looking. — Joop Eggen
– Joop Eggen, Commented Oct 29, 2017 at 19:48

Eugene · Accepted Answer · 2017-10-29 20:16:07Z

4

You could do it in a few lines of code a bit different:

public static int[] productExceptSelf(int[] nums) {
    int all = Arrays.stream(nums).reduce(1, (x, y) -> x * y);
    return IntStream.range(0, nums.length).map(x -> all / nums[x]).toArray();
}

answered Oct 29, 2017 at 20:16

Eugene

122k17 gold badges219 silver badges335 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Flown Over a year ago

I really like this solution but the requirement was: Solve it without division and in O(n)

Eugene Over a year ago

@Flown I have absolutely done the skim reading over the question and did not even noticed :(

Stuart Marks · Accepted Answer · 2017-10-30 17:02:31Z

Several comments and answers have mentioned that the streams API doesn't lend itself to solving this sort of problem. I agree; it's much easier to work with arrays. Here's how I'd do it:

static int[] productExceptSelf(int[] nums) {
    int len = nums.length;

    int[] lefts = new int[len];
    Arrays.setAll(lefts, i -> i == 0 ? 1 : lefts[i-1] * nums[i-1]);

    int[] rights = new int[len]; // reversed
    Arrays.setAll(rights, i -> i == 0 ? 1 : rights[i-1] * nums[len-i]);

    int[] result = new int[len];
    Arrays.setAll(result, i -> lefts[i] * rights[len-i-1]);

    return result;
}

public static void main(String[] args) {
    int[] nums = { 1, 2, 3, 4 };
    System.out.println(Arrays.toString(productExceptSelf(nums)));
}

This is conceptually quite similar to the iterative approach, but it stores full intermediate results in temporary arrays in order to take advantage of the Arrays.setAll operation. This takes more space, but it does the same number of multiplications.

I note that the specification of Arrays.setAll doesn't guarantee left-to-right opreation, but this approach requires it. In fact, setAll is basically a wrapper for IntStream.range(0, length), so you could easily write this utility yourself if this dependence on setAll is a concern.

Note that this is basically a "prefix" or "scan" operation, as illustrated in Flown's answer. (+1) Unfortunately, the limitations of Arrays.parallelPrefix, such as inability to specify an initial element, and the inability to scan right-to-left (and also the lack of a built-in way to reverse a primitive array) make that approach inconvenient, though sound.

Infamous · Accepted Answer · 2017-10-29 19:52:48Z

2

This does what you ask, but I feel like it needs more elegance :-D

public static void main(String[] args) {
    List<Integer> output = productExceptSelf(new int[]{1, 2, 3, 4});
    output.forEach(System.out::println);
}

public static List<Integer> productExceptSelf(int[] nums) {
    List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
    List<Integer> results = new ArrayList<>();
    list.forEach(value -> {
        int x = 1;
        for (Integer i : list) {
            if (value.equals(i)) continue;
            x *= i;
        }
        results.add(x);
    });
    return results;
}

edited Oct 29, 2017 at 19:52

answered Oct 29, 2017 at 19:12

Infamous

76411 silver badges25 bronze badges

3 Comments

Joop Eggen Over a year ago

The OP had an already very nice solution. This time your solution seems not to do the same, the first element being 24.

Infamous Over a year ago

@JoopEggen care to point out where the error lies? I ran some test cases and they seem to do fine.

Joop Eggen Over a year ago

apologies! The solution itself is fine and to the point, but not O(N), it is O(N²). And I would have wished more stream things. Still I should have said so.

Flown · Accepted Answer · 2017-10-30 08:31:58Z

As already said in the comments: Streams are not well suited for this kind of task, but there are other methods in the JDK, like Arrays::parallelPrefix.

I took your idea and transformed it into:

private static int[] productExceptSelf(int[] arr) {
  IntBinaryOperator product = (a, b) -> a * b;

  int[] leftPrefix = IntStream.concat(IntStream.of(1), IntStream.of(arr)).toArray();
  Arrays.parallelPrefix(leftPrefix, product);

  int[] reversedRightPrefix = reversed(IntStream.concat(IntStream.of(arr), IntStream.of(1))
                                             .toArray());
  Arrays.parallelPrefix(reversedRightPrefix, product);
  //Could be calculated on-the-fly: reversedRightPrefix[reversedRightPrefix - i - 2]
  int[] rightPrefix = reversed(reversedRightPrefix);

  return IntStream.range(0, arr.length)
                 .map(i -> product.applyAsInt(leftPrefix[i], rightPrefix[i + 1]))
                 .toArray();
}

private static int[] reversed(int[] arr) {
  return IntStream.range(0, arr.length).map(i -> arr[arr.length - 1 - i]).toArray();
}

Since you've asked for loop alternatives you can use recursion (still Java 8 code):

private static int[] productExceptSelf(int[] arr) {
  int[] result = new int[arr.length];
  productExceptSelf(arr, result, 0, 1);
  return result;
}

private static int productExceptSelf(int[] arr, int[] result, int i, int leftPrefix) {
  if (arr.length <= i) {
    return 1;
  }
  int rightPrefix = productExceptSelf(arr, result, i + 1, leftPrefix * arr[i]);
  result[i] = leftPrefix * rightPrefix;
  return rightPrefix * arr[i];
}

Collectives™ on Stack Overflow

Iterating Java Arrays in Java 8

4 Answers 4

2 Comments

Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related