LeetCode Problem 3745

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting, Enumeration

Solution

LeetCode 3745 - Maximize Expression of Three Elements

Problem Understanding

The problem gives us an integer array nums and asks us to choose three elements a, b, and c from distinct indices such that the expression:

$$a + b - c$$

is as large as possible.

The important detail is that the three elements must come from different positions in the array. Even if two elements have the same value, they can still be chosen as long as their indices are different.

The input is a single integer array. The output is one integer, representing the maximum possible value of the expression after selecting three valid elements.

The constraints are quite small:

• 3 <= nums.length <= 100
• -100 <= nums[i] <= 100

Since the array contains at most 100 elements, even cubic solutions are technically feasible. However, there is a much simpler observation that allows us to solve the problem more efficiently.

Some important edge cases include arrays containing all negative values, arrays with duplicate values, and arrays where the smallest value appears multiple times. The problem guarantees that there are at least three elements, so a valid selection always exists.

Approaches

Brute Force

The most direct solution is to try every possible choice of three distinct indices.

For every triple (i, j, k) where all indices are different, compute:

$$nums[i] + nums[j] - nums[k]$$

and keep track of the maximum value encountered.

This approach is correct because it explicitly examines every valid selection of three elements. Since the optimal answer must correspond to one of these triples, the maximum value found is guaranteed to be correct.

However, the time complexity is O(n³) because we must iterate through all triples of indices.

Key Insight

The expression is:

$$a + b - c$$

To maximize it:

• We want a as large as possible.
• We want b as large as possible.
• We want c as small as possible because subtracting a smaller number increases the result.

Therefore, the optimal choice is simply:

• The two largest values in the array.
• The smallest value in the array.

The only remaining concern is whether the indices are distinct.

Since the array contains at least three elements, the smallest element and the two largest elements can always be chosen from three positions. If duplicate values exist, they occupy different indices, which still satisfies the requirement.

Thus, if we sort the array:

• Smallest value = nums[0]
• Largest value = nums[n-1]
• Second largest value = nums[n-2]

The answer becomes:

$$nums[n-1] + nums[n-2] - nums[0]$$

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Tries every valid triple of indices
Optimal	O(n log n)	O(1) or O(n) depending on sorting implementation	Sort and use smallest plus two largest values

Algorithm Walkthrough

Optimal Algorithm

1. Sort the array in nondecreasing order.
2. After sorting, identify the smallest element as nums[0].
3. Identify the largest element as nums[n - 1].
4. Identify the second largest element as nums[n - 2].
5. Compute:

nums[n - 1] + nums[n - 2] - nums[0] 6. Return the computed value.

Why it works

The expression depends only on three selected values:

$$a + b - c$$

Increasing either a or b always increases the expression. Decreasing c also increases the expression because it is being subtracted. Therefore, any optimal solution must use the two largest values available for a and b, and the smallest value available for c. Sorting makes these values immediately accessible, guaranteeing the maximum possible result.

Python Solution

from typing import List

class Solution:
    def maximizeExpressionOfThree(self, nums: List[int]) -> int:
        nums.sort()
        return nums[-1] + nums[-2] - nums[0]

The implementation begins by sorting the array.

Once sorted, the smallest element is located at index 0, while the two largest elements are located at indices -1 and -2.

The expression is then evaluated directly using those three values and returned immediately. No additional data structures or complicated logic are required.

Go Solution

import "sort"

func maximizeExpressionOfThree(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	return nums[n-1] + nums[n-2] - nums[0]
}

The Go solution follows exactly the same logic as the Python version.

The slice is sorted using sort.Ints. After sorting, the smallest value is at index 0, and the two largest values are at indices n-1 and n-2. The expression is computed directly and returned.

Since the constraints are very small and the values are between -100 and 100, integer overflow is not a concern.

Worked Examples

Example 1

Input:

nums = [1, 4, 2, 5]

After sorting:

[1, 2, 4, 5]

Variable	Value
Smallest	1
Second Largest	4
Largest	5

Compute:

Expression	Value
5 + 4 - 1	8

Result:

8

Example 2

Input:

nums = [-2, 0, 5, -2, 4]

After sorting:

[-2, -2, 0, 4, 5]

Variable	Value
Smallest	-2
Second Largest	4
Largest	5

Compute:

Expression	Value
5 + 4 - (-2)	11

Result:

11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Dominated by sorting the array
Space	O(1) or O(n)	Depends on the sorting implementation used by the language runtime

The only significant operation is sorting. After sorting, accessing the smallest and two largest values takes constant time. No auxiliary data structures proportional to the input size are required by the algorithm itself.

Test Cases

sol = Solution()

assert sol.maximizeExpressionOfThree([1, 4, 2, 5]) == 8          # example 1
assert sol.maximizeExpressionOfThree([-2, 0, 5, -2, 4]) == 11    # example 2

assert sol.maximizeExpressionOfThree([1, 2, 3]) == 4             # minimum valid length
assert sol.maximizeExpressionOfThree([-5, -4, -3]) == -2         # all negative values
assert sol.maximizeExpressionOfThree([0, 0, 0]) == 0             # all zeros

assert sol.maximizeExpressionOfThree([5, 5, 5, 5]) == 5          # all equal values
assert sol.maximizeExpressionOfThree([-100, 100, 100]) == 300    # extreme values

assert sol.maximizeExpressionOfThree([2, 2, 1]) == 3             # duplicate maximum values
assert sol.maximizeExpressionOfThree([10, -5, -5, 8]) == 23      # duplicate minimum values

assert sol.maximizeExpressionOfThree([-10, 7, 8, 9, -2]) == 27   # mixed positive and negative
assert sol.maximizeExpressionOfThree([100, -100, 99, -99]) == 299 # larger spread

Test Summary

Test	Why
[1,4,2,5]	Official example
[-2,0,5,-2,4]	Official example with negatives
[1,2,3]	Minimum array size
[-5,-4,-3]	All values negative
[0,0,0]	All values identical and zero
[5,5,5,5]	Duplicate values everywhere
[-100,100,100]	Constraint extremes
[2,2,1]	Repeated maximum value
[10,-5,-5,8]	Repeated minimum value
[-10,7,8,9,-2]	General mixed case
[100,-100,99,-99]	Large positive and negative spread

Edge Cases

Array of Exactly Three Elements

When the array length is exactly three, every element must be used. A common source of bugs is accidentally assuming additional choices exist. After sorting, the formula still works correctly because the smallest and the two largest elements are precisely the three available values.

All Negative Numbers

With all negative values, it may seem tempting to think the answer should also be very negative. However, maximizing the expression still means choosing the two largest values, which are the least negative numbers, and subtracting the most negative number. The sorting approach naturally handles this situation.

For example:

[-5, -4, -3]

becomes:

-3 + -4 - (-5) = -2

which is optimal.

Duplicate Values

Arrays may contain repeated values. The problem requires distinct indices, not distinct values. If the two largest values are equal, we can simply choose their different positions in the array. Sorting preserves all occurrences, so selecting nums[n-1] and nums[n-2] remains valid.

Multiple Occurrences of the Minimum Value

The minimum value may appear several times. Since only one occurrence is needed for c, any of those positions can be chosen. The formula uses the minimum value itself, and duplicate occurrences do not affect correctness.

All Elements Equal

If every element has the same value x, then:

$$x + x - x = x$$

The algorithm returns exactly that value because the smallest and largest elements are identical. This confirms that the approach handles completely uniform arrays correctly.