Frontend Prep

Appearance

Maximum Profit Triplet ​

Problem Statement ​

Given an array of daily prices, find three days i < j < k such that prices[i] < prices[j] < prices[k] (strictly increasing) and return the maximum possible value of prices[i] + prices[j] + prices[k]. Return -1 if no such triplet exists.

Example 1:

Input: prices = [1, 5, 3, 4, 2, 6]
Output: 12
Explanation: Triplet (5, -, 6) is not valid because 5 is not followed by a middle > 5. 
             Triplet (1, 5, 6) works: 1 < 5 < 6, sum = 12. 
             Also (3, 4, 6) = 13 — actually better. 
             So max = 13. (Trace updated below.)

Corrected Example 1:

Input: prices = [1, 5, 3, 4, 2, 6]
Output: 13
Explanation: (3, 4, 6) gives 3 + 4 + 6 = 13. Checking all valid triples, 13 is the max.

Example 2:

Input: prices = [5, 4, 3, 2, 1]
Output: -1
Explanation: Array is strictly decreasing; no valid triplet.

Constraints:

  • 3 <= prices.length <= 10^5.
  • 1 <= prices[i] <= 10^4.

Difficulty: Medium Round: OA

Pattern Recognition ​

  • What is the input structure? A flat array of integers.
  • What are we optimizing? Max sum of three strictly increasing values at strictly increasing indices.
  • What pattern does this fit? Fix the middle. For each index j, find the max value to the left that is strictly less than prices[j] and the max value to the right that is strictly greater than prices[j].
  • Why does this pattern fit? The triplet constraint is symmetric around j. Once you pick j, the left and right subproblems are independent.

Approach ​

Brute Force — Triple Loop ​

For each (i, j, k), check the inequality and track the max sum.

Time: O(n^3). Space: O(1). Why insufficient: For n = 10^5, this is 10^15 ops. Dead on arrival.

Intermediate — O(n^2) Precomputation ​

For each j, scan left for the max value < prices[j], and scan right for the max value > prices[j]. Combine.

Time: O(n^2). Space: O(n).

Acceptable for n <= a few thousand. For n = 10^5, still 10^10 ops.

Optimal — Two Passes with Running Max ​

Key Insight: You do not need the strict comparison pre-computed per j if you are willing to replace "max left less than prices[j]" with a slightly different structure. The O(n log n) version uses a sorted structure to answer "max value at indices < j with value < prices[j]" in O(log n).

A cleaner O(n log n) for this problem uses a Binary Indexed Tree (Fenwick tree) or ordered set with prefix-max keyed on value:

  1. Compress prices to ranks.
  2. Left-to-right pass: for each j, query the Fenwick tree for max value at ranks < rank(prices[j]), store as leftMaxLess[j]. Then insert prices[j] into the tree at position rank(prices[j]).
  3. Right-to-left pass (with a second tree): for each j, query for max value at ranks > rank(prices[j]), store as rightMaxGreater[j]. Then insert prices[j].
  4. Scan j from 1 to n-2, compute leftMaxLess[j] + prices[j] + rightMaxGreater[j], track max.

Time: O(n log n). Space: O(n).

At OA time, the O(n^2) version is usually fast enough and much simpler. If the problem constraints force O(n log n), reach for the Fenwick tree.

Walkthrough (O(n^2) version) ​

Trace on prices = [1, 5, 3, 4, 2, 6]:

leftMaxLess[j] (max of prices[i] for i < j with prices[i] < prices[j]):

jprices[j]candidates (i < j, prices[i] < prices[j])leftMaxLess[j]
01—-1
151
231
343
421
565

rightMaxGreater[j] (max of prices[k] for k > j with prices[k] > prices[j]):

jprices[j]candidates (k > j, prices[k] > prices[j])rightMaxGreater[j]
016
156
236
346
426
56—-1

Combine:

jleftMaxLess[j]prices[j]rightMaxGreater[j]sum
115612
213610
334613
41269

Answer: 13 from triplet (3, 4, 6).

Implementation ​

