What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Linear DP, which you haven’t finished yet.

P2MediumBuilt on Linear DP~3 min speedrun

Best Left Half Carry (Best Sightseeing Pair)

Built on

Linear DPThe score of a pair splits into one term for the left spot and one term for the right spot, so one carried value, best_left, is the whole state.

The problem

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.

The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.

Example 1

Input:values = [8,1,5,2,6]

Output:11

Take the spots at positions 0 and 2. The score is 8 + 5 - 2 = 11. Every other pair scores less.

Best Sightseeing Pair

Spot it when: You must pick two positions i < j of an array to get the highest score, where the score adds one term for i and one term for j, and the distance j - i is part of it, for example values[i] + values[j] - (j - i).

Python

1	def max_score_sightseeing_pair(values: list[int]) -> int:
2	"""Best Sightseeing Pair: carry the best left spot, values[i] + i, and score every spot j against it.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best_left: the largest values[i] + i over the spots before j; best: the largest pair score found so far
6	best_left = values[0]
7	best = float('-inf')
8	for j in range(1, len(values)):
9	# 1. Score Spot j As The Right End:
10	# The score is (values[i] + i) + (values[j] - j), so the best partner for j is the spot with the largest values[i] + i before j.
11	best = max(best, best_left + values[j] - j)
12
13	# 2. Update best_left With Spot j:
14	# This runs after the score, so spot j is never paired with itself.
15	best_left = max(best_left, values[j] + j)
16
17	return best

Invariant: Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j.

The score values[i] + values[j] + i - j splits into a part that needs only i, which is values[i] + i, and a part that needs only j, which is values[j] - j. So for each j the best partner is the earlier spot with the largest values[i] + i, and one carried value, best_left, holds it. best_left is the maximum over every earlier spot, so no pair is missed, and each spot is read once. The trap is the order inside the loop. Score j first with best = max(best, best_left + values[j] - j), and only then update best_left with j, using best_left = max(best_left, values[j] + j). If best_left changes first, spot j is paired with itself and scores 2 * values[j].

See it run

Best Sightseeing Pair, step by step

best_left 8best -inf

Each column is one spot, numbered from 0.

j the spot being scored
best_left the earlier spot with the largest values[i] + i

Start: best_left = values[0] + 0 = 8. Spot 0 is the only spot before spot 1.

8best_left

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Updating best_left with spot j before scoring j
Mistake
```
best_left = max(best_left, values[j] + j)
best = max(best, best_left + values[j] - j)
```
Fix
```
best = max(best, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
```
What happens: best_left must hold only the spots before j. When best_left is updated first, it already holds values[j] + j. The score then uses spot j at both ends of the pair. That score is (values[j] + j) + (values[j] - j), which is 2 * values[j]. At j = 4 in the example, the pair scores 12, which is 2 * 6, and no real pair scores that high.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 12Fix: returns 11
Gotcha 2: Carrying values[i] instead of values[i] + i
Mistake
```
best_left = max(best_left, values[j])
```
Fix
```
best_left = max(best_left, values[j] + j)
```
What happens: The distance is part of the left term. A spot nearer to j loses less, so the carried value must be values[i] + i. With only values[i], the four 1s in the example look equal and best_left stays 1. The pair of spots 3 and 4 is then scored as 1 + 9 - 4 = 6. Its real score is 1 + 9 - 1 = 9.
Example: values = [1, 1, 1, 1, 9]
Mistake: returns 6Fix: returns 9
Gotcha 3: Leaving out - j from the score
Mistake
```
best = max(best, best_left + values[j])
```
Fix
```
best = max(best, best_left + values[j] - j)
```
What happens: best_left holds values[i] + i. The + i is correct only when the right spot pays - j, because i - j is the negative distance. Without - j, the distance is never subtracted and the score is too large. In the example, the pair of spots 0 and 4 scores 8 + 6 = 14 instead of 8 + 6 - 4 = 10.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 14Fix: returns 11
Gotcha 4: Starting the loop at j = 0
Mistake
```
for j in range(0, len(values)):
```
Fix
```
for j in range(1, len(values)):
```
What happens: best_left starts as values[0], which is spot 0 as a left end. At j = 0, the loop scores spot 0 against that same spot: (8 + 0) + (8 - 0) = 16. A pair needs two different spots, so the loop starts at j = 1.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 16Fix: returns 11

Not this one if…

The score adds up every number between the two ends, as in Maximum Subarray (LC 53), instead of only the two end values and the distance between them, so the carried value is a running sum, not a best left end. See Kadane's Algorithm
You may buy and sell many times, as in Best Time to Buy and Sell Stock II (LC 122), so every day has a state (holding a share or not), not one best left end for a single pair. See State Machine DP
Every position needs the best value on its left and also the best value on its right, as in Trapping Rain Water (LC 42), so one pass from the left is not enough. See Prefix-Suffix Scan

Deep Dive

The observation: split the score into a left part and a right part

A pair of spots i < j scores values[i] + values[j] + i - j. Move the terms: the score is (values[i] + i) + (values[j] - j). The first bracket reads only i. The second bracket reads only j.

Example: values = [8, 1, 5, 2, 6], i = 0 and j = 2. The left part is 8 + 0 = 8. The right part is 5 - 2 = 3. The score is 8 + 3 = 11, which is the answer.

For a fixed j, the right part is one number. Only the left part changes with i. So the best partner of j is the spot i < j with the largest values[i] + i.

Example: for j = 4, the left parts of spots 0 to 3 are 8, 2, 7 and 5, and the right part is 6 - 4 = 2. The best left part is 8, so the best score that ends at spot 4 is 10.

Why one variable, `best_left`, is enough

At the start of the iteration for j, best_left is the largest values[i] + i over all i < j. This is a prefix maximum. One comparison per spot keeps it up to date, so no table is needed.

The best pair that ends at j scores best_left + values[j] - j. Every pair (i, j) is counted under its right end j, and its score is at most the score with the best partner. So best, the maximum over all j, is the best pair.

The brute force scores N * (N - 1) / 2 pairs. For N = 5 * 10⁴ that is 1,249,975,000 pairs. The loop reads each spot once.

What this card adds to Linear DP

Linear DP walks the array once and keeps the state in a few registers. This card keeps that single pass and that rolling register.

The new part is what the register holds. In Linear DP, the state at step i is built from the one or two states just before it. Here the register is a maximum over all earlier spots, and the answer is a separate maximum, best, over all right ends. That is why there are two variables.

This is not Kadane's Algorithm. Kadane's state is the sum of one unbroken run. Here the numbers between i and j are not added. Only the two end values and the distance j - i count.

The order inside the loop, and the same idea with a minimum

The loop scores j first and updates best_left with j second. When best_left is updated first, it already holds spot j, so the score pairs j with itself and equals 2 * values[j]. For [8, 1, 5, 2, 6], the update-first order returns 12 and the correct order returns 11.

Best Time to Buy and Sell Stock (LC 121) uses the same loop. The profit of a trade is prices[j] - prices[i], so the left part is -prices[i], the right part is prices[j], and best_left is the lowest price so far, negated. Positions are not part of that score, so there is no - j.

Time is O(N), because the loop does constant work for each of the N - 1 spots. Space is O(1), because only best_left and best are kept.

60-Second Pitch

"The brute force scores every pair, which is about N squared over two pairs. I split the score into a left part, values i plus i, and a right part, values j minus j. For a fixed j the right part is one number, so the best partner is the earlier spot with the largest left part. I keep that maximum in one variable, best left, which starts as spot 0. For each j from 1, I first score the pair, best left plus values j minus j, and keep the largest score. Only after that I update best left with j. If I did it before, j would pair with itself. That is one pass, O of N time and O of 1 space. For 8, 1, 5, 2, 6 the answer is 11, from spots 0 and 2."

Common Questions

Why can the loop not keep the largest values[i] and fix the distance later?: The distance depends on which spot is chosen. A spot with a smaller value but a larger index i can lose less to the distance. The left term must be values[i] + i. For [1, 1, 1, 1, 9], the largest value alone gives 6, and the correct answer is 9.
How does the same loop solve Best Time to Buy and Sell Stock (LC 121)?: The profit is prices[j] - prices[i], so the left term is -prices[i] and the right term is prices[j]. best_left is the lowest price so far, negated. The positions are not part of the score, so there is no - j. A trade is optional, so best starts at 0.
How do you return the pair of spots and not only the score?: Keep the index of the spot that gave best_left, called left_index. When the score line improves best, save (left_index, j). When the update line improves best_left, set left_index = j. For [8, 1, 5, 2, 6], this returns the spots 0 and 2.
What changes when the score rewards distance, as in values[i] + values[j] + j - i?: The terms move to the other side. The left term is values[i] - i and the right term is values[j] + j. The loop keeps the same shape and the same order: score j first, then update best_left with j.
Can the time or the space be smaller?: The loop uses O(N) time and O(1) space. Every value must be read at least once, so no algorithm can take less than O(N) time. The space is already constant, because only best_left and best are kept.

SWE Reasoning

Spot it

The question asks for the best pair of positions i < j, not for a sum over a run of numbers.
The score adds a term that reads only i and a term that reads only j. The distance j - i splits into + i for the left spot and - j for the right spot.
The brute force scores all N * (N - 1) / 2 pairs. For N = 5 * 10⁴, that is about 1.25 * 10^9 pairs.
For a fixed j, only the left term changes with i, so the best i is a maximum over a prefix of the array.

The invariant, step by step

Before the loop, best_left = values[0] and best = float('-inf'). Spot 0 is the only spot before spot 1, and its left term is values[0] + 0.
At the start of the iteration for j, best_left is the largest values[i] + i over all i < j.
The score line sets best = max(best, best_left + values[j] - j). This is the best pair that ends at j.
The update line sets best_left = max(best_left, values[j] + j). It runs after the score line, so best_left still holds only the spots before j when j is scored. Afterwards it holds all spots up to j, which is what the iteration for j + 1 needs.
After the last j, every pair (i, j) was considered through its right end j. best is the largest score.
Trace for [8, 1, 5, 2, 6]: after j = 1, 2, 3, 4, best is 8, 11, 11, 11 and best_left is 8, 8, 8, 10. The answer is 11, from spots 0 and 2.

Traps

Updating best_left with j before scoring j. best_left already holds spot j, so j is paired with itself and scores 2 * values[j]. [8, 1, 5, 2, 6] returns 12 instead of 11.
Carrying values[i] without + i. The distance is lost from the left term. [1, 1, 1, 1, 9] returns 6 instead of 9.
Leaving out - j from the score. The distance is never subtracted. [8, 1, 5, 2, 6] returns 14 instead of 11.
Starting the loop at j = 0. Spot 0 is scored against itself. The same input returns 16.
Starting best at minus infinity in Best Time to Buy and Sell Stock (LC 121). A trade is optional there, so the answer is never negative. [7, 6, 4, 3, 1] returns -1 instead of 0. Start best at 0.
Copying the signs when the score rewards distance. For the score values[i] + values[j] + j - i, the left term is values[i] - i and the right term is values[j] + j. Read the signs from the formula, not from this card.

Practice

Canonical LeetCode:Best Sightseeing Pair (LC 1014)Best Time to Buy and Sell Stock (LC 121)Maximum Difference Between Increasing Elements (LC 2016)

Theory Context•Dynamic Programming

Builds on Linear DP, which you haven’t finished yet.

P2MediumBuilt on Linear DP~3 min speedrun

Best Left Half Carry (Best Sightseeing Pair)

Built on

Linear DPThe score of a pair splits into one term for the left spot and one term for the right spot, so one carried value, best_left, is the whole state.

The problem

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.

The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.

Example 1

Input:values = [8,1,5,2,6]

Output:11

Take the spots at positions 0 and 2. The score is 8 + 5 - 2 = 11. Every other pair scores less.

Best Sightseeing Pair

Python

1	def max_score_sightseeing_pair(values: list[int]) -> int:
2	"""Best Sightseeing Pair: carry the best left spot, values[i] + i, and score every spot j against it.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best_left: the largest values[i] + i over the spots before j; best: the largest pair score found so far
6	best_left = values[0]
7	best = float('-inf')
8	for j in range(1, len(values)):
9	# 1. Score Spot j As The Right End:
10	# The score is (values[i] + i) + (values[j] - j), so the best partner for j is the spot with the largest values[i] + i before j.
11	best = max(best, best_left + values[j] - j)
12
13	# 2. Update best_left With Spot j:
14	# This runs after the score, so spot j is never paired with itself.
15	best_left = max(best_left, values[j] + j)
16
17	return best

