Water Jugs Problem

Suppose we are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, there is a blue jug for every red jug that holds the same amount of water and vice versa. The task is to efficiently group the jugs into pairs of red and blue jugs that hold the same amount of water. (Problem Source: CLRS)

A simple solution to group the jugs into pairs is to compare a red jug with each blue jug. Once we get the matching pair, group that pair, and repeat for the next red jug. This algorithm can be easily implemented, but it will perform at most n² comparisons.

We can do better by using a randomized algorithm where the expected number of comparisons is n.log(n). The idea is analogous to the randomized Quicksort algorithm.

Randomly pick a jug from either red or blue jugs.
Partition the red jugs around the chosen jug such that it will be divided into two groups – red jugs smaller than the selected jug and those which are larger than the selected jug.
Once the red jugs have been divided, partition the blue jugs similarly – those which are smaller and those which are larger than the chosen jug.
Once the red and blue jugs are divided into two groups, repeat the process for the group of red and blue jugs that are smaller and larger than the chosen jug.

The expected number of comparisons performed by the above algorithm is the same as that of a randomized Quicksort algorithm, i.e., n.log(n) comparisons for n items. In the worst-case, the largest jug gets picked every time, which results in n² comparisons.

Following is the implementation in C++, Java, and Python based on the above idea:

C++

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Utility function to print a vector

void printVector(vector<int> const &A, string msg)

{

cout << msg << ": ";

for (int i: A) {

cout << i << " ";

}

cout << endl;

}

// This function is similar to the partition routine of the Quicksort algorithm.

// It partitions the specified array A[low, high] around `pivot`

// and returns the partition index.

int partition(vector<int> &A, int low, int high, int pivot)

