Water Jug problem using BFS
Problem Statement
You have two jugs with capacities A and B litres respectively. You can fill a jug completely, empty a jug, or pour water from one jug to another. Determine the minimum number of steps to measure exactly C litres of water in either jug.
Example:
- Input:
A = 4, B = 3, C = 2 - Output:
4(Steps: Fill 4L jug → Pour into 3L jug → Empty 3L jug → Pour from 4L to 3L → now 4L jug has 1L... eventually reach 2L)
Noob-Friendly Explanation
Imagine you're at a river with two buckets — one holds 4 litres and the other holds 3 litres. You need to measure exactly 2 litres. You can only do three things: fill a bucket completely from the river, dump a bucket completely, or pour from one bucket to the other (stop when either the source is empty or the destination is full).
This is like a puzzle! BFS helps us explore every possible combination of water levels in both jugs until we find the target amount.
Approach 1: Brute Force (Recursive with Memoization)
Intuition
Try all possible operations (fill, empty, pour) from each state. A state is (water in jug A, water in jug B). Track visited states to avoid infinite loops. Try all paths and find the minimum steps.
Algorithm
- Start from state (0, 0).
- From each state, generate all 6 possible next states.
- Use memoization to avoid revisiting states.
- Return the minimum steps to reach any state containing C.
import java.util.*;
public class WaterJugBrute {
static Map<String, Integer> memo = new HashMap<>();
public static int solve(int a, int b, int target) {
memo.clear();
int result = dfs(0, 0, a, b, target, new HashSet<>());
return result == Integer.MAX_VALUE ? -1 : result;
}
static int dfs(int currA, int currB, int capA, int capB, int target, Set<String> visited) {
if (currA == target || currB == target) return 0;
String state = currA + "," + currB;
if (visited.contains(state)) return Integer.MAX_VALUE;
visited.add(state);
int best = Integer.MAX_VALUE;
int[][] nextStates = {
{capA, currB}, // Fill A
{currA, capB}, // Fill B
{0, currB}, // Empty A
{currA, 0}, // Empty B
{Math.max(0, currA - (capB - currB)), Math.min(capB, currA + currB)}, // Pour A → B
{Math.min(capA, currA + currB), Math.max(0, currB - (capA - currA))} // Pour B → A
};
for (int[] next : nextStates) {
int res = dfs(next[0], next[1], capA, capB, target, visited);
if (res != Integer.MAX_VALUE) {
best = Math.min(best, 1 + res);
}
}
visited.remove(state);
return best;
}
public static void main(String[] args) {
System.out.println("Min steps: " + solve(4, 3, 2));
}
}Complexity Analysis
- Time Complexity: O(A * B) - each state (i, j) with 0 ≤ i ≤ A, 0 ≤ j ≤ B is visited at most once
- Space Complexity: O(A * B) - for the visited set
Approach 2: Optimal (BFS)
Intuition
BFS is ideal for finding the shortest path (minimum steps). Each state is (water in jug A, water in jug B). From each state, we generate all possible next states using the 6 operations. BFS guarantees the first time we reach a state with C litres, we've found the minimum steps.
Algorithm
- Start BFS from state (0, 0).
- For each state, generate 6 possible next states:
- Fill A, Fill B, Empty A, Empty B, Pour A→B, Pour B→A.
- If any next state has C litres in either jug, return the step count.
- Mark states as visited to avoid cycles.
import java.util.*;
public class WaterJugBFS {
public static int solve(int capA, int capB, int target) {
if (target > Math.max(capA, capB)) return -1;
if (target == 0) return 0;
Set<String> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 0}); // {waterA, waterB, steps}
visited.add("0,0");
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int a = curr[0], b = curr[1], steps = curr[2];
int[][] nextStates = {
{capA, b}, // Fill A
{a, capB}, // Fill B
{0, b}, // Empty A
{a, 0}, // Empty B
{Math.max(0, a - (capB - b)), Math.min(capB, a + b)}, // Pour A → B
{Math.min(capA, a + b), Math.max(0, b - (capA - a))} // Pour B → A
};
for (int[] next : nextStates) {
if (next[0] == target || next[1] == target) {
return steps + 1;
}
String key = next[0] + "," + next[1];
if (!visited.contains(key)) {
visited.add(key);
queue.offer(new int[]{next[0], next[1], steps + 1});
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println("Min steps: " + solve(4, 3, 2));
}
}Complexity Analysis
- Time Complexity: O(A * B) - there are at most (A+1)*(B+1) states, each processed once
- Space Complexity: O(A * B) - for the visited set and queue