Invariant: Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j.

See it run

Best Sightseeing Pair, step by step

best_left 8best -inf

Each column is one spot, numbered from 0.

j the spot being scored
best_left the earlier spot with the largest values[i] + i

Start: best_left = values[0] + 0 = 8. Spot 0 is the only spot before spot 1.

8best_left

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Updating best_left with spot j before scoring j
Mistake
```
best_left = max(best_left, values[j] + j)
best = max(best, best_left + values[j] - j)
```
Fix
```
best = max(best, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
```
What happens: best_left must hold only the spots before j. When best_left is updated first, it already holds values[j] + j. The score then uses spot j at both ends of the pair. That score is (values[j] + j) + (values[j] - j), which is 2 * values[j]. At j = 4 in the example, the pair scores 12, which is 2 * 6, and no real pair scores that high.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 12Fix: returns 11
Gotcha 2: Carrying values[i] instead of values[i] + i
Mistake
```
best_left = max(best_left, values[j])
```
Fix
```
best_left = max(best_left, values[j] + j)
```
What happens: The distance is part of the left term. A spot nearer to j loses less, so the carried value must be values[i] + i. With only values[i], the four 1s in the example look equal and best_left stays 1. The pair of spots 3 and 4 is then scored as 1 + 9 - 4 = 6. Its real score is 1 + 9 - 1 = 9.
Example: values = [1, 1, 1, 1, 9]
Mistake: returns 6Fix: returns 9
Gotcha 3: Leaving out - j from the score
Mistake
```
best = max(best, best_left + values[j])
```
Fix
```
best = max(best, best_left + values[j] - j)
```
What happens: best_left holds values[i] + i. The + i is correct only when the right spot pays - j, because i - j is the negative distance. Without - j, the distance is never subtracted and the score is too large. In the example, the pair of spots 0 and 4 scores 8 + 6 = 14 instead of 8 + 6 - 4 = 10.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 14Fix: returns 11
Gotcha 4: Starting the loop at j = 0
Mistake
```
for j in range(0, len(values)):
```
Fix
```
for j in range(1, len(values)):
```
What happens: best_left starts as values[0], which is spot 0 as a left end. At j = 0, the loop scores spot 0 against that same spot: (8 + 0) + (8 - 0) = 16. A pair needs two different spots, so the loop starts at j = 1.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 16Fix: returns 11

