Abstract / Summary

Given an array, find the smallest sum of three non overlapping increasing then decreasing subsequences covering all elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (70k+ submissions).

Typical patterns to solve this problem:

• Array

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method minimumSum. The method receives a list of integers and searches for a specific ordered triple of indices (i, j, k) such that i < j < k, the value at the first index is strictly smaller than the value at the second (nums[i] < nums[j]), and the value at the second is strictly larger than the value at the third (nums[j] > nums[k]). For every triple that satisfies these constraints the sum nums[i] + nums[j] + nums[k] is computed, and the smallest such sum is returned. If no triple meets the criteria the method returns -1.

The algorithm proceeds with three nested loops that enumerate all possible index triples while applying early conditional checks to prune the search space. The result is accumulated in a variable initialized to positive infinity, and the final value is transformed into the required return format.

Key Steps

The method begins by establishing a sentinel value for the best result and determining the length of the input list.

result = +inf
size = len(nums)

The outermost loop iterates over each possible first index i. Inside this loop the element at position i is stored in a temporary variable a.

for i in range(size):
    a = nums[i]

The second loop selects a candidate second index j that follows i. The element at j is captured as b. A strict ordering test a < b is performed before any deeper exploration, ensuring that only pairs where the first element is smaller than the second are considered.

    for j in range(i + 1, size):
        b = nums[j]
        if a < b:

When the ordering condition holds, the innermost loop scans the remaining positions for a third index k. The element at k is assigned to c. A second strict ordering test b > c validates the required “peak” shape of the triple. Only when both ordering constraints are satisfied is the sum of the three elements evaluated and the current best result possibly updated.

            for k in range(j + 1, size):
                c = nums[k]
                if b > c:
                    result = min(result, a + b + c)

After all loops have completed, the method translates the sentinel value back into the problem’s output convention: if result remains unchanged (still positive infinity) the function returns -1; otherwise it returns the smallest sum found.

return -1 if result == +inf else result

Edge Cases Handled

The algorithm naturally accommodates an empty input list. In that scenario size is zero, the outer loop never executes, result stays at positive infinity, and the method returns -1. The same flow applies when the list contains one or two elements; there are insufficient indices to form a triple, so the loops terminate without updating result, leading again to a -1 return.

When the list contains duplicate values the strict inequality checks (a < b and b > c) ensure that triples with equal adjacent elements are excluded. Consequently a sequence such as [5, 5, 5] yields no valid triple and the method returns -1. Conversely, a list that does contain a valid “valley-peak” pattern, for example [1, 4, 2], satisfies both ordering conditions and the sum 7 is returned.

If multiple qualifying triples exist, the use of min guarantees that the smallest sum among them is retained. For instance, in [1, 5, 2, 4, 3] the triples (1,5,2) and (1,4,3) both meet the constraints, and the algorithm will ultimately return the lower sum 8.

Performance Optimizations Observed

The most noticeable optimization is the early conditional guard if a < b: placed immediately after selecting the second index. By checking this relationship before entering the innermost loop, the algorithm avoids iterating over the third index for any pair that cannot possibly satisfy the required pattern, thereby reducing the number of inner loop executions.

A second guard if b > c: inside the innermost loop serves a similar purpose. It prevents the costly min operation and sum calculation for triples that fail the second ordering requirement, ensuring that only promising candidates affect the result.

The use of local variables a, b, and c to hold the current elements eliminates repeated indexing into the list, which can be beneficial in tight loops. Additionally, the built-in min function provides a concise and efficient way to maintain the smallest sum without explicit conditional branching.

Overall, the combination of early pruning checks and minimal per-iteration work contributes to a focused search that avoids unnecessary computation while still guaranteeing correctness for all input configurations.

Imagine a long row of numbered toy blocks lined up on the floor. This code is like a little robot helper that walks along the row to find three special blocks to pick up. To choose the right ones, the robot looks for a tricky pattern where the first block is smaller than the second one, and then the second block is bigger than the third one. It keeps track of the total value of these three blocks. Every time it finds a new group that fits this specific pattern, it checks to see if the total is smaller than the smallest one it has seen before. If it finds a smaller total, it remembers that one instead. The robot does this by looking at every possible combination of three blocks in order until it reaches the very end of the line. Once it has checked everything, it tells you the smallest total it managed to find.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality