Facebook Pixel

3387. Maximize Amount After Two Days of Conversions

MediumDepth-First SearchBreadth-First SearchGraphArrayString
Leetcode Link

Problem Description

You are given a string initialCurrency, and you start with 1.0 of initialCurrency. Additionally, you have two sets of currency pairs and exchange rates for two successive days:

  • pairs1[i] = [startCurrency_i, targetCurrency_i] indicates that you can convert startCurrency_i to targetCurrency_i at a rate of rates1[i] on day 1.
  • pairs2[i] = [startCurrency_i, targetCurrency_i] indicates that you can convert startCurrency_i to targetCurrency_i at a rate of rates2[i] on day 2.

Each targetCurrency can be converted back to its corresponding startCurrency at an inverse rate of 1 / rate. You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of conversions, including zero, using rates2 on day 2.

The task is to determine the maximum amount of initialCurrency you can obtain after performing conversions on both days in order.

Intuition

The problem essentially boils down to finding the best possible conversion strategy across two days to maximize the amount of the initialCurrency. This can be thought of like finding the optimal routes through a graph where nodes represent currencies and edges represent conversion rates.

To undertake this, the solution constructs two distinct graphs for both days using the given currency pairs and rates. Then, a Depth First Search (DFS) is performed on these graphs starting from the initialCurrency to compute the maximum possible conversion amounts attainable on each day.

  • Day 1 Processing: Build a graph using pairs1 and rates1, perform DFS starting from initialCurrency to evaluate all the possible conversions, and store the maximum conversion possibilities.

  • Day 2 Processing: Similarly, construct another graph using pairs2 and rates2, perform DFS, and evaluate all potential gains stemming from the endpoint of the maximum conversions achievable with the first graph.

The ultimate goal is to assess all possible currency gains by carrying forward the result of conversions from day 1 to day 2 for a complete evaluation of optimal conversions over the two days, returning the maximum value of initialCurrency achievable as the result.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution to this problem involves constructing currency conversion graphs from the given pairs and rates for each day and evaluating the maximum amount of initialCurrency obtainable through depth-first search (DFS). Here's a breakdown of the implementation:

  1. Graph Construction:

    • For each day, create a graph where nodes represent currencies and edges correspond to conversion rates. This is done using a dictionary where each key is a currency and the value is a list of tuples, with each tuple containing a target currency and the conversion rate.
    • For pairs1 and rates1, graph g1 is built. Similarly, p2 and rates2 are utilized to build graph g2.

  2. Depth First Search (DFS):

    • Perform a DFS starting from initialCurrency in order to calculate the maximum amount achievable for each currency. This process is conducted independently on each daily graph. The DFS is initiated with a value of 1.0 since you begin with one unit of the initialCurrency.
    • The DFS traverses all possible conversions, updating a dictionary d that maintains the maximum amount of each currency found during the traversal.
    • For each starting node (currency), explore all reachable currencies, multiplying the accumulated value by the conversion rate as you move to the next node.

  3. Calculate Maximum Result:

    • After processing both days, you will have two dictionaries (d1 and d2) representing the maximum amounts of all currencies achievable at the end of each day.
    • For each achievable currency on day 1 stored in d1, check how it can be further converted on day 2 using d2. The key consideration here is multiplying the results from day 1 by possible additional conversion rates.
    • The final step involves selecting the maximum value achievable of the initialCurrency returned after potentially converting through these optimal paths across both days.

The core implementation of the above steps is represented as follows in the code:

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to better understand the solution approach.

Example Details:

Assume we have an initial currency USD and the following conversion pairs and rates for two days:

  • Day 1:

    • pairs1 = [["USD", "EUR"], ["EUR", "GBP"]]
    • rates1 = [0.9, 1.2]

  • Day 2:

    • pairs2 = [["EUR", "JPY"], ["GBP", "CHF"]]
    • rates2 = [1.1, 0.8]

Day 1 Processing:

  1. Graph Construction:
    For day 1, we build a graph g1:

    • USD -> EUR with rate 0.9
    • EUR -> GBP with rate 1.2
    • These also imply inverse conversions: EUR -> USD at 1/0.9 ≈ 1.11 and GBP -> EUR at 1/1.2 ≈ 0.83.

  2. Depth First Search (DFS):
    Start DFS from USD with value 1.0.

    • Convert USD -> EUR: 1.0 * 0.9 = 0.9 EUR
    • Convert EUR -> GBP: 0.9 * 1.2 = 1.08 GBP
    • We now have d1 = {"USD": 1.0, "EUR": 0.9, "GBP": 1.08} representing the maximum amount achievable in each currency at the end of day 1.

Day 2 Processing:

  1. Graph Construction:
    For day 2, we build a graph g2:

    • EUR -> JPY with rate 1.1
    • GBP -> CHF with rate 0.8
    • Also, JPY -> EUR at 1/1.1 ≈ 0.91 and CHF -> GBP at 1/0.8 = 1.25.

  2. Depth First Search (DFS):
    Start DFS from USD aiming to maximize currencies starting from d1 outcomes.

    • For EUR available from day 1, convert EUR -> JPY: 0.9 * 1.1 = 0.99 JPY
    • For GBP available from day 1, convert GBP -> CHF: 1.08 * 0.8 = 0.864 CHF
    • We now have d2 = {"EUR": 0.99, "JPY": 0.99, "GBP": 0.864, "CHF": 0.864} at the end of day 2.

Calculate Maximum Result:

  • Evaluate the optimal conversion paths:
    • From day 1 d1["USD"] = 1.0, no improvement possible.
    • Use day 1 EUR to obtain 0.99 JPY on day 2.
    • Use day 1 GBP to obtain 0.864 CHF on day 2.

After examining all routes, the maximum amount of USD after potential conversions is retained directly or derived through indirect paths, as recorded across both days.

Ultimately, in this particular example, the progression reveals that maintaining the initial currency retains the maximum amount, given the opportunities and rates provided.

Solution Implementation