Not this one if…

The score adds up every number between the two ends, as in Maximum Subarray (LC 53), instead of only the two end values and the distance between them, so the carried value is a running sum, not a best left end. See Kadane's Algorithm
You may buy and sell many times, as in Best Time to Buy and Sell Stock II (LC 122), so every day has a state (holding a share or not), not one best left end for a single pair. See State Machine DP
Every position needs the best value on its left and also the best value on its right, as in Trapping Rain Water (LC 42), so one pass from the left is not enough. See Prefix-Suffix Scan

Deep Dive

The observation: split the score into a left part and a right part

A pair of spots i < j scores values[i] + values[j] + i - j. Move the terms: the score is (values[i] + i) + (values[j] - j). The first bracket reads only i. The second bracket reads only j.

Example: values = [8, 1, 5, 2, 6], i = 0 and j = 2. The left part is 8 + 0 = 8. The right part is 5 - 2 = 3. The score is 8 + 3 = 11, which is the answer.

For a fixed j, the right part is one number. Only the left part changes with i. So the best partner of j is the spot i < j with the largest values[i] + i.

Example: for j = 4, the left parts of spots 0 to 3 are 8, 2, 7 and 5, and the right part is 6 - 4 = 2. The best left part is 8, so the best score that ends at spot 4 is 10.

