Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution.

---

Problem Explanation

You are given a string initialCurrency (the starting currency), along with four arrays:

1. pairs1 and rates1: Represent exchange rates between currency pairs on Day 1.

2. pairs2 and rates2: Represent exchange rates between currency pairs on Day 2.

The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates.

Key Insights:

1. Conversion rates are valid (no contradictions).

2. Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2.0, then EUR -> USD = 0.5).

---

Example Scenarios

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:

  • Day 1: Convert EUR -> USD (2.0 USD), then USD -> JPY (6.0 JPY).

  • Day 2: Convert JPY -> USD (24.0 USD), USD -> CHF (120.0 CHF), and CHF -> EUR (720.0 EUR).

Example 2:

• Input:

  initialCurrency = "NGN"
  pairs1 = [["NGN", "EUR"]]
  rates1 = [9.0]
  pairs2 = [["NGN", "EUR"]]
  rates2 = [6.0]

• Output: 1.50000

• Explanation: Convert NGN -> EUR on Day 1 and back to NGN on Day 2.

---

Approach 1: Brute Force

Algorithm:

1. Graph Representation: Build a graph for each day where nodes are currencies and edges are exchange rates.

2. Path Calculation: For each currency, calculate possible conversion paths for Day 1 and Day 2.

3. Exhaustive Search: Compute the maximum amount of initialCurrency through all possible conversions.

Limitations:

The brute force method involves recalculating paths multiple times, which becomes computationally expensive as the number of currencies grows.

---

Approach 2: Optimized Solution (Using Floyd-Warshall Algorithm)

To address the inefficiencies in the brute force approach, we use the Floyd-Warshall algorithm, which efficiently computes all-pairs maximum exchange rates.

Key Steps:

1. Graph Construction:

   • Build adjacency lists for both Day 1 and Day 2 graphs, where graph[from][to] = rate.

2. Floyd-Warshall Algorithm:

   • Update the graph to reflect the maximum possible rate between any two currencies via intermediate currencies.

3. Maximization:

   • Calculate all reachable amounts on Day 1 and use Day 2 graphs to determine the final maximum amount.

Code Implementation

C++ Solution:

#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    unordered_map<string, unordered_map<string, double>> buildGraph(vector<vector<string>>& pairs, vector<double>& rates) {
        unordered_map<string, unordered_map<string, double>> graph;
        for (int i = 0; i < pairs.size(); ++i) {
            string from = pairs[i][0], to = pairs[i][1];
            double rate = rates[i];
            graph[from][to] = rate;
            graph[to][from] = 1.0 / rate;
        }
        return graph;
    }

    unordered_map<string, unordered_map<string, double>> floydWarshall(unordered_map<string, unordered_map<string, double>>& graph) {
        vector<string> currencies;
        for (auto& pair : graph) currencies.push_back(pair.first);

        unordered_map<string, unordered_map<string, double>> dist;
        for (auto& from : currencies) {
            for (auto& to : currencies) {
                if (from == to) dist[from][to] = 1.0;
                else if (graph[from].count(to)) dist[from][to] = graph[from][to];
                else dist[from][to] = 0.0;
            }
        }

        for (auto& k : currencies) {
            for (auto& i : currencies) {
                for (auto& j : currencies) {
                    dist[i][j] = max(dist[i][j], dist[i][k] * dist[k][j]);
                }
            }
        }
        return dist;
    }

    double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
        auto graph1 = buildGraph(pairs1, rates1);
        auto graph2 = buildGraph(pairs2, rates2);
        auto day1Rates = floydWarshall(graph1);
        auto day2Rates = floydWarshall(graph2);

        unordered_map<string, double> day1Amounts;
        for (auto& currency : day1Rates) {
            if (day1Rates[initialCurrency].count(currency.first)) {
                day1Amounts[currency.first] = day1Rates[initialCurrency][currency.first];
            }
        }
        day1Amounts[initialCurrency] = 1.0;

        double maxAmount = 1.0;
        for (auto& [currency, amount] : day1Amounts) {
            if (day2Rates.count(currency)) {
                maxAmount = max(maxAmount, amount * day2Rates[currency][initialCurrency]);
            }
        }

        return maxAmount;
    }
};

---

Complexity Analysis

Time Complexity:

1. Graph Construction: O(n + m) for Day 1 and Day 2, where n and m are the number of currency pairs.

2. Floyd-Warshall: O(V^3) for each day, where V is the number of currencies.

3. Maximization: O(V) to evaluate all possible amounts.

Overall: O(V^3) for a typical case.

Space Complexity:

1. Graph Storage: O(V^2) to store rates.

2. Intermediate Distances: O(V^2).

Overall: O(V^2).

---

Tags for SEO

• Floyd-Warshall Algorithm

• Graph-based Problems

• Currency Conversion Optimization

• Dynamic Programming in Graphs

• Competitive Programming Solutions

---