programming challenge - Leetcode #826. Most Profit Assigning Work solution in Java (Sort + Binary Search) - Code Review Stack Exchange

programming challenge - Leetcode #826. Most Profit Assigning Work solution in Java (Sort + Binary Search) - Code Review Stack Exchange

The algorithm is correct, but an optimization is possible. When the input contains multiple jobs with the same difficulty, then you can reduce the search space, because at any difficulty level, you're only interested in the most profitable job. The time complexity would become $O(n \log n + w \log n')$, where $n'$ is the number of unique difficulties.

Extract special treatment out of the loop

The loop in updateDifficultyAndMaxProfits has a special treatment for index 0. Instead of evaluating a condition for each iteration of the loop, since the input is guaranteed to have at least 1 element, you could perform the special treatment before the loop begins, and make the loop start from index 1, and no conditional.

Avoid modifying the input

You pass to the method updateDifficultyAndMaxProfits the difficulties array that was an input, and overwrite its content. Although this saved you some space in memory, it may not be acceptable, and not a good practice. It would have been better to pass to the function a new array.

However, with the first tip at the top of this review, this point will no longer matter, because you will need a different approach to store the (difficulty, maxProfit) pairs that avoids redundant difficulty values, and you won't know in advance the number of pairs you will need. You may for example implement a computeDifficultyAndMaxProfits, returning a list of pairs.

How about some streams and lambdas

Some elements of your program can be written more compactly with streams and lambdas, for example:

Job[] jobs = IntStream.range(0, profit.length)      .mapToObj(i -> new Job(difficulty[i], profit[i]))      .sorted(Comparator.comparingInt(job -> job.difficulty))      .toArray(Job[]::new);

Since Job implements Comparable, the custom comparator is not necessary here. Keeping the sorting logic outside the class like this is often more practical. It's also compact to write. If you needed to sort multiple times, you could store the lambda in a variable to avoid duplicating logic.

Read full article from programming challenge - Leetcode #826. Most Profit Assigning Work solution in Java (Sort + Binary Search) - Code Review Stack Exchange