Why one variable, `best_left`, is enough

At the start of the iteration for j, best_left is the largest values[i] + i over all i < j. This is a prefix maximum. One comparison per spot keeps it up to date, so no table is needed.

The brute force scores N * (N - 1) / 2 pairs. For N = 5 * 10⁴ that is 1,249,975,000 pairs. The loop reads each spot once.

What this card adds to Linear DP

Linear DP walks the array once and keeps the state in a few registers. This card keeps that single pass and that rolling register.

This is not Kadane's Algorithm. Kadane's state is the sum of one unbroken run. Here the numbers between i and j are not added. Only the two end values and the distance j - i count.

The order inside the loop, and the same idea with a minimum

Time is O(N), because the loop does constant work for each of the N - 1 spots. Space is O(1), because only best_left and best are kept.

60-Second Pitch

Common Questions

Why can the loop not keep the largest values[i] and fix the distance later?: The distance depends on which spot is chosen. A spot with a smaller value but a larger index i can lose less to the distance. The left term must be values[i] + i. For [1, 1, 1, 1, 9], the largest value alone gives 6, and the correct answer is 9.
How does the same loop solve Best Time to Buy and Sell Stock (LC 121)?: The profit is prices[j] - prices[i], so the left term is -prices[i] and the right term is prices[j]. best_left is the lowest price so far, negated. The positions are not part of the score, so there is no - j. A trade is optional, so best starts at 0.
How do you return the pair of spots and not only the score?: Keep the index of the spot that gave best_left, called left_index. When the score line improves best, save (left_index, j). When the update line improves best_left, set left_index = j. For [8, 1, 5, 2, 6], this returns the spots 0 and 2.
What changes when the score rewards distance, as in values[i] + values[j] + j - i?: The terms move to the other side. The left term is values[i] - i and the right term is values[j] + j. The loop keeps the same shape and the same order: score j first, then update best_left with j.
Can the time or the space be smaller?: The loop uses O(N) time and O(1) space. Every value must be read at least once, so no algorithm can take less than O(N) time. The space is already constant, because only best_left and best are kept.

SWE Reasoning

Spot it

The question asks for the best pair of positions i < j, not for a sum over a run of numbers.
The score adds a term that reads only i and a term that reads only j. The distance j - i splits into + i for the left spot and - j for the right spot.
The brute force scores all N * (N - 1) / 2 pairs. For N = 5 * 10⁴, that is about 1.25 * 10^9 pairs.
For a fixed j, only the left term changes with i, so the best i is a maximum over a prefix of the array.

The invariant, step by step

Before the loop, best_left = values[0] and best = float('-inf'). Spot 0 is the only spot before spot 1, and its left term is values[0] + 0.
At the start of the iteration for j, best_left is the largest values[i] + i over all i < j.
The score line sets best = max(best, best_left + values[j] - j). This is the best pair that ends at j.
The update line sets best_left = max(best_left, values[j] + j). It runs after the score line, so best_left still holds only the spots before j when j is scored. Afterwards it holds all spots up to j, which is what the iteration for j + 1 needs.
After the last j, every pair (i, j) was considered through its right end j. best is the largest score.
Trace for [8, 1, 5, 2, 6]: after j = 1, 2, 3, 4, best is 8, 11, 11, 11 and best_left is 8, 8, 8, 10. The answer is 11, from spots 0 and 2.

Traps

Updating best_left with j before scoring j. best_left already holds spot j, so j is paired with itself and scores 2 * values[j]. [8, 1, 5, 2, 6] returns 12 instead of 11.
Carrying values[i] without + i. The distance is lost from the left term. [1, 1, 1, 1, 9] returns 6 instead of 9.
Leaving out - j from the score. The distance is never subtracted. [8, 1, 5, 2, 6] returns 14 instead of 11.
Starting the loop at j = 0. Spot 0 is scored against itself. The same input returns 16.
Starting best at minus infinity in Best Time to Buy and Sell Stock (LC 121). A trade is optional there, so the answer is never negative. [7, 6, 4, 3, 1] returns -1 instead of 0. Start best at 0.
Copying the signs when the score rewards distance. For the score values[i] + values[j] + j - i, the left term is values[i] - i and the right term is values[j] + j. Read the signs from the formula, not from this card.

