How to find the highest pair from 2 arrays and that isnt above a specified budget-CodePudding

lets say you have two lists of ints: [1, 2, 8] and [3, 6, 7]. If the budget is 6, the int returned has to be 5 (2 3). I am struggling to find a solution faster than n^2. The second part of the question is "how would you change your function if the number of lists is not fixed?" as in, there are multiple lists with the lists being stored in a 2d array. Any guidance or help would be appreciated.

CodePudding user response：

I will provide an answer for the case of 2 sequences. You will need to ask a separate question for the extended case. I am assuming the entries are natural numbers (i.e. no negatives).

Store your values in a NavigableSet. The implementations of this interface (e.g. TreeSet) allow you to efficiently find (for example) the largest value less than an amount.

So if you have each of your 2 sets in a NavigableSet then you could use:

set1.headSet(total).stream()
    .map(v1 -> Optional.ofNullable(set2.floor(total - v1)).map(v2 -> v1   v2)
    .flatMap(Optional::stream)
    .max(Integer::compareTo);

Essentially this streams all elements of the first set that are less than the total and then finds the largest element of the second set that's less than total - element (if any), adds them and finds the largest. it returns an Optional which is empty if there is no such element.

You wouldn't necessarily need the first set to be a NavigableSet - you could use any sorted structure and then use Stream.takeWhile to only look at elements smaller than the target.

This should be O(n * log n) once the sets are constructed. You could perhaps do even better by navigating the second set rather than using floor.

CodePudding user response：

I think my first approach would be to use for statements and add the elements to each of the next array, then take whatever is close to the budget but not exceeding it. I am new to java and I don't get your solution though, so I don't know if this would help.

For the second part of your question, are you referring to the indefinite length of your array? If so, you can use the ArrayList for that.

CodePudding user response：

The best way to approach the problem if there are multiple lists, would be to use a hash table to store the pair or sequence of values that sum to the number you want (the budget).

You would simply print out the hash map key and values (key being an integer, values: a list of integers) that sum to the number.

Time complexity O(N) where N is the size of the largest list, Space Complexity of O(N).