Two Robots Minimum Distance | DSA Interview Patterns - Study Chapter | QuizMaker

Course

DSA Interview Patterns Roadmap

Topic

Company Asked Variants

Learning Outcome

Turn the Two Robots Minimum Distance interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Given ordered queries from point a to b, two robots can execute them. Minimize total movement.

Examples

Brute Force Approach

Assign each query to robot 1 or robot 2 recursively, producing 2^q choices.

Optimized Approach

DP by query index and the idle robot position; the active robot is implied by the previous query end.

Exact Pseudocode

dp(i, idle)
active = end of query i-1
option1 = move active to query i start/end
option2 = move idle to query i start/end
return min

Reference Code

from functools import lru_cache

def minimum_distance(queries):
    n = len(queries)

    @lru_cache(None)
    def dp(i, idle):
        if i == n:
            return 0
        start, end = queries[i]
        active = None if i == 0 else queries[i - 1][1]
        move_active = abs(start - end) if active is None else abs(active - start) + abs(start - end)
        best = move_active + dp(i + 1, idle)
        if idle != -1:
            move_idle = abs(idle - start) + abs(start - end)
            best = min(best, move_idle + dp(i + 1, active if active is not None else -1))
        else:
            best = min(best, abs(start - end) + dp(i + 1, active if active is not None else -1))
        return best

    return dp(0, -1)

int minimumDistance(vector<pair<int,int>>& queries) {
    int n = queries.size();
    map<pair<int,int>, int> memo;
    function<int(int,int)> dp = [&](int i, int idle) {
        if (i == n) return 0;
        auto key = make_pair(i, idle);
        if (memo.count(key)) return memo[key];
        int start = queries[i].first, end = queries[i].second;
        int active = (i == 0 ? -1 : queries[i - 1].second);
        int moveActive = (active == -1 ? 0 : abs(active - start)) + abs(start - end);
        int best = moveActive + dp(i + 1, idle);
        int moveIdle = (idle == -1 ? 0 : abs(idle - start)) + abs(start - end);
        best = min(best, moveIdle + dp(i + 1, active));
        return memo[key] = best;
    };
    return dp(0, -1);
}

static Map<String, Integer> memo;

public static int minimumDistance(int[][] queries) {
    memo = new HashMap<>();
    return dp(0, -1, queries);
}

private static int dp(int i, int idle, int[][] q) {
    if (i == q.length) return 0;
    String key = i + "#" + idle;
    if (memo.containsKey(key)) return memo.get(key);
    int start = q[i][0], end = q[i][1];
    int active = i == 0 ? -1 : q[i - 1][1];
    int moveActive = (active == -1 ? 0 : Math.abs(active - start)) + Math.abs(start - end);
    int best = moveActive + dp(i + 1, idle, q);
    int moveIdle = (idle == -1 ? 0 : Math.abs(idle - start)) + Math.abs(start - end);
    best = Math.min(best, moveIdle + dp(i + 1, active, q));
    memo.put(key, best);
    return best;
}

Complexity

Edge Cases

• First query has no active robot
• Same start/end
• Large coordinates

Follow-ups

• Return assignment path
• More than two robots

Nearest Practice References

• HackerRank Two Robots
• DP with compressed state

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.

Tags

• dsa
• coding interview
• java
• c++
• python
• no-js
• company-asked-variants