typescript
function maxProfitTriplet(prices: number[]): number {
    const n = prices.length;
    if (n < 3) return -1;

    const leftMaxLess = new Array(n).fill(-1);
    const rightMaxGreater = new Array(n).fill(-1);

    // leftMaxLess[j]: max price at index < j with value < prices[j].
    for (let j = 0; j < n; j++) {
        let best = -1;
        for (let i = 0; i < j; i++) {
            if (prices[i] < prices[j]) best = Math.max(best, prices[i]);
        }
        leftMaxLess[j] = best;
    }

    // rightMaxGreater[j]: max price at index > j with value > prices[j].
    for (let j = 0; j < n; j++) {
        let best = -1;
        for (let k = j + 1; k < n; k++) {
            if (prices[k] > prices[j]) best = Math.max(best, prices[k]);
        }
        rightMaxGreater[j] = best;
    }

    let best = -1;
    for (let j = 1; j < n - 1; j++) {
        if (leftMaxLess[j] !== -1 && rightMaxGreater[j] !== -1) {
            best = Math.max(best, leftMaxLess[j] + prices[j] + rightMaxGreater[j]);
        }
    }
    return best;
}
cpp
#include <vector>
#include <algorithm>

int maxProfitTriplet(const std::vector<int>& prices) {
    int n = prices.size();
    if (n < 3) return -1;

    std::vector<int> leftMaxLess(n, -1), rightMaxGreater(n, -1);

    for (int j = 0; j < n; j++) {
        int best = -1;
        for (int i = 0; i < j; i++)
            if (prices[i] < prices[j]) best = std::max(best, prices[i]);
        leftMaxLess[j] = best;
    }
    for (int j = 0; j < n; j++) {
        int best = -1;
        for (int k = j + 1; k < n; k++)
            if (prices[k] > prices[j]) best = std::max(best, prices[k]);
        rightMaxGreater[j] = best;
    }

    int best = -1;
    for (int j = 1; j < n - 1; j++) {
        if (leftMaxLess[j] != -1 && rightMaxGreater[j] != -1)
            best = std::max(best, leftMaxLess[j] + prices[j] + rightMaxGreater[j]);
    }
    return best;
}

Watch out:

  1. Strict vs non-strict inequality. The problem says strictly increasing, so < and >. Using <= admits equal values and yields different (wrong) triplets.
  2. Returning 0 vs -1 when no triplet exists. Clarify. The canonical convention is -1 as a sentinel.
  3. Off-by-one on the middle loop. j ranges from 1 to n - 2 inclusive — you need at least one index on each side.

Complexity Analysis ​

TimeSpace
Brute ForceO(n^3)O(1)
O(n^2) PrecomputationO(n^2)O(n)
Fenwick Tree (O(n log n))O(n log n)O(n)

Bottleneck: For the O(n^2) version, the nested scans. For the Fenwick version, the log factor from tree queries.

Edge Cases ​

  1. Fewer than 3 elements — return -1 immediately.
  2. Strictly decreasing array — no triplet; return -1.
  3. All equal values — no strict inequality; return -1.
  4. Exactly 3 elements, increasing — return the sum.
  5. Duplicate values at middle — if multiple i give the same leftMaxLess, take the max; the algorithm does this naturally.
  • LC 334 — Increasing Triplet Subsequence — Same shape, but only asks for existence (boolean), not the max sum. Has a beautiful O(n) solution with two "smallest" trackers.
  • LC 300 — Longest Increasing Subsequence — Generalization to arbitrary length. O(n log n) with patience sort.
  • LC 456 — 132 Pattern — Related pattern-matching problem, uses a monotonic stack.

OA Strategy Notes ​

Medium-difficulty OA problem. Expect 20-30 minutes. The O(n^2) version is likely fast enough for HackerRank's typical limits (n <= 5000). If constraints push to 10^5, prep the Fenwick tree approach. In either case, verify on the "strictly decreasing" edge case and confirm -1 is returned.

What is Expected at Each Level ​

Junior: Brute force O(n^3), arrives at O(n^2) with prompting.

Mid-level: Writes O(n^2) cleanly. Handles edge cases. Notes that Fenwick tree could push to O(n log n) if needed.

Senior: Implements the Fenwick tree version without being asked. Discusses strict vs non-strict and the implications on ties. Connects to LC 334 as the existence-only cousin.

Frontend interview preparation reference.