Practice

Canonical LeetCode:Best Sightseeing Pair (LC 1014)Best Time to Buy and Sell Stock (LC 121)Maximum Difference Between Increasing Elements (LC 2016)

Theory Context•Dynamic Programming

Builds on Linear DP, which you haven’t finished yet.

P2MediumBuilt on Linear DP~3 min speedrun

Best Left Half Carry (Best Sightseeing Pair)

Built on

Linear DPThe score of a pair splits into one term for the left spot and one term for the right spot, so one carried value, best_left, is the whole state.

The problem

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.

The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.

Example 1

Input:values = [8,1,5,2,6]

Output:11

Take the spots at positions 0 and 2. The score is 8 + 5 - 2 = 11. Every other pair scores less.

Best Sightseeing Pair

Python

1	def max_score_sightseeing_pair(values: list[int]) -> int:
2	"""Best Sightseeing Pair: carry the best left spot, values[i] + i, and score every spot j against it.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best_left: the largest values[i] + i over the spots before j; best: the largest pair score found so far
6	best_left = values[0]
7	best = float('-inf')
8	for j in range(1, len(values)):
9	# 1. Score Spot j As The Right End:
10	# The score is (values[i] + i) + (values[j] - j), so the best partner for j is the spot with the largest values[i] + i before j.
11	best = max(best, best_left + values[j] - j)
12
13	# 2. Update best_left With Spot j:
14	# This runs after the score, so spot j is never paired with itself.
15	best_left = max(best_left, values[j] + j)
16
17	return best

Invariant: Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j.

See it run

Best Sightseeing Pair, step by step

best_left 8best -inf

Each column is one spot, numbered from 0.

j the spot being scored
best_left the earlier spot with the largest values[i] + i

Start: best_left = values[0] + 0 = 8. Spot 0 is the only spot before spot 1.

8best_left

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Updating best_left with spot j before scoring j
Mistake
```
best_left = max(best_left, values[j] + j)
best = max(best, best_left + values[j] - j)
```
Fix
```
best = max(best, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
```
What happens: best_left must hold only the spots before j. When best_left is updated first, it already holds values[j] + j. The score then uses spot j at both ends of the pair. That score is (values[j] + j) + (values[j] - j), which is 2 * values[j]. At j = 4 in the example, the pair scores 12, which is 2 * 6, and no real pair scores that high.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 12Fix: returns 11
Gotcha 2: Carrying values[i] instead of values[i] + i
Mistake
```
best_left = max(best_left, values[j])
```
Fix
```
best_left = max(best_left, values[j] + j)
```
What happens: The distance is part of the left term. A spot nearer to j loses less, so the carried value must be values[i] + i. With only values[i], the four 1s in the example look equal and best_left stays 1. The pair of spots 3 and 4 is then scored as 1 + 9 - 4 = 6. Its real score is 1 + 9 - 1 = 9.
Example: values = [1, 1, 1, 1, 9]
Mistake: returns 6Fix: returns 9
Gotcha 3: Leaving out - j from the score
Mistake
```
best = max(best, best_left + values[j])
```
Fix
```
best = max(best, best_left + values[j] - j)
```
What happens: best_left holds values[i] + i. The + i is correct only when the right spot pays - j, because i - j is the negative distance. Without - j, the distance is never subtracted and the score is too large. In the example, the pair of spots 0 and 4 scores 8 + 6 = 14 instead of 8 + 6 - 4 = 10.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 14Fix: returns 11
Gotcha 4: Starting the loop at j = 0
Mistake
```
for j in range(0, len(values)):
```
Fix
```
for j in range(1, len(values)):
```
What happens: best_left starts as values[0], which is spot 0 as a left end. At j = 0, the loop scores spot 0 against that same spot: (8 + 0) + (8 - 0) = 16. A pair needs two different spots, so the loop starts at j = 1.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 16Fix: returns 11

Not this one if…

The score adds up every number between the two ends, as in Maximum Subarray (LC 53), instead of only the two end values and the distance between them, so the carried value is a running sum, not a best left end. See Kadane's Algorithm
You may buy and sell many times, as in Best Time to Buy and Sell Stock II (LC 122), so every day has a state (holding a share or not), not one best left end for a single pair. See State Machine DP
Every position needs the best value on its left and also the best value on its right, as in Trapping Rain Water (LC 42), so one pass from the left is not enough. See Prefix-Suffix Scan

Deep Dive

The observation: split the score into a left part and a right part

A pair of spots i < j scores values[i] + values[j] + i - j. Move the terms: the score is (values[i] + i) + (values[j] - j). The first bracket reads only i. The second bracket reads only j.

Example: values = [8, 1, 5, 2, 6], i = 0 and j = 2. The left part is 8 + 0 = 8. The right part is 5 - 2 = 3. The score is 8 + 3 = 11, which is the answer.

For a fixed j, the right part is one number. Only the left part changes with i. So the best partner of j is the spot i < j with the largest values[i] + i.

Example: for j = 4, the left parts of spots 0 to 3 are 8, 2, 7 and 5, and the right part is 6 - 4 = 2. The best left part is 8, so the best score that ends at spot 4 is 10.

Why one variable, `best_left`, is enough

At the start of the iteration for j, best_left is the largest values[i] + i over all i < j. This is a prefix maximum. One comparison per spot keeps it up to date, so no table is needed.

The brute force scores N * (N - 1) / 2 pairs. For N = 5 * 10⁴ that is 1,249,975,000 pairs. The loop reads each spot once.

What this card adds to Linear DP

Linear DP walks the array once and keeps the state in a few registers. This card keeps that single pass and that rolling register.

This is not Kadane's Algorithm. Kadane's state is the sum of one unbroken run. Here the numbers between i and j are not added. Only the two end values and the distance j - i count.

The order inside the loop, and the same idea with a minimum

Time is O(N), because the loop does constant work for each of the N - 1 spots. Space is O(1), because only best_left and best are kept.

60-Second Pitch

Common Questions

Why can the loop not keep the largest values[i] and fix the distance later?: The distance depends on which spot is chosen. A spot with a smaller value but a larger index i can lose less to the distance. The left term must be values[i] + i. For [1, 1, 1, 1, 9], the largest value alone gives 6, and the correct answer is 9.
How does the same loop solve Best Time to Buy and Sell Stock (LC 121)?: The profit is prices[j] - prices[i], so the left term is -prices[i] and the right term is prices[j]. best_left is the lowest price so far, negated. The positions are not part of the score, so there is no - j. A trade is optional, so best starts at 0.
How do you return the pair of spots and not only the score?: Keep the index of the spot that gave best_left, called left_index. When the score line improves best, save (left_index, j). When the update line improves best_left, set left_index = j. For [8, 1, 5, 2, 6], this returns the spots 0 and 2.
What changes when the score rewards distance, as in values[i] + values[j] + j - i?: The terms move to the other side. The left term is values[i] - i and the right term is values[j] + j. The loop keeps the same shape and the same order: score j first, then update best_left with j.
Can the time or the space be smaller?: The loop uses O(N) time and O(1) space. Every value must be read at least once, so no algorithm can take less than O(N) time. The space is already constant, because only best_left and best are kept.

SWE Reasoning

Spot it

The question asks for the best pair of positions i < j, not for a sum over a run of numbers.
The score adds a term that reads only i and a term that reads only j. The distance j - i splits into + i for the left spot and - j for the right spot.
The brute force scores all N * (N - 1) / 2 pairs. For N = 5 * 10⁴, that is about 1.25 * 10^9 pairs.
For a fixed j, only the left term changes with i, so the best i is a maximum over a prefix of the array.

The invariant, step by step

Before the loop, best_left = values[0] and best = float('-inf'). Spot 0 is the only spot before spot 1, and its left term is values[0] + 0.
At the start of the iteration for j, best_left is the largest values[i] + i over all i < j.
The score line sets best = max(best, best_left + values[j] - j). This is the best pair that ends at j.
The update line sets best_left = max(best_left, values[j] + j). It runs after the score line, so best_left still holds only the spots before j when j is scored. Afterwards it holds all spots up to j, which is what the iteration for j + 1 needs.
After the last j, every pair (i, j) was considered through its right end j. best is the largest score.
Trace for [8, 1, 5, 2, 6]: after j = 1, 2, 3, 4, best is 8, 11, 11, 11 and best_left is 8, 8, 8, 10. The answer is 11, from spots 0 and 2.

Traps

Updating best_left with j before scoring j. best_left already holds spot j, so j is paired with itself and scores 2 * values[j]. [8, 1, 5, 2, 6] returns 12 instead of 11.
Carrying values[i] without + i. The distance is lost from the left term. [1, 1, 1, 1, 9] returns 6 instead of 9.
Leaving out - j from the score. The distance is never subtracted. [8, 1, 5, 2, 6] returns 14 instead of 11.
Starting the loop at j = 0. Spot 0 is scored against itself. The same input returns 16.
Starting best at minus infinity in Best Time to Buy and Sell Stock (LC 121). A trade is optional there, so the answer is never negative. [7, 6, 4, 3, 1] returns -1 instead of 0. Start best at 0.
Copying the signs when the score rewards distance. For the score values[i] + values[j] + j - i, the left term is values[i] - i and the right term is values[j] + j. Read the signs from the formula, not from this card.

Practice

Canonical LeetCode:Best Sightseeing Pair (LC 1014)Best Time to Buy and Sell Stock (LC 121)Maximum Difference Between Increasing Elements (LC 2016)

Theory Context•Dynamic Programming

Builds on Linear DP, which you haven’t finished yet.

P2MediumBuilt on Linear DP~3 min speedrun

Best Left Half Carry (Best Sightseeing Pair)

Built on

Linear DPThe score of a pair splits into one term for the left spot and one term for the right spot, so one carried value, best_left, is the whole state.

The problem

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.

The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.

Example 1

Input:values = [8,1,5,2,6]

Output:11

Take the spots at positions 0 and 2. The score is 8 + 5 - 2 = 11. Every other pair scores less.

Best Sightseeing Pair

Python

1	def max_score_sightseeing_pair(values: list[int]) -> int:
2	"""Best Sightseeing Pair: carry the best left spot, values[i] + i, and score every spot j against it.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best_left: the largest values[i] + i over the spots before j; best: the largest pair score found so far
6	best_left = values[0]
7	best = float('-inf')
8	for j in range(1, len(values)):
9	# 1. Score Spot j As The Right End:
10	# The score is (values[i] + i) + (values[j] - j), so the best partner for j is the spot with the largest values[i] + i before j.
11	best = max(best, best_left + values[j] - j)
12
13	# 2. Update best_left With Spot j:
14	# This runs after the score, so spot j is never paired with itself.
15	best_left = max(best_left, values[j] + j)
16
17	return best

