Unit Conversion II - Practice Coding Problems

Unit Conversion II - Problem

There are n types of units indexed from 0 to n - 1. You are given a 2D integer array conversions of length n - 1, where conversions[i] = [sourceUnit_i, targetUnit_i, conversionFactor_i]. This indicates that a single unit of type sourceUnit_i is equivalent to conversionFactor_i units of type targetUnit_i.

You are also given a 2D integer array queries of length q, where queries[i] = [unitA_i, unitB_i]. Return an array answer of length q where answer[i] is the number of units of type unitB_i equivalent to 1 unit of type unitA_i, and can be represented as p/q where p and q are coprime.

Return each answer[i] as p * q^(-1) mod (10^9 + 7), where q^(-1) represents the multiplicative inverse of q modulo 10^9 + 7.

Input & Output

Example 1 — Basic Conversion Chain

$ Input: conversions = [[0,1,3],[1,2,2]], queries = [[0,2],[1,0]]

› Output: [6,333333336]

💡 Note: For query [0,2]: 0→1 (×3) then 1→2 (×2), so 1 unit of type 0 = 6 units of type 2. For query [1,0]: reverse conversion 1→0 is 1/3, which as modular arithmetic gives 333333336.

Example 2 — Direct Conversion

$ Input: conversions = [[0,1,5]], queries = [[0,1],[1,0]]

› Output: [5,400000003]

💡 Note: Direct conversions: 0→1 gives 5/1 = 5. Reverse 1→0 gives 1/5, and the modular inverse of 5 mod (10^9+7) is 400000003.

Example 3 — No Path Available

$ Input: conversions = [[0,1,2]], queries = [[0,2]]

› Output: [0]

💡 Note: No conversion path exists from unit 0 to unit 2, so return 0.

Constraints

1 ≤ n ≤ 100
conversions.length == n - 1
1 ≤ queries.length ≤ 100
1 ≤ conversionFactor_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Conversions [[0,1,3],[1,2,2]] create connected units

Path Search

Find path from query unit A to unit B

Ratio Calculation

Multiply conversion factors along the path

Key Takeaway

🎯 Key Insight: Model conversions as a graph and use DFS to find conversion paths between units

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to model unit conversions as a graph where nodes are unit types and edges are conversion ratios. Build a graph from the conversion array, then use DFS to find paths between query units and calculate the conversion ratio along the path. The result must be expressed as p×q^-1 mod (10⁹+7) using modular arithmetic. Best approach uses memoization to cache computed ratios. Time: O(n + q), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Graph Traversal with Memoization	O(n + q)	O(n²)	Use BFS/DFS with memoization to cache conversion ratios between units
Brute Force Path Search	O(q × n)	O(n)	For each query, try all possible paths through the conversion graph

Optimized Graph Traversal with Memoization — Algorithm Steps

Build adjacency list from conversions
Use memoization map to cache ratios
For each query, check cache or use DFS to find new ratio

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create bidirectional conversion graph

Cache Results

Store computed ratios in memoization table

Fast Lookup

Reuse cached results for repeated queries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_NODES 100
#define MAX_MEMO 10000

typedef struct {
    long long p, q;
} Fraction;

typedef struct Edge {
    int neighbor;
    Fraction ratio;
    struct Edge* next;
} Edge;

typedef struct {
    char key[20];
    Fraction* value;
} MemoEntry;

Edge* graph[MAX_NODES];
int visited[MAX_NODES];
MemoEntry memoTable[MAX_MEMO];
int memoSize = 0;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long modInverse(long long a) {
    return modPow(a, MOD - 2, MOD);
}

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

void addEdge(int src, int dst, Fraction ratio) {
    Edge* edge = malloc(sizeof(Edge));
    edge->neighbor = dst;
    edge->ratio = ratio;
    edge->next = graph[src];
    graph[src] = edge;
}

Fraction* getMemo(char* key) {
    for (int i = 0; i < memoSize; i++) {
        if (strcmp(memoTable[i].key, key) == 0) {
            return memoTable[i].value;
        }
    }
    return NULL;
}

void setMemo(char* key, Fraction* value) {
    if (memoSize < MAX_MEMO) {
        strcpy(memoTable[memoSize].key, key);
        memoTable[memoSize].value = value;
        memoSize++;
    }
}

Fraction* dfs(int start, int target) {
    char key[20];
    sprintf(key, "%d-%d", start, target);
    
    Fraction* cached = getMemo(key);
    if (cached) return cached;
    
    if (start == target) {
        Fraction* result = malloc(sizeof(Fraction));
        result->p = 1;
        result->q = 1;
        setMemo(key, result);
        return result;
    }
    
    visited[start] = 1;
    Edge* edge = graph[start];
    while (edge) {
        if (!visited[edge->neighbor]) {
            Fraction* result = dfs(edge->neighbor, target);
            if (result) {
                long long newP = edge->ratio.p * result->p;
                long long newQ = edge->ratio.q * result->q;
                long long g = gcd(newP, newQ);
                Fraction* finalResult = malloc(sizeof(Fraction));
                finalResult->p = newP / g;
                finalResult->q = newQ / g;
                setMemo(key, finalResult);
                visited[start] = 0;
                return finalResult;
            }
        }
        edge = edge->next;
    }
    visited[start] = 0;
    setMemo(key, NULL);
    return NULL;
}

int* solution(int** conversions, int conversionsSize, int** queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = malloc(queriesSize * sizeof(int));
    
    // Initialize
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }
    memoSize = 0;
    
    // Build graph
    for (int i = 0; i < conversionsSize; i++) {
        int src = conversions[i][0];
        int dst = conversions[i][1];
        int factor = conversions[i][2];
        
        addEdge(src, dst, (Fraction){factor, 1});
        addEdge(dst, src, (Fraction){1, factor});
    }
    
    // Process queries
    for (int i = 0; i < queriesSize; i++) {
        memset(visited, 0, sizeof(visited));
        Fraction* ratio = dfs(queries[i][0], queries[i][1]);
        if (!ratio) {
            result[i] = 0;
        } else {
            long long p = ratio->p % MOD;
            long long q = ratio->q % MOD;
            result[i] = (p * modInverse(q)) % MOD;
        }
    }
    
    return result;
}

int main() {
    printf("[0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q)

Build graph once O(n), each query O(1) with memoization in best case

✓ Linear Growth

Space Complexity

O(n²)

Graph storage O(n) plus memoization cache for all pairs O(n²)

⚠ Quadratic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Graph Traversal with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler