Abstract / Summary

Given a list of integers, find the smallest total of three non overlapping increasing then decreasing sequences 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 55% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum

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 minimumSum method receives a list of integers and searches for a triplet of indices i < j < k such that the values satisfy nums[i] < nums[j] > nums[k]. For every qualifying triplet it computes the sum nums[i] + nums[j] + nums[k] and returns the smallest possible sum. If no such triplet exists the function returns -1. The implementation proceeds in three logical phases: constructing a structure that records the smallest element to the right of each position, scanning from the left while tracking the smallest element seen so far, and merging the left, current, and right information to update the best result.

Building the right-side minima

right = [ (size, +inf) ]          # min-heap: (position, minimum value)
for k in reversed(range(size)):
    if nums[k] < right[0][1]:
        heappush(right, (k, nums[k]))

In this phase the algorithm walks the array backward. The heap always holds the smallest value encountered so far together with its index. By comparing the current element nums[k] with the minimum stored at the top of the heap (right[0][1]), the code decides whether to insert a new candidate. Because the heap is ordered by the value, the smallest element to the right of any index can be retrieved in constant time from the heap’s root.

Maintaining the left-side minimum while scanning forward

left = nums[0]
for i in range(size):
    if right[0][0] < i:
        heappop(right)

    left = min(left, nums[i])
    # further processing follows

During the forward pass the variable left holds the smallest value seen from the start up to the current index i. Before using the right-hand heap, the code discards any entry whose stored index is no longer to the right of i (right[0][0] < i). This ensures that the heap always reflects a valid candidate for the third element of the triplet.

Combining left, current, and right to evaluate candidates

if left < nums[i] > right[0][1]:
    total = left + nums[i] + right[0][1]
    result = min(result, total)

The conditional checks the strict ordering required for a valid triplet: the left minimum must be smaller than the current element, and the current element must be larger than the smallest element to its right. When the condition holds, the sum of the three values is computed and the global result is updated with the smaller of the existing result and the newly found total.

Final result handling

return result if result < invalid else -1

The variable invalid is initialized to positive infinity, serving as a sentinel that indicates no valid triplet has been discovered. If result remains equal to this sentinel, the method returns -1; otherwise it returns the smallest sum found.

Edge-case considerations

The algorithm gracefully handles an input list containing a single element because the forward loop runs but the condition left < nums[i] > right[0][1] can never be satisfied, leaving result unchanged and causing -1 to be returned. When the list is strictly decreasing, the right-hand heap will always contain values larger than any left candidate, preventing the conditional from ever succeeding and again yielding -1. Duplicate values are also respected: the strict inequality operators (< and >) ensure that equal values do not form a valid triplet, so cases with repeated numbers are correctly excluded. Extremely large positive numbers are accommodated by the use of +inf as the initial sentinel, guaranteeing that any real sum will be smaller.

Performance optimizations observed

The use of a min-heap to store only the smallest element seen so far on the right side avoids the need for an auxiliary array that would store a minimum for every index. By pushing a new entry only when a strictly smaller value appears, the heap size stays bounded by the number of distinct decreasing minima, which is typically far less than the length of the list. The forward scan removes stale entries from the heap as soon as their index falls behind the current position, preventing unnecessary heap growth and keeping lookup of the right-hand minimum at the heap’s root constant time. The algorithm also reuses a single variable left to keep track of the left-hand minimum, eliminating the overhead of additional data structures. These choices collectively reduce memory pressure and keep the core operations tight, leading to an efficient execution profile even on large inputs.

Imagine you have a long row of building blocks, and each block has a different number written on it. This set of instructions is like playing a game to find three special blocks that are arranged in a specific mountain shape. The mountain shape means the first block is small, the middle block is the biggest, and the third block is small again.

To do this, the computer looks at all the blocks from the right side first to remember which small blocks are hiding at the end of the line. It keeps these in a special organized pile. Then, the computer walks through the row block by block starting from the beginning. It keeps track of the smallest number seen so far on the left side. As it walks, it checks every single block to see if it acts like a peak. A peak is a block that is taller than the small one to its left and also taller than the smallest one waiting on its right.

If it finds a perfect little mountain of three blocks, it adds their numbers together. The computer is very careful and keeps track of all the mountain sums it finds, always remembering the smallest one it has seen so far. If it reaches the end and finds a small sum, that is the winner of the game. If it never finds a set of three blocks that make a mountain, it decides that the game could not be finished.

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

Time: loglinear
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
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

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