Steady Climb or Drop Trios

Medium

Entrants stand in a row, each with a rating scores[i]; all ratings are distinct. A coach builds trios by taking three entrants at positions i < j < k (their order in the row is kept). A trio works if its ratings strictly increase (scores[i] < scores[j] < scores[k]) or strictly decrease (scores[i] > scores[j] > scores[k]). Return the number of trios that work. One entrant may belong to several trios.

Example 1

scores=[5, 1, 4, 2, 6] → 3

The trios (1, 4, 6) and (1, 2, 6) strictly increase and (5, 4, 2) strictly decreases, 3 in total.

Example 2

scores=[6, 5, 4, 3] → 4

Any three entrants are in decreasing order, and there are 4 ways to choose three out of four.

Example 3

scores=[1, 3, 2] → 0

Constraints

3 ≤ len(scores) ≤ 1000
1 ≤ scores[i] ≤ 10⁵
All values in scores are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Dynamic Programming

Similar problems

Counting the Longest Rising Selections Medium Rising Chain With Small Steps Hard Squared Variety Total Hard Steep Subsequence With the Largest Sum Hard Rebuild the Line from Height Records Medium

Input

scores=[5, 1, 4, 2, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.