Invariant: Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j.

See it run

Best Sightseeing Pair, step by step

best_left 8best -inf

Each column is one spot, numbered from 0.

j the spot being scored
best_left the earlier spot with the largest values[i] + i

Start: best_left = values[0] + 0 = 8. Spot 0 is the only spot before spot 1.

8best_left

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Updating best_left with spot j before scoring j
Mistake
```
best_left = max(best_left, values[j] + j)
best = max(best, best_left + values[j] - j)
```
Fix
```
best = max(best, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
```
What happens: best_left must hold only the spots before j. When best_left is updated first, it already holds values[j] + j. The score then uses spot j at both ends of the pair. That score is (values[j] + j) + (values[j] - j), which is 2 * values[j]. At j = 4 in the example, the pair scores 12, which is 2 * 6, and no real pair scores that high.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 12Fix: returns 11
Gotcha 2: Carrying values[i] instead of values[i] + i
Mistake
```
best_left = max(best_left, values[j])
```
Fix
```
best_left = max(best_left, values[j] + j)
```
What happens: The distance is part of the left term. A spot nearer to j loses less, so the carried value must be values[i] + i. With only values[i], the four 1s in the example look equal and best_left stays 1. The pair of spots 3 and 4 is then scored as 1 + 9 - 4 = 6. Its real score is 1 + 9 - 1 = 9.
Example: values = [1, 1, 1, 1, 9]
Mistake: returns 6Fix: returns 9
Gotcha 3: Leaving out - j from the score
Mistake
```
best = max(best, best_left + values[j])
```
Fix
```
best = max(best, best_left + values[j] - j)
```
What happens: best_left holds values[i] + i. The + i is correct only when the right spot pays - j, because i - j is the negative distance. Without - j, the distance is never subtracted and the score is too large. In the example, the pair of spots 0 and 4 scores 8 + 6 = 14 instead of 8 + 6 - 4 = 10.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 14Fix: returns 11
Gotcha 4: Starting the loop at j = 0
Mistake
```
for j in range(0, len(values)):
```
Fix
```
for j in range(1, len(values)):
```
What happens: best_left starts as values[0], which is spot 0 as a left end. At j = 0, the loop scores spot 0 against that same spot: (8 + 0) + (8 - 0) = 16. A pair needs two different spots, so the loop starts at j = 1.
Example: Best Sightseeing Pair (LC 1014): values = [8, 1, 5, 2, 6]
Mistake: returns 16Fix: returns 11

