Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
You are given an integer array cost of size n. You are currently at position n (at the end of the line) in a line of n + 1 people (numbered from 0 to n).
You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person i is given by cost[i].
You are allowed to swap places with people as follows:
cost[i] to swap with them.Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.
Example 1:
Input: cost = [5,3,4,1,3,2]
Output: [5,3,3,1,1,1]
Explanation:
We can get to each position in the following way:
i = 0. We can swap with person 0 for a cost of 5.i = 1. We can swap with person 1 for a cost of 3.i = 2. We can swap with person 1 for a cost of 3, then swap with person 2 for free.i = 3. We can swap with person 3 for a cost of 1.i = 4. We can swap with person 3 for a cost of 1, then swap with person 4 for free.i = 5. We can swap with person 3 for a cost of 1, then swap with person 5 for free.Example 2:
Input: cost = [1,2,4,6,7]
Output: [1,1,1,1,1]
Explanation:
We can swap with person 0 for a cost of 1, then we will be able to reach any position i for free.
Constraints:
1 <= n == cost.length <= 1001 <= cost[i] <= 100Problem summary: You are given an integer array cost of size n. You are currently at position n (at the end of the line) in a line of n + 1 people (numbered from 0 to n). You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person i is given by cost[i]. You are allowed to swap places with people as follows: If they are in front of you, you must pay them cost[i] to swap with them. If they are behind you, they can swap with you for free. Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[5,3,4,1,3,2]
[1,2,4,6,7]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3502: Minimum Cost to Reach Every Position
class Solution {
public int[] minCosts(int[] cost) {
int n = cost.length;
int[] ans = new int[n];
int mi = cost[0];
for (int i = 0; i < n; ++i) {
mi = Math.min(mi, cost[i]);
ans[i] = mi;
}
return ans;
}
}
// Accepted solution for LeetCode #3502: Minimum Cost to Reach Every Position
func minCosts(cost []int) []int {
n := len(cost)
ans := make([]int, n)
mi := cost[0]
for i, c := range cost {
mi = min(mi, c)
ans[i] = mi
}
return ans
}
# Accepted solution for LeetCode #3502: Minimum Cost to Reach Every Position
class Solution:
def minCosts(self, cost: List[int]) -> List[int]:
n = len(cost)
ans = [0] * n
mi = cost[0]
for i, c in enumerate(cost):
mi = min(mi, c)
ans[i] = mi
return ans
// Accepted solution for LeetCode #3502: Minimum Cost to Reach Every Position
fn min_costs(cost: Vec<i32>) -> Vec<i32> {
let mut ret = vec![];
let mut min_cost = cost[0];
for c in cost {
min_cost = std::cmp::min(min_cost, c);
ret.push(min_cost);
}
ret
}
fn main() {
let cost = vec![5, 3, 4, 1, 3, 2];
let ret = min_costs(cost);
println!("ret={ret:?}");
}
#[test]
fn test() {
{
let cost = vec![5, 3, 4, 1, 3, 2];
let expected = vec![5, 3, 3, 1, 1, 1];
let ret = min_costs(cost);
assert_eq!(ret, expected);
}
{
let cost = vec![1, 2, 4, 6, 7];
let expected = vec![1, 1, 1, 1, 1];
let ret = min_costs(cost);
assert_eq!(ret, expected);
}
}
// Accepted solution for LeetCode #3502: Minimum Cost to Reach Every Position
function minCosts(cost: number[]): number[] {
const n = cost.length;
const ans: number[] = Array(n).fill(0);
let mi = cost[0];
for (let i = 0; i < n; ++i) {
mi = Math.min(mi, cost[i]);
ans[i] = mi;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.