How to remove only one max (min) from a list using Java 8 thread API in O (N) time and O (C) complexity

Question

Here is the code to remove only one of the maximum values ​​(in this case, the first, but it does not matter) from the list. This is O(n) in time and O(n) in space (outside of input).

 public List<Integer> removeOneOfTheMax(List<Integer> nums) { int max = Integer.MIN_VALUE; int maxIndex = -1; Iterator<Integer> it = nums.iterator(); for (int i = 0; it.hasNext(); i++) { Integer temp = it.next(); if (max < temp) { maxIndex = i; max = temp; } } nums.remove(maxIndex); return nums; } 

1 .. What would be equivalent to a method using the Java 8 thread API? I would like to save the complexity of time and space, so sorting is not allowed.

2. Actually, if you pass the LinkedList to the code above, the complexity of the space will be O(C) (again, outside the input), but as far as I understand .stream() creates an additional data structure, so the equivalent of the API stream should be at least O(n) in space. Correct me if I am wrong.

Answer 1

A streaming solution might look like this:

 int maxIndex = IntStream.range(1, nums.size()).reduce(0, (i, j) -> { int left = nums.get(i); int right = nums.get(j); return Integer.max(left, right) == left ? i : j; }); nums.remove(maxIndex); 

Under it will be a Spliterator .

The stream operation itself is not going to create additional data structures.