Not this one if…

The score adds up every number between the two ends, as in Maximum Subarray (LC 53), instead of only the two end values and the distance between them, so the carried value is a running sum, not a best left end. See Kadane's Algorithm
You may buy and sell many times, as in Best Time to Buy and Sell Stock II (LC 122), so every day has a state (holding a share or not), not one best left end for a single pair. See State Machine DP
Every position needs the best value on its left and also the best value on its right, as in Trapping Rain Water (LC 42), so one pass from the left is not enough. See Prefix-Suffix Scan

Deep Dive

The observation: split the score into a left part and a right part

A pair of spots i < j scores values[i] + values[j] + i - j. Move the terms: the score is (values[i] + i) + (values[j] - j). The first bracket reads only i. The second bracket reads only j.

Example: values = [8, 1, 5, 2, 6], i = 0 and j = 2. The left part is 8 + 0 = 8. The right part is 5 - 2 = 3. The score is 8 + 3 = 11, which is the answer.

For a fixed j, the right part is one number. Only the left part changes with i. So the best partner of j is the spot i < j with the largest values[i] + i.

Example: for j = 4, the left parts of spots 0 to 3 are 8, 2, 7 and 5, and the right part is 6 - 4 = 2. The best left part is 8, so the best score that ends at spot 4 is 10.

Why one variable, `best_left`, is enough

At the start of the iteration for j, best_left is the largest values[i] + i over all i < j. This is a prefix maximum. One comparison per spot keeps it up to date, so no table is needed.

The brute force scores N * (N - 1) / 2 pairs. For N = 5 * 10⁴ that is 1,249,975,000 pairs. The loop reads each spot once.

What this card adds to Linear DP

