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.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given n individuals at a base camp who need to cross a river to reach a destination using a single boat. The boat can carry at most k people at a time. The trip is affected by environmental conditions that vary cyclically over m stages.
Each stage j has a speed multiplier mul[j]:
mul[j] > 1, the trip slows down.mul[j] < 1, the trip speeds up.Each individual i has a rowing strength represented by time[i], the time (in minutes) it takes them to cross alone in neutral conditions.
Rules:
g departing at stage j takes time equal to the maximum time[i] among its members, multiplied by mul[j] minutes to reach the destination.d, the stage advances by floor(d) % m steps.r be the index of the returning person, the return takes time[r] × mul[current_stage], defined as return_time, and the stage advances by floor(return_time) % m.Return the minimum total time required to transport all individuals. If it is not possible to transport all individuals to the destination, return -1.
Example 1:
Input: n = 1, k = 1, m = 2, time = [5], mul = [1.0,1.3]
Output: 5.00000
Explanation:
5 × 1.00 = 5.00 minutes.5.00 minutes.Example 2:
Input: n = 3, k = 2, m = 3, time = [2,5,8], mul = [1.0,1.5,0.75]
Output: 14.50000
Explanation:
The optimal strategy is:
max(2, 8) × mul[0] = 8 × 1.00 = 8.00 minutes. The stage advances by floor(8.00) % 3 = 2, so the next stage is (0 + 2) % 3 = 2.2 × mul[2] = 2 × 0.75 = 1.50 minutes. The stage advances by floor(1.50) % 3 = 1, so the next stage is (2 + 1) % 3 = 0.max(2, 5) × mul[0] = 5 × 1.00 = 5.00 minutes. The stage advances by floor(5.00) % 3 = 2, so the final stage is (0 + 2) % 3 = 2.8.00 + 1.50 + 5.00 = 14.50 minutes.Example 3:
Input: n = 2, k = 1, m = 2, time = [10,10], mul = [2.0,2.0]
Output: -1.00000
Explanation:
-1.00.Constraints:
1 <= n == time.length <= 121 <= k <= 51 <= m <= 51 <= time[i] <= 100m == mul.length0.5 <= mul[i] <= 2.0Problem summary: You are given n individuals at a base camp who need to cross a river to reach a destination using a single boat. The boat can carry at most k people at a time. The trip is affected by environmental conditions that vary cyclically over m stages. Each stage j has a speed multiplier mul[j]: If mul[j] > 1, the trip slows down. If mul[j] < 1, the trip speeds up. Each individual i has a rowing strength represented by time[i], the time (in minutes) it takes them to cross alone in neutral conditions. Rules: A group g departing at stage j takes time equal to the maximum time[i] among its members, multiplied by mul[j] minutes to reach the destination. After the group crosses the river in time d, the stage advances by floor(d) % m steps. If individuals are left behind, one person must return with the boat. Let r be the index of the returning person, the return takes time[r] × mul[current_stage],
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Dynamic Programming · Bit Manipulation
1 1 2 [5] [1.0,1.3]
3 2 3 [2,5,8] [1.0,1.5,0.75]
2 1 2 [10,10] [2.0,2.0]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// package main
//
// import (
// "container/heap"
// "math"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// func minTime(n, k, m int, time []int, mul []float64) float64 {
// u := 1 << n
// // 计算每个 time 子集的最大值
// maxTime := make([]int, u)
// for i, t := range time {
// highBit := 1 << i
// for mask, mx := range maxTime[:highBit] {
// maxTime[highBit|mask] = max(mx, t)
// }
// }
// // 把 maxTime 中的大小大于 k 的集合改为 inf
// for i := range maxTime {
// if bits.OnesCount(uint(i)) > k {
// maxTime[i] = math.MaxInt
// }
// }
//
// dis := make([][][2]float64, m)
// for i := range dis {
// dis[i] = make([][2]float64, u)
// for j := range dis[i] {
// dis[i][j] = [2]float64{math.MaxFloat64, math.MaxFloat64}
// }
// }
// h := hp{}
// push := func(d float64, stage, mask int, direction uint8) {
// if d < dis[stage][mask][direction] {
// dis[stage][mask][direction] = d
// heap.Push(&h, tuple{d, stage, mask, direction})
// }
// }
//
// push(0, 0, u-1, 0) // 起点
//
// for len(h) > 0 {
// top := heap.Pop(&h).(tuple)
// d := top.dis
// stage := top.stage
// left := top.mask // 剩余没有过河的人
// direction := top.direction
// if left == 0 { // 所有人都过河了
// return d
// }
// if d > dis[stage][left][direction] {
// continue
// }
// if direction == 0 {
// // 枚举 sub 这群人坐一艘船
// for sub := left; sub > 0; sub = (sub - 1) & left {
// if maxTime[sub] != math.MaxInt {
// cost := float64(maxTime[sub]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^sub, 1)
// }
// }
// } else {
// // 枚举回来的人
// for s, lb := u-1^left, 0; s > 0; s ^= lb {
// lb = s & -s
// cost := float64(maxTime[lb]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^lb, 0)
// }
// }
// }
// return -1
// }
//
// type tuple struct {
// dis float64
// stage, mask int
// direction uint8 // 状态机：0 未过河，1 已过河
// }
// type hp []tuple
//
// func (h hp) Len() int { return len(h) }
// func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
// func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
// func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
// Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
package main
import (
"container/heap"
"math"
"math/bits"
)
// https://space.bilibili.com/206214
func minTime(n, k, m int, time []int, mul []float64) float64 {
u := 1 << n
// 计算每个 time 子集的最大值
maxTime := make([]int, u)
for i, t := range time {
highBit := 1 << i
for mask, mx := range maxTime[:highBit] {
maxTime[highBit|mask] = max(mx, t)
}
}
// 把 maxTime 中的大小大于 k 的集合改为 inf
for i := range maxTime {
if bits.OnesCount(uint(i)) > k {
maxTime[i] = math.MaxInt
}
}
dis := make([][][2]float64, m)
for i := range dis {
dis[i] = make([][2]float64, u)
for j := range dis[i] {
dis[i][j] = [2]float64{math.MaxFloat64, math.MaxFloat64}
}
}
h := hp{}
push := func(d float64, stage, mask int, direction uint8) {
if d < dis[stage][mask][direction] {
dis[stage][mask][direction] = d
heap.Push(&h, tuple{d, stage, mask, direction})
}
}
push(0, 0, u-1, 0) // 起点
for len(h) > 0 {
top := heap.Pop(&h).(tuple)
d := top.dis
stage := top.stage
left := top.mask // 剩余没有过河的人
direction := top.direction
if left == 0 { // 所有人都过河了
return d
}
if d > dis[stage][left][direction] {
continue
}
if direction == 0 {
// 枚举 sub 这群人坐一艘船
for sub := left; sub > 0; sub = (sub - 1) & left {
if maxTime[sub] != math.MaxInt {
cost := float64(maxTime[sub]) * mul[stage]
push(d+cost, (stage+int(cost))%m, left^sub, 1)
}
}
} else {
// 枚举回来的人
for s, lb := u-1^left, 0; s > 0; s ^= lb {
lb = s & -s
cost := float64(maxTime[lb]) * mul[stage]
push(d+cost, (stage+int(cost))%m, left^lb, 0)
}
}
}
return -1
}
type tuple struct {
dis float64
stage, mask int
direction uint8 // 状态机：0 未过河，1 已过河
}
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
# Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
#
# @lc app=leetcode id=3594 lang=python3
#
# [3594] Minimum Time to Transport All Individuals
#
# @lc code=start
import heapq
import math
from typing import List
class Solution:
def minTime(self, n: int, k: int, m: int, time: List[int], mul: List[float]) -> float:
# Sort time so that indices correspond to speed (lower index = faster/same)
# Actually, sorting helps us easily pick 'slowest' by picking largest indices.
time.sort()
# State: (mask, stage, boat_loc)
# mask: bitmask of people at Base
# stage: current stage index 0..m-1
# boat_loc: 0 for Base, 1 for Dest
# We map state (mask, stage, boat) to a linear index for the dist array
# Index = (mask * m + stage) * 2 + boat
size = (1 << n) * m * 2
dist = [float('inf')] * size
start_mask = (1 << n) - 1
start_idx = (start_mask * m + 0) * 2 + 0
dist[start_idx] = 0.0
# PQ stores (current_time, mask, stage, boat_loc)
pq = [(0.0, start_mask, 0, 0)]
while pq:
d, mask, stage, boat = heapq.heappop(pq)
curr_idx = (mask * m + stage) * 2 + boat
if d > dist[curr_idx]:
continue
# If everyone is at destination (mask 0) and boat is there (or doesn't matter, we are done)
# The problem implies we just need to transport everyone.
# However, the boat must end up at destination if the last trip was Base->Dest.
if mask == 0 and boat == 1:
return d
if boat == 0: # At Base, moving to Dest
# Indices of people currently at Base
at_base = [i for i in range(n) if (mask >> i) & 1]
next_states = {} # new_mask -> trip_cost
for idx_i, driver in enumerate(at_base):
driver_time = time[driver]
# Strategy 1: Driver + fill with slowest available people
# We pick people with indices < driver (which are faster or equal)
# but we prefer the largest indices among them (slowest among them)
# to clear 'hard' people from base.
riders_mask = 0
rem = k - 1
for idx_x in range(idx_i - 1, -1, -1):
if rem == 0: break
riders_mask |= (1 << at_base[idx_x])
rem -= 1
nm1 = mask ^ (1 << driver) ^ riders_mask
# Store/Update best cost for this mask
# Note: For a fixed mask transition, the driver is actually implicitly fixed
# (it must be the max time person removed), so cost is fixed.
next_states[nm1] = driver_time
if k > 1:
# Strategy 2: Driver + Specific Partner + fill with slowest
# We only need to try partners that were NOT included in Strategy 1.
# Strategy 1 includes indices at_base[idx_i-1 ... idx_i-(k-1)].
# So we check partners with index < idx_i - (k-1).
limit = idx_i - (k - 1)
if limit > 0:
for idx_j in range(limit):
partner = at_base[idx_j]
current_group_mask = (1 << driver) | (1 << partner)
# Fill remainder with slowest
rem2 = k - 2
riders_mask2 = 0
for idx_x in range(idx_i - 1, -1, -1):
if rem2 == 0: break
cand = at_base[idx_x]
if cand == partner: continue
riders_mask2 |= (1 << cand)
rem2 -= 1
nm2 = mask ^ current_group_mask ^ riders_mask2
next_states[nm2] = driver_time
# Process transitions
for nm, cost in next_states.items():
trip_time = cost * mul[stage]
new_time = d + trip_time
# Stage advances by floor(time)
new_stage = (stage + int(trip_time + 1e-9)) % m
idx = (nm * m + new_stage) * 2 + 1
if new_time < dist[idx]:
dist[idx] = new_time
heapq.heappush(pq, (new_time, nm, new_stage, 1))
else: # At Dest, returning to Base
# Indices of people currently at Dest (NOT in mask)
at_dest = [i for i in range(n) if not ((mask >> i) & 1)]
for r in at_dest:
return_time = time[r] * mul[stage]
new_time = d + return_time
new_stage = (stage + int(return_time + 1e-9)) % m
new_mask = mask | (1 << r)
idx = (new_mask * m + new_stage) * 2 + 0
if new_time < dist[idx]:
dist[idx] = new_time
heapq.heappush(pq, (new_time, new_mask, new_stage, 0))
return -1.0
# @lc code=end
// Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// package main
//
// import (
// "container/heap"
// "math"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// func minTime(n, k, m int, time []int, mul []float64) float64 {
// u := 1 << n
// // 计算每个 time 子集的最大值
// maxTime := make([]int, u)
// for i, t := range time {
// highBit := 1 << i
// for mask, mx := range maxTime[:highBit] {
// maxTime[highBit|mask] = max(mx, t)
// }
// }
// // 把 maxTime 中的大小大于 k 的集合改为 inf
// for i := range maxTime {
// if bits.OnesCount(uint(i)) > k {
// maxTime[i] = math.MaxInt
// }
// }
//
// dis := make([][][2]float64, m)
// for i := range dis {
// dis[i] = make([][2]float64, u)
// for j := range dis[i] {
// dis[i][j] = [2]float64{math.MaxFloat64, math.MaxFloat64}
// }
// }
// h := hp{}
// push := func(d float64, stage, mask int, direction uint8) {
// if d < dis[stage][mask][direction] {
// dis[stage][mask][direction] = d
// heap.Push(&h, tuple{d, stage, mask, direction})
// }
// }
//
// push(0, 0, u-1, 0) // 起点
//
// for len(h) > 0 {
// top := heap.Pop(&h).(tuple)
// d := top.dis
// stage := top.stage
// left := top.mask // 剩余没有过河的人
// direction := top.direction
// if left == 0 { // 所有人都过河了
// return d
// }
// if d > dis[stage][left][direction] {
// continue
// }
// if direction == 0 {
// // 枚举 sub 这群人坐一艘船
// for sub := left; sub > 0; sub = (sub - 1) & left {
// if maxTime[sub] != math.MaxInt {
// cost := float64(maxTime[sub]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^sub, 1)
// }
// }
// } else {
// // 枚举回来的人
// for s, lb := u-1^left, 0; s > 0; s ^= lb {
// lb = s & -s
// cost := float64(maxTime[lb]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^lb, 0)
// }
// }
// }
// return -1
// }
//
// type tuple struct {
// dis float64
// stage, mask int
// direction uint8 // 状态机：0 未过河，1 已过河
// }
// type hp []tuple
//
// func (h hp) Len() int { return len(h) }
// func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
// func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
// func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
// Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3594: Minimum Time to Transport All Individuals
// package main
//
// import (
// "container/heap"
// "math"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// func minTime(n, k, m int, time []int, mul []float64) float64 {
// u := 1 << n
// // 计算每个 time 子集的最大值
// maxTime := make([]int, u)
// for i, t := range time {
// highBit := 1 << i
// for mask, mx := range maxTime[:highBit] {
// maxTime[highBit|mask] = max(mx, t)
// }
// }
// // 把 maxTime 中的大小大于 k 的集合改为 inf
// for i := range maxTime {
// if bits.OnesCount(uint(i)) > k {
// maxTime[i] = math.MaxInt
// }
// }
//
// dis := make([][][2]float64, m)
// for i := range dis {
// dis[i] = make([][2]float64, u)
// for j := range dis[i] {
// dis[i][j] = [2]float64{math.MaxFloat64, math.MaxFloat64}
// }
// }
// h := hp{}
// push := func(d float64, stage, mask int, direction uint8) {
// if d < dis[stage][mask][direction] {
// dis[stage][mask][direction] = d
// heap.Push(&h, tuple{d, stage, mask, direction})
// }
// }
//
// push(0, 0, u-1, 0) // 起点
//
// for len(h) > 0 {
// top := heap.Pop(&h).(tuple)
// d := top.dis
// stage := top.stage
// left := top.mask // 剩余没有过河的人
// direction := top.direction
// if left == 0 { // 所有人都过河了
// return d
// }
// if d > dis[stage][left][direction] {
// continue
// }
// if direction == 0 {
// // 枚举 sub 这群人坐一艘船
// for sub := left; sub > 0; sub = (sub - 1) & left {
// if maxTime[sub] != math.MaxInt {
// cost := float64(maxTime[sub]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^sub, 1)
// }
// }
// } else {
// // 枚举回来的人
// for s, lb := u-1^left, 0; s > 0; s ^= lb {
// lb = s & -s
// cost := float64(maxTime[lb]) * mul[stage]
// push(d+cost, (stage+int(cost))%m, left^lb, 0)
// }
// }
// }
// return -1
// }
//
// type tuple struct {
// dis float64
// stage, mask int
// direction uint8 // 状态机：0 未过河，1 已过河
// }
// type hp []tuple
//
// func (h hp) Len() int { return len(h) }
// func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
// func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
// func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
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.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.