Water jug problem (reach a target amount)

Medium

Problem

You have jugs of capacity m and n litres and unlimited water. Each step you may fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Return the minimum number of steps to measure exactly d litres in either jug, or −1 if impossible.

Example 1

Input:  m = 3, n = 5, d = 4
Output: 6

Also asked as: Water Jug problem using BFS

Test cases

Case 1

Input:    3, 5, 4
Expected: 6

Case 2

Input:    4, 3, 2
Expected: 4

Case 3

Input:    3, 5, 3
Expected: 1

Case 4

Input:    2, 6, 5
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. BFS over (jug1, jug2) states

Time O(cap1 · cap2)Space O(cap1 · cap2)

Each state is the pair of current amounts; transitions are fill/empty/pour for either jug. BFS finds the fewest steps to any state containing the target.

function waterJug(cap1, cap2, target) {
const seen = new Set(['0,0']);
let q = [[0, 0, 0]];
while (q.length) {
const next = [];
for (const [a, b, d] of q) {
if (a === target || b === target || a + b === target) return d;
const moves = [
[cap1, b], [a, cap2], [0, b], [a, 0],
[Math.min(a + b, cap1), b - (Math.min(a + b, cap1) - a)],
[a - (Math.min(a + b, cap2) - b), Math.min(a + b, cap2)],
];
for (const [na, nb] of moves) {
const key = na + ',' + nb;
if (!seen.has(key)) { seen.add(key); next.push([na, nb, d + 1]); }
}
}
q = next;
}
return -1;
}