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.
Move from brute-force thinking to an efficient approach using array strategy.
You are given a string initialCurrency, and you start with 1.0 of initialCurrency.
You are also given four arrays with currency pairs (strings) and rates (real numbers):
pairs1[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates1[i] on day 1.pairs2[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates2[i] on day 2.targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / rate.You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.
Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.
Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.
Example 1:
Input: initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]
Output: 720.00000
Explanation:
To get the maximum amount of EUR, starting with 1.0 EUR:
Example 2:
Input: initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]
Output: 1.50000
Explanation:
Converting NGN to EUR on day 1 and EUR to NGN using the inverse rate on day 2 gives the maximum amount.
Example 3:
Input: initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]
Output: 1.00000
Explanation:
In this example, there is no need to make any conversions on either day.
Constraints:
1 <= initialCurrency.length <= 3initialCurrency consists only of uppercase English letters.1 <= n == pairs1.length <= 101 <= m == pairs2.length <= 10pairs1[i] == [startCurrencyi, targetCurrencyi]pairs2[i] == [startCurrencyi, targetCurrencyi]1 <= startCurrencyi.length, targetCurrencyi.length <= 3startCurrencyi and targetCurrencyi consist only of uppercase English letters.rates1.length == nrates2.length == m1.0 <= rates1[i], rates2[i] <= 10.05 * 1010.Problem summary: You are given a string initialCurrency, and you start with 1.0 of initialCurrency. You are also given four arrays with currency pairs (strings) and rates (real numbers): pairs1[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates1[i] on day 1. pairs2[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates2[i] on day 2. Also, each targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / rate. You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2. Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order. Note: Conversion rates are valid,
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
"EUR" [["EUR","USD"],["USD","JPY"]] [2.0,3.0] [["JPY","USD"],["USD","CHF"],["CHF","EUR"]] [4.0,5.0,6.0]
"NGN" [["NGN","EUR"]] [9.0] [["NGN","EUR"]] [6.0]
"USD" [["USD","EUR"]] [1.0] [["EUR","JPY"]] [10.0]
evaluate-division)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
class Solution {
public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1,
List<List<String>> pairs2, double[] rates2) {
Map<String, Double> d1 = build(pairs1, rates1, initialCurrency);
Map<String, Double> d2 = build(pairs2, rates2, initialCurrency);
double ans = 0;
for (Map.Entry<String, Double> entry : d2.entrySet()) {
String currency = entry.getKey();
double rate = entry.getValue();
if (d1.containsKey(currency)) {
ans = Math.max(ans, d1.get(currency) / rate);
}
}
return ans;
}
private Map<String, Double> build(List<List<String>> pairs, double[] rates, String init) {
Map<String, List<Pair<String, Double>>> g = new HashMap<>();
Map<String, Double> d = new HashMap<>();
for (int i = 0; i < pairs.size(); ++i) {
String a = pairs.get(i).get(0);
String b = pairs.get(i).get(1);
double r = rates[i];
g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Pair<>(b, r));
g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Pair<>(a, 1 / r));
}
dfs(g, d, init, 1.0);
return d;
}
private void dfs(
Map<String, List<Pair<String, Double>>> g, Map<String, Double> d, String a, double v) {
if (d.containsKey(a)) {
return;
}
d.put(a, v);
for (Pair<String, Double> pair : g.getOrDefault(a, List.of())) {
String b = pair.getKey();
double r = pair.getValue();
if (!d.containsKey(b)) {
dfs(g, d, b, v * r);
}
}
}
}
// Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
type Pair struct {
Key string
Value float64
}
func maxAmount(initialCurrency string, pairs1 [][]string, rates1 []float64, pairs2 [][]string, rates2 []float64) (ans float64) {
d1 := build(pairs1, rates1, initialCurrency)
d2 := build(pairs2, rates2, initialCurrency)
for currency, rate := range d2 {
if val, found := d1[currency]; found {
ans = max(ans, val/rate)
}
}
return
}
func build(pairs [][]string, rates []float64, init string) map[string]float64 {
g := make(map[string][]Pair)
d := make(map[string]float64)
for i := 0; i < len(pairs); i++ {
a := pairs[i][0]
b := pairs[i][1]
r := rates[i]
g[a] = append(g[a], Pair{Key: b, Value: r})
g[b] = append(g[b], Pair{Key: a, Value: 1.0 / r})
}
dfs(g, d, init, 1.0)
return d
}
func dfs(g map[string][]Pair, d map[string]float64, a string, v float64) {
if _, found := d[a]; found {
return
}
d[a] = v
for _, pair := range g[a] {
b := pair.Key
r := pair.Value
if _, found := d[b]; !found {
dfs(g, d, b, v*r)
}
}
}
# Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
class Solution:
def maxAmount(
self,
initialCurrency: str,
pairs1: List[List[str]],
rates1: List[float],
pairs2: List[List[str]],
rates2: List[float],
) -> float:
d1 = self.build(pairs1, rates1, initialCurrency)
d2 = self.build(pairs2, rates2, initialCurrency)
return max(d1.get(a, 0) / r2 for a, r2 in d2.items())
def build(
self, pairs: List[List[str]], rates: List[float], init: str
) -> Dict[str, float]:
def dfs(a: str, v: float):
d[a] = v
for b, r in g[a]:
if b not in d:
dfs(b, v * r)
g = defaultdict(list)
for (a, b), r in zip(pairs, rates):
g[a].append((b, r))
g[b].append((a, 1 / r))
d = {}
dfs(init, 1)
return d
// Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
// Rust example auto-generated from java 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 (java):
// // Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
// class Solution {
// public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1,
// List<List<String>> pairs2, double[] rates2) {
// Map<String, Double> d1 = build(pairs1, rates1, initialCurrency);
// Map<String, Double> d2 = build(pairs2, rates2, initialCurrency);
// double ans = 0;
// for (Map.Entry<String, Double> entry : d2.entrySet()) {
// String currency = entry.getKey();
// double rate = entry.getValue();
// if (d1.containsKey(currency)) {
// ans = Math.max(ans, d1.get(currency) / rate);
// }
// }
// return ans;
// }
//
// private Map<String, Double> build(List<List<String>> pairs, double[] rates, String init) {
// Map<String, List<Pair<String, Double>>> g = new HashMap<>();
// Map<String, Double> d = new HashMap<>();
// for (int i = 0; i < pairs.size(); ++i) {
// String a = pairs.get(i).get(0);
// String b = pairs.get(i).get(1);
// double r = rates[i];
// g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Pair<>(b, r));
// g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Pair<>(a, 1 / r));
// }
// dfs(g, d, init, 1.0);
// return d;
// }
//
// private void dfs(
// Map<String, List<Pair<String, Double>>> g, Map<String, Double> d, String a, double v) {
// if (d.containsKey(a)) {
// return;
// }
//
// d.put(a, v);
// for (Pair<String, Double> pair : g.getOrDefault(a, List.of())) {
// String b = pair.getKey();
// double r = pair.getValue();
// if (!d.containsKey(b)) {
// dfs(g, d, b, v * r);
// }
// }
// }
// }
// Accepted solution for LeetCode #3387: Maximize Amount After Two Days of Conversions
class Pair {
constructor(
public key: string,
public value: number,
) {}
}
function maxAmount(
initialCurrency: string,
pairs1: string[][],
rates1: number[],
pairs2: string[][],
rates2: number[],
): number {
const d1 = build(pairs1, rates1, initialCurrency);
const d2 = build(pairs2, rates2, initialCurrency);
let ans = 0;
for (const [currency, rate] of Object.entries(d2)) {
if (currency in d1) {
ans = Math.max(ans, d1[currency] / rate);
}
}
return ans;
}
function build(pairs: string[][], rates: number[], init: string): { [key: string]: number } {
const g: { [key: string]: Pair[] } = {};
const d: { [key: string]: number } = {};
for (let i = 0; i < pairs.length; ++i) {
const a = pairs[i][0];
const b = pairs[i][1];
const r = rates[i];
if (!g[a]) g[a] = [];
if (!g[b]) g[b] = [];
g[a].push(new Pair(b, r));
g[b].push(new Pair(a, 1 / r));
}
dfs(g, d, init, 1.0);
return d;
}
function dfs(
g: { [key: string]: Pair[] },
d: { [key: string]: number },
a: string,
v: number,
): void {
if (a in d) {
return;
}
d[a] = v;
for (const pair of g[a] || []) {
const b = pair.key;
const r = pair.value;
if (!(b in d)) {
dfs(g, d, b, v * r);
}
}
}
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.