Maximize Expression of Three Elements solution and explanation
7 more videos on this problem
Leetcode Weekly Contest 476 Q1. Maximize Expression of Three Elements #python #dsaADevOpsEngineer · 1:24 · 208 views
3745. Maximize Expression of Three Elements (Leetcode Easy)Programming Live with Larry · 2:00 · 155 views
Maximize expression of three elements | Leetcode 3745 | Leetcode Weekly contest 476 | Problem no 1Prince Gupta Study · 10:01 · 48 views
Maximize Expression of Three Elements | LeetCode 3745 | SortingcodeTips · 2:10 · 32 views
LeetCode 3745 | Maximize Expression of Three Elements – EasyCode Kage · 2:32 · 32 views
Maximize Expression of Three Elements | Leetcode 3745 | Mayank PandeyMayank Pandey · 3:45 · 28 views
Maximize Expression of Three ElementsOwen Wu · 1:30 · 10 views
Leetcode 3745 Maximize Expression of Three ElementsLuc Taylor · 1:07 · 9 views
The problem
You are given an integer array nums.
Choose three elements a, b, and c from nums at distinct indices such that the value of the expression a + b - c is maximized.
Return an integer denoting the maximum possible value of this expression.
Example 1:
Input: nums = [1,4,2,5]
Output: 8
Explanation:
We can choose a = 4, b = 5, and c = 1. The expression value is 4 + 5 - 1 = 8, which is the maximum possible.
Example 2:
Input: nums = [-2,0,5,-2,4]
Output: 11
Explanation:
We can choose a = 5, b = 4, and c = -2. The expression value is 5 + 4 - (-2) = 11, which is the maximum possible.
Constraints:
3 <= nums.length <= 100-100 <= nums[i] <= 100
Approach overview
Problem Overview: You are given an array and need to maximize the value of an expression formed using three different elements. The indices must be distinct, and the goal is to choose the combination of numbers that produces the largest possible value.
Approach 1: Enumeration (Brute Force) (Time: O(n^3), Space: O(1))
The most direct strategy checks every valid triplet of indices (i, j, k). Iterate through the array with three nested loops and compute the expression for each combination. Track the maximum value seen so far. This approach guarantees correctness because it evaluates all possibilities, but it quickly becomes impractical for large arrays due to cubic time complexity. It’s useful as a baseline when first reasoning about the problem.
Approach 2: Sorting the Array (Time: O(n log n), Space: O(1) or O(n) depending on implementation)
Sorting the array helps reveal which values contribute most to the expression. Since the maximum result often comes from combining the largest elements with the smallest one, you can sort the array and evaluate only a few candidate combinations such as the largest two values with the smallest value. Sorting reduces the search space dramatically compared to brute force. This approach relies on the observation that extreme values dominate the expression.
Approach 3: Track Maximum, Second Maximum, and Minimum (Greedy) (Time: O(n), Space: O(1))
The optimal solution scans the array once while tracking three key values: the maximum element, the second maximum element, and the minimum element. These values are sufficient because the expression becomes largest when the positive contribution is maximized and the subtractive component is minimized. During a single pass, update these three variables using simple comparisons. After the scan, compute the expression using these extremes. This greedy observation removes the need for sorting or enumeration.
This solution is a classic pattern when working with Array problems: the optimal answer often depends only on a few extreme values. The reasoning also overlaps with Greedy strategies where local optimal choices lead to the global optimum, and sometimes with Sorting when extremes must be identified.
Recommended for interviews: The greedy single-pass approach. Start by explaining the brute force enumeration to demonstrate understanding of the constraints, then derive the insight that only the maximum, second maximum, and minimum elements affect the result. Interviewers expect the final O(n) time and O(1) space solution.
Solution
According to the problem description, we need to choose three elements a, b, and c at distinct indices such that the value of the expression a + b - c is maximized.
We only need to traverse the array to find the largest two elements a and b and the smallest element c. Then we can calculate the value of the expression.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
class Solution:
def maximizeExpressionOfThree(self, nums: List[int]) -> int:
a = b = -inf
c = inf
for x in nums:
if x < c:
c = x
if x >= a:
a, b = x, a
elif x > b:
b = x
return a + b - cclass Solution {
public int maximizeExpressionOfThree(int[] nums) {
final int inf = 1 << 30;
int a = -inf, b = -inf, c = inf;
for (int x : nums) {
if (x < c) {
c = x;
}
if (x >= a) {
b = a;
a = x;
} else if (x > b) {
b = x;
}
}
return a + b - c;
}
}class Solution {
public:
int maximizeExpressionOfThree(vector<int>& nums) {
const int inf = 1 << 30;
int a = -inf, b = -inf, c = inf;
for (int x : nums) {
if (x < c) {
c = x;
}
if (x >= a) {
b = a;
a = x;
} else if (x > b) {
b = x;
}
}
return a + b - c;
}
};function maximizeExpressionOfThree(nums: number[]): number {
const inf = 1 << 30;
let [a, b, c] = [-inf, -inf, inf];
for (const x of nums) {
if (x < c) {
c = x;
}
if (x >= a) {
b = a;
a = x;
} else if (x > b) {
b = x;
}
}
return a + b - c;
}func maximizeExpressionOfThree(nums []int) int {
const inf = 1 << 30
a, b, c := -inf, -inf, inf
for _, x := range nums {
if x < c {
c = x
}
if x >= a {
b = a
a = x
} else if x > b {
b = x
}
}
return a + b - c
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration (Brute Force) | O(n^3) | O(1) | Useful for validating logic or very small arrays |
| Sorting + Candidate Evaluation | O(n log n) | O(1)–O(n) | When sorting is acceptable and you want simple reasoning with extreme values |
| Track Max, Second Max, and Min (Greedy) | O(n) | O(1) | Best general solution; single pass without sorting |
Frequently asked questions
Is Maximize Expression of Three Elements easy or hard?
Maximize Expression of Three Elements is considered an Easy problem with an acceptance rate around 72%. The challenge is recognizing that only extreme values in the array affect the maximum expression, allowing a simple O(n) greedy solution.
Maximize Expression of Three Elements Python/Java solution
Most implementations follow the same pattern: iterate once through the array and update variables storing the maximum, second maximum, and minimum values. The final expression is computed after the loop. This logic translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Maximize Expression of Three Elements in O(n)?
Iterate through the array while maintaining three variables: the largest value, the second largest value, and the smallest value. Update these values with simple comparisons during the scan. After the pass completes, compute the expression using these extremes to get the maximum result.
What is the best approach for Maximize Expression of Three Elements?
The optimal approach scans the array once and tracks the maximum value, the second maximum value, and the minimum value. These extreme values determine the largest possible result for the expression. This greedy strategy runs in O(n) time and uses O(1) extra space.
Is Maximize Expression of Three Elements asked at Google/Amazon/Meta?
Problems based on maximizing expressions using array extremes appear frequently in technical interviews at companies like Amazon, Google, and Meta. The exact problem number may vary, but the underlying pattern—tracking maximum and minimum values in a single pass—is a common interview technique.
What data structure is used in Maximize Expression of Three Elements?
The solution primarily uses a basic array traversal. Instead of complex data structures, the algorithm maintains a few variables to store the maximum, second maximum, and minimum values while iterating through the array.
What is the time complexity of Maximize Expression of Three Elements?
The optimal greedy solution runs in O(n) time because the array is scanned once to identify the maximum, second maximum, and minimum elements. Space complexity is O(1) since only a few variables are stored. A brute force enumeration approach would take O(n^3) time.