1from typing import List, Dict
2from collections import defaultdict
3
4class Solution:
5    def maxAmount(
6        self,
7        initialCurrency: str,
8        pairs1: List[List[str]],
9        rates1: List[float],
10        pairs2: List[List[str]],
11        rates2: List[float],
12    ) -> float:
13        # Build dictionaries of exchange rates starting from the initial currency for both sets of pairs and rates
14        dict1 = self.build(pairs1, rates1, initialCurrency)
15        dict2 = self.build(pairs2, rates2, initialCurrency)
16
17        # Calculate the maximum amount by comparing currencies in both dictionaries
18        return max(dict1.get(currency, 0) / rate2 for currency, rate2 in dict2.items())
19
20    def build(
21        self, pairs: List[List[str]], rates: List[float], init: str
22    ) -> Dict[str, float]:
23        # Depth-first search (DFS) to compute the value of all currencies starting from the initial currency
24        def dfs(currency: str, value: float):
25            # Set the current value for this currency
26            currency_values[currency] = value
27            # Explore adjacent currencies
28            for neighbor, rate in graph[currency]:
29                if neighbor not in currency_values:
30                    dfs(neighbor, value * rate)
31
32        # Build the exchange graph using a defaultdict with lists
33        graph = defaultdict(list)
34        for (a, b), rate in zip(pairs, rates):
35            # Add both directions for each currency pair
36            graph[a].append((b, rate))
37            graph[b].append((a, 1 / rate))  # Reverse direction with reciprocal rate
38
39        # Dictionary to store the computed currency values from the initial currency
40        currency_values = {}
41
42        # Start DFS from the initial currency with a starting value of 1
43        dfs(init, 1)
44      
45        return currency_values
46
1import java.util.*;
2
3class Solution {
4    public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1,
5            List<List<String>> pairs2, double[] rates2) {
6
7        // Build exchange rate maps based on the given pairs and rates for both sets
8        Map<String, Double> exchangeRates1 = build(pairs1, rates1, initialCurrency);
9        Map<String, Double> exchangeRates2 = build(pairs2, rates2, initialCurrency);
10
11        double maximumAmount = 0;
12
13        // Iterate over the second set of exchange rates
14        for (Map.Entry<String, Double> entry : exchangeRates2.entrySet()) {
15            String currency = entry.getKey();
16            double rate = entry.getValue();
17          
18            // If the currency is available in the first set, calculate possible max amount
19            if (exchangeRates1.containsKey(currency)) {
20                maximumAmount = Math.max(maximumAmount, exchangeRates1.get(currency) / rate);
21            }
22        }
23
24        return maximumAmount;
25    }
26
27    private Map<String, Double> build(List<List<String>> pairs, double[] rates, String initial) {
28        Map<String, List<Pair<String, Double>>> graph = new HashMap<>();
29        Map<String, Double> distance = new HashMap<>();
30
31        // Construct the graph using the given currency pairs and their rates
32        for (int i = 0; i < pairs.size(); ++i) {
33            String currencyA = pairs.get(i).get(0);
34            String currencyB = pairs.get(i).get(1);
35            double rate = rates[i];
36          
37            // Add the direct conversion and its reciprocal to the graph
38            graph.computeIfAbsent(currencyA, k -> new ArrayList<>()).add(new Pair<>(currencyB, rate));
39            graph.computeIfAbsent(currencyB, k -> new ArrayList<>()).add(new Pair<>(currencyA, 1 / rate));
40        }
41      
42        // Perform depth-first search starting from the initial currency
43        dfs(graph, distance, initial, 1.0);
44        return distance;
45    }
46
47    private void dfs(Map<String, List<Pair<String, Double>>> graph, Map<String, Double> distance, 
48            String currentCurrency, double value) {
49
50        // If we've already computed the distance for this currency, exit early
51        if (distance.containsKey(currentCurrency)) {
52            return;
53        }
54
55        distance.put(currentCurrency, value);
56
57        // Recursively visit all connected currencies
58        for (Pair<String, Double> pair : graph.getOrDefault(currentCurrency, List.of())) {
59            String nextCurrency = pair.getKey();
60            double conversionRate = pair.getValue();
61
62            // Visit the next currency if not already processed
63            if (!distance.containsKey(nextCurrency)) {
64                dfs(graph, distance, nextCurrency, value * conversionRate);
65            }
66        }
67    }
68}
69
70// A simple Pair class to hold two correlated objects together
71class Pair<K, V> {
72    private K key;
73    private V value;
74
75    public Pair(K key, V value) {
76        this.key = key;
77        this.value = value;
78    }
79
80    public K getKey() {
81        return key;
82    }
83
84    public V getValue() {
85        return value;
86    }
87}
88
1#include <unordered_map>
2#include <vector>
3#include <string>
4#include <utility>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10public:
11    // Function to calculate the maximum amount achievable starting from initialCurrency
12    // using provided exchange pairs and rates.
13    double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, 
14                     vector<vector<string>>& pairs2, vector<double>& rates2) {
15
16        // Build the exchange rate map from first set of pairs and rates
17        unordered_map<string, double> d1 = build(pairs1, rates1, initialCurrency);
18      
19        // Build the exchange rate map from second set of pairs and rates
20        unordered_map<string, double> d2 = build(pairs2, rates2, initialCurrency);
21      
22        double ans = 0.0;
23        // Traverse the built map d2 to find the maximum achievable amount
24        for (const auto& [currency, rate] : d2) {
25            if (d1.find(currency) != d1.end()) {
26                // Update the answer with the maximum value found
27                ans = max(ans, d1[currency] / rate);
28            }
29        }
30      
31        return ans;
32    }
33
34private:
35    // Helper function to build the exchange rate map using DFS
36    unordered_map<string, double> build(vector<vector<string>>& pairs, vector<double>& rates, 
37                                        const string& init) {
38        unordered_map<string, vector<pair<string, double>>> graph;
39        unordered_map<string, double> distance;
40      
41        // Populate the graph with bidirectional exchange rates
42        for (int i = 0; i < pairs.size(); ++i) {
43            const string& fromCurrency = pairs[i][0];
44            const string& toCurrency = pairs[i][1];
45            double rate = rates[i];
46          
47            graph[fromCurrency].emplace_back(toCurrency, rate);
48            graph[toCurrency].emplace_back(fromCurrency, 1.0 / rate);
49        }
50
51        // Recursive lambda function for DFS traversal
52        auto dfs = [&](auto&& self, const string& currency, double value) -> void {
53            // If the currency conversion value is already set, skip
54            if (distance.find(currency) != distance.end()) {
55                return;
56            }
57
58            // Set the conversion rate for the currency
59            distance[currency] = value;
60
61            // Recursively visit all connected currencies
62            for (const auto& [nextCurrency, nextRate] : graph[currency]) {
63                if (distance.find(nextCurrency) == distance.end()) {
64                    self(self, nextCurrency, value * nextRate);
65                }
66            }
67        };
68      
69        // Start DFS from the initial currency with conversion rate 1
70        dfs(dfs, init, 1.0);
71      
72        return distance;
73    }
74};
75
1// Represents a currency and its exchange rate
2interface Pair {
3    key: string;
4    value: number;
5}
6
7// Finds the maximum amount of the initial currency that can be obtained
8function maxAmount(
9    initialCurrency: string,
10    pairs1: string[][],
11    rates1: number[],
12    pairs2: string[][],
13    rates2: number[]
14): number {
15    // Build currency conversion rates from the first set of pairs and rates
16    const d1 = build(pairs1, rates1, initialCurrency);
17    // Build currency conversion rates from the second set of pairs and rates
18    const d2 = build(pairs2, rates2, initialCurrency);
19    let ans = 0;
20    // Calculate the maximum amount of initial currency possible
21    for (const [currency, rate] of Object.entries(d2)) {
22        if (currency in d1) {
23            ans = Math.max(ans, d1[currency] / rate);
24        }
25    }
26    return ans;
27}
28
29// Constructs a map of currencies to their conversion rates from a given initial currency
30function build(pairs: string[][], rates: number[], init: string): { [key: string]: number } {
31    const graph: { [key: string]: Pair[] } = {}; // Graph representation of currency relations
32    const distance: { [key: string]: number } = {}; // Stores the conversion rate from initial currency
33
34    // Build the graph with exchange rates for each pair
35    for (let i = 0; i < pairs.length; ++i) {
36        const a = pairs[i][0];
37        const b = pairs[i][1];
38        const rate = rates[i];
39
40        // Initialize graph nodes if they do not already exist
41        if (!graph[a]) graph[a] = [];
42        if (!graph[b]) graph[b] = [];
43
44        // Each edge is represented both ways to allow conversion in both directions
45        graph[a].push({ key: b, value: rate });
46        graph[b].push({ key: a, value: 1 / rate });
47    }
48
49    // Use DFS to find the conversion rate of each currency from the initial currency
50    dfs(graph, distance, init, 1.0);
51
52    return distance;
53}
54
55// Depth-first search to traverse and set exchange rates starting from the initial node
56function dfs(
57    graph: { [key: string]: Pair[] },
58    distance: { [key: string]: number },
59    currency: string,
60    rate: number
61): void {
62    // If the currency has already been visited, return
63    if (currency in distance) {
64        return;
65    }
66
67    // Set the conversion rate for this currency
68    distance[currency] = rate;
69
70    // Traverse neighbors (connected currencies)
71    for (const pair of graph[currency] || []) {
72        const nextCurrency = pair.key;
73        const exchangeRate = pair.value;
74
75        // Recursively perform DFS if the currency hasn't been visited
76        if (!(nextCurrency in distance)) {
77            dfs(graph, distance, nextCurrency, rate * exchangeRate);
78        }
79    }
80}
81

Time and Space Complexity

The code provided implements a solution to find the maximum amount of currency that can be obtained starting from an initialCurrency using two different sets of currency pairs and their corresponding exchange rates.

Time Complexity

The main components of the algorithm are:

  1. Graph Construction: For each pair of currencies given in pairs1 and pairs2, the code constructs a graph by iterating through the pairs once. This has a time complexity of O(N + M), where N is the number of pairs in pairs1 and M in pairs2.

  2. Depth-First Search (DFS): Each DFS traversal starting from the initialCurrency visits each node (currency) and edge (exchange rate) in the respective graph exactly once. Thus, the DFS traversal for pairs1 and pairs2 each takes O(N + M).

Overall, the time complexity of the solution is O(N + M) for building the graph and performing DFS on both pairs1 and pairs2.

Space Complexity

The space requirements primarily come from storing the graph and the visited nodes dictionary.

  1. Graph Storage: Using a graph representation with an adjacency list requires storing each currency pair and their corresponding rates. Hence, the space complexity for the graph is O(N + M).

  2. Visited Dictionary: The dictionary d stores the conversion rates for each currency starting from the initial currency. In the worst case, this can also be O(N + M).

Thus, the overall space complexity for the solution is O(N + M) due to storing both the graph and the dictionary of visited nodes.

In summary, the code's computational complexity is:

  • Time Complexity: O(N + M)
  • Space Complexity: O(N + M)

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More