{

int pIndex = low;

for (int j = low; j < high; j++)

{

if (A[j] < pivot)

{

swap(A[pIndex], A[j]);

pIndex++;

}

else if (A[j] == pivot)

{

swap(A[j], A[high]);

j--;

}

swap(A[pIndex], A[high]);

return pIndex;

}

// Group the jugs into pairs of red and blue jugs that hold the same amount of water.

// This function is similar to the Quicksort-like routine.

void findMatchingPairs(vector<int> &red, vector<int> &blue, int low, int high)

{

// base case: if there is only one red jug and one blue jug,

// they must be of the same size

if (low >= high) {

return;

}

// Randomly select a jug from either red or blue jugs

int r = rand() % (high - low + 1) + low;

int chosenJug = red[r]; // or use blue[r]

// Partition the red jugs around the chosen jug

int pivot = partition(red, low, high, chosenJug);

// Now partition the blue jugs around the chosen jug

partition(blue, low, high, chosenJug);

// `pivot` now points to an index of the chosen jug in red/blue jugs.

// Recur, once the red and blue jugs are divided into two groups

// around the chosen jug

findMatchingPairs(red, blue, low, pivot - 1);

findMatchingPairs(red, blue, pivot + 1, high);

}

int main()

{

vector<int> red = { 6, 3, 2, 8, 7 };

vector<int> blue = { 8, 6, 7, 2, 3 };

int n = red.size();

findMatchingPairs(red, blue, 0, n - 1);

printVector(red, "Red jugs");

printVector(blue, "Blue jugs");

return 0;

}

Download Run Code

Output:

Red jugs: 2 3 6 7 8
Blue jugs: 2 3 6 7 8

Java

import java.util.Arrays;

import java.util.Random;

class Main

{

// Utility function to swap elements at indices `i` and `j` in array `A`

public static void swap(int[] A, int i, int j)

{

int temp = A[i];

A[i] = A[j];

A[j] = temp;

}

// This method is similar to the partition routine of the Quicksort algorithm.

// It partitions the specified array A[low, high] around `pivot`

// and returns the partition index.

private static int partition(int[] A, int low, int high, int pivot)

{

int pIndex = low;

for (int j = low; j < high; j++)

{

if (A[j] < pivot)

{

swap(A, pIndex, j);

pIndex++;

}

else if (A[j] == pivot)

{

swap(A, j, high);

j--;

}

swap(A, pIndex, high);

return pIndex;

}

// Group the jugs into pairs of red and blue jugs that hold the same amount

// of water. This method is similar to the Quicksort-like routine.

private static void findMatchingPairs(int[] red, int[] blue, int low, int high)

{

// base case: if there is only one red jug and one blue jug,

// they must be of the same size

if (low >= high) {

return;

}

// Randomly select a jug from either red or blue jugs

int r = new Random().nextInt(high - low + 1) + low;

int chosenJug = red[r]; // or use blue[r]

// Partition the red jugs around the chosen jug

int pivot = partition(red, low, high, chosenJug);

// Now partition the blue jugs around the chosen jug

partition(blue, low, high, chosenJug);

// `pivot` now points to an index of the chosen jug in red/blue jugs.

// Recur, once the red and blue jugs are divided into two groups

// around the chosen jug

findMatchingPairs(red, blue, low, pivot - 1);

findMatchingPairs(red, blue, pivot + 1, high);

}

public static void main(String[] args)

{

int[] red = {6, 3, 2, 8, 7};

int[] blue = {8, 6, 7, 2, 3};

findMatchingPairs(red, blue, 0, red.length - 1);

System.out.println("Red jugs: " + Arrays.toString(red));

System.out.println("Blue jugs: " + Arrays.toString(blue));

}

Download Run Code

Output:

Red jugs: [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]

Python

import random

# Utility function to swap elements at indices `i` and `j` in array `A`

def swap(A, i, j):

temp = A[i]

A[i] = A[j]

A[j] = temp

# This method is similar to the partition routine of the Quicksort algorithm.

# It partitions the specified array A[low, high] around `pivot`

# and returns the partition index.

def partition(A, low, high, pivot):

pIndex = low

j = low

while j < high:

if A[j] < pivot:

swap(A, pIndex, j)

pIndex = pIndex + 1

elif A[j] == pivot:

swap(A, j, high)

j = j - 1

j = j + 1

swap(A, pIndex, high)

return pIndex

# Group the jugs into pairs of red and blue jugs that hold the same amount of water.

# This method is similar to the Quicksort-like routine.

def findMatchingPairs(red, blue, low, high):

# base case: if there is only one red jug and one blue jug,

# they must be of the same size

if low >= high:

return

# Randomly select a jug from either red or blue jugs

r = random.randint(low, high)

chosenJug = red[r] # or use blue[r]

# Partition the red jugs around the chosen jug

pivot = partition(red, low, high, chosenJug)

# Now partition the blue jugs around the chosen jug

partition(blue, low, high, chosenJug)

# `pivot` now points to an index of the chosen jug in red/blue jugs.

# Recur, once the red and blue jugs are divided into two groups

# around the chosen jug

findMatchingPairs(red, blue, low, pivot - 1)

findMatchingPairs(red, blue, pivot + 1, high)

if __name__ == '__main__':

red = [6, 3, 2, 8, 7]

blue = [8, 6, 7, 2, 3]

findMatchingPairs(red, blue, 0, len(red) - 1)

print('Red jugs:', red)

print('Blue jugs:', blue)

Download Run Code

Output:

Red jugs: [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]

The time complexity of the above algorithm is the same as that of Quicksort, i.e., O(n.log(n)). The auxiliary space required by the algorithm is O(n) for the call stack.

There are several other variations of this problem which can be solved similarly:

Nuts & Bolts Problem: Given n nuts and n bolts of different shapes and sizes. The task is to match nuts with bolts, provided that a specific bolt can open each nut.
Lock & Key Problem: Given a box of n locks and n keys where each lock can be opened by only a specific key in the box. The task is to match locks with their keys.

C++

Java

Python

Share this: