Maximize amount after two days of conversions

Array String Depth-First Search Breadth-First Search Graph Theory

61.2% acceptance

Feb 24, 2026

158

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_amount(
    initial_currency: String,
    pairs1: Vec<Vec<String>>,
    rates1: Vec<f64>,
    pairs2: Vec<Vec<String>>,
    rates2: Vec<f64>,
  ) -> f64 {
    use std::collections::HashMap;
    
    // BFS/Bellman-Ford to find max reachable amount of each currency
    fn max_reachable(
      start: &str,
      pairs: &Vec<Vec<String>>,
      rates: &Vec<f64>,
    ) -> HashMap<String, f64> {
      let mut dist: HashMap<String, f64> = HashMap::new();
      dist.insert(start.to_string(), 1.0);
      
      // Build adjacency (bidirectional)
      let mut adj: HashMap<String, Vec<(String, f64)>> = HashMap::new();
      for (i, pair) in pairs.iter().enumerate() {
        let (a, b, r) = (&pair[0], &pair[1], rates[i]);
        adj.entry(a.clone()).or_default().push((b.clone(), r));
        adj.entry(b.clone()).or_default().push((a.clone(), 1.0 / r));
      }
      
      // Bellman-Ford style relaxation (maximize product)
      for _ in 0..pairs.len() + 1 {
        let keys: Vec<String> = dist.keys().cloned().collect();
        for cur in keys {
          let cur_val = dist[&cur];
          if let Some(neighbors) = adj.get(&cur) {
            for (nxt, rate) in neighbors {
              let new_val = cur_val * rate;
              let entry = dist.entry(nxt.clone()).or_insert(0.0);
              if new_val > *entry {
                *entry = new_val;
              }
            }
          }
        }
      }
      dist
    }
    
    let day1 = max_reachable(&initial_currency, &pairs1, &rates1);
    
    let mut ans = 1.0f64;
    
    // For each currency reachable on day 1, do day 2 conversions and find max of initial
    for (currency, amount) in &day1 {
      let day2 = max_reachable(currency, &pairs2, &rates2);
      if let Some(&back) = day2.get(&initial_currency) {
        let total = amount * back;
        if total > ans {
          ans = total;
        }
      }
      // Also: if initial_currency is not reachable from this currency, amount might still
      // be kept (we stay at this currency on day 2 with no conversion)
      // That case is handled when day2 contains initial_currency = 0 contribution
    }
    
    // Also consider: stay in initial_currency for day 1, then do day 2
    // (already included since day1 has initial_currency -> 1.0)
    
    ans
  }
}