Linear DP walks the array once and keeps the state in a few registers. This card keeps that single pass and that rolling register.

This is not Kadane's Algorithm. Kadane's state is the sum of one unbroken run. Here the numbers between i and j are not added. Only the two end values and the distance j - i count.

The order inside the loop, and the same idea with a minimum

Time is O(N), because the loop does constant work for each of the N - 1 spots. Space is O(1), because only best_left and best are kept.

60-Second Pitch

Common Questions

Why can the loop not keep the largest values[i] and fix the distance later?: The distance depends on which spot is chosen. A spot with a smaller value but a larger index i can lose less to the distance. The left term must be values[i] + i. For [1, 1, 1, 1, 9], the largest value alone gives 6, and the correct answer is 9.
How does the same loop solve Best Time to Buy and Sell Stock (LC 121)?: The profit is prices[j] - prices[i], so the left term is -prices[i] and the right term is prices[j]. best_left is the lowest price so far, negated. The positions are not part of the score, so there is no - j. A trade is optional, so best starts at 0.
How do you return the pair of spots and not only the score?: Keep the index of the spot that gave best_left, called left_index. When the score line improves best, save (left_index, j). When the update line improves best_left, set left_index = j. For [8, 1, 5, 2, 6], this returns the spots 0 and 2.
What changes when the score rewards distance, as in values[i] + values[j] + j - i?: The terms move to the other side. The left term is values[i] - i and the right term is values[j] + j. The loop keeps the same shape and the same order: score j first, then update best_left with j.
Can the time or the space be smaller?: The loop uses O(N) time and O(1) space. Every value must be read at least once, so no algorithm can take less than O(N) time. The space is already constant, because only best_left and best are kept.

SWE Reasoning

Spot it

The question asks for the best pair of positions i < j, not for a sum over a run of numbers.
The score adds a term that reads only i and a term that reads only j. The distance j - i splits into + i for the left spot and - j for the right spot.
The brute force scores all N * (N - 1) / 2 pairs. For N = 5 * 10⁴, that is about 1.25 * 10^9 pairs.
For a fixed j, only the left term changes with i, so the best i is a maximum over a prefix of the array.

The invariant, step by step

Before the loop, best_left = values[0] and best = float('-inf'). Spot 0 is the only spot before spot 1, and its left term is values[0] + 0.
At the start of the iteration for j, best_left is the largest values[i] + i over all i < j.
The score line sets best = max(best, best_left + values[j] - j). This is the best pair that ends at j.
The update line sets best_left = max(best_left, values[j] + j). It runs after the score line, so best_left still holds only the spots before j when j is scored. Afterwards it holds all spots up to j, which is what the iteration for j + 1 needs.
After the last j, every pair (i, j) was considered through its right end j. best is the largest score.
Trace for [8, 1, 5, 2, 6]: after j = 1, 2, 3, 4, best is 8, 11, 11, 11 and best_left is 8, 8, 8, 10. The answer is 11, from spots 0 and 2.

Traps

Updating best_left with j before scoring j. best_left already holds spot j, so j is paired with itself and scores 2 * values[j]. [8, 1, 5, 2, 6] returns 12 instead of 11.
Carrying values[i] without + i. The distance is lost from the left term. [1, 1, 1, 1, 9] returns 6 instead of 9.
Leaving out - j from the score. The distance is never subtracted. [8, 1, 5, 2, 6] returns 14 instead of 11.
Starting the loop at j = 0. Spot 0 is scored against itself. The same input returns 16.
Starting best at minus infinity in Best Time to Buy and Sell Stock (LC 121). A trade is optional there, so the answer is never negative. [7, 6, 4, 3, 1] returns -1 instead of 0. Start best at 0.
Copying the signs when the score rewards distance. For the score values[i] + values[j] + j - i, the left term is values[i] - i and the right term is values[j] + j. Read the signs from the formula, not from this card.

Practice

Canonical LeetCode:Best Sightseeing Pair (LC 1014)Best Time to Buy and Sell Stock (LC 121)Maximum Difference Between Increasing Elements (LC 2016)

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

Best Sightseeing Pair

See it run

Deep Dive

The observation: split the score into a left part and a right part

Why one variable, best_left, is enough

What this card adds to Linear DP

The order inside the loop, and the same idea with a minimum

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

Best Sightseeing Pair

See it run

Deep Dive

The observation: split the score into a left part and a right part

Why one variable, best_left, is enough

What this card adds to Linear DP

The order inside the loop, and the same idea with a minimum

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

Best Sightseeing Pair

See it run

Deep Dive

The observation: split the score into a left part and a right part

Why one variable, best_left, is enough

What this card adds to Linear DP

The order inside the loop, and the same idea with a minimum

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Best Sightseeing Pair (LC 1014)(opens leetcode.com)

Best Sightseeing Pair

See it run

Deep Dive

The observation: split the score into a left part and a right part

Why one variable, best_left, is enough

What this card adds to Linear DP

The order inside the loop, and the same idea with a minimum

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Why one variable, `best_left`, is enough

Why one variable, `best_left`, is enough

Why one variable, `best_left`, is enough

Why one variable, `best_left`, is enough