In this post, we discuss the Meet in Middle problem solving technique and show through examples how we can use it to improve a naive brute force algorithm.

Table of contents:

1. Introduction to Meet In Middle
2. Problem 1: Pythagorean triplet
3. Problem 2: Maximum sum subset
4. More examples using Meet in Middle

Introduction to Meet In Middle

The meet-in-middle algorithm is a search technique used for problem solving whereby the given input size of the problem is small but not small enough for a brute force approach to work.

It works by splitting the given input into two subsets, solves them using a standard algorithm then combines results obtained from the subsets to come up with a general solution.

Like divide and conquer it takes a similar approach of dividing a problem in smaller sub-problems but unlike divide and conquer, we do not use recursion.

It also has a similar approach to dynamic programming whereby we divide a problem and break it down to smaller problems and combine sub-solutions to solve the main problem but unlike dynamic programming, we only divide problems into two parts here.

Problem 1: Pythagorean triplet

Problem Statement; Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies the pythagorean theorem that is, a2+b2=c2.

Example 1:

Input: array = [3, 10, 4, 6, 13, 8]
Output: true
Explanation.
square(6) + square(8) = square(10), 36 + 64 = 100

Example 2:

Input: array = [3, 10, 4, 7, 13, 8]
Output: false
Explanation.
There are no elements in the array that satisfy the condition, we return false.

Naive Approach.

We compute all combinations of all elements in the array, in python we use something like itertools combinations for this and out of those subsets we return true is any satisfies the condtion, otherwise we return false.

Pseudocode

for i from 0 - n
    for j from i+1 to n
        for k from j+1 to n
            return true if either of the conditions suffice
            arr[i] * arr[i] = arr[j] * arr[j] + arr[k] + arr[k]
            arr[j] * arr[j] = arr[i] * arr[i] + arr[k] + arr[k]
            arr[k] * arr[k] = arr[i] * arr[i] + arr[j] + arr[j]
            otherwise false

Analysis

This is a brute force approach, we try out all possible combinations of the elements to find the result.

We use three loops making out time complexity O(N³).

Optimized Approach

We will optimize the naive approach using meet-in-middle technique to achieve a better computational complexity.

In this approach we use three pointers and work our way to the middle of the array making comparisons until the pythagorean condition is met.

Steps

1. Square all elements in the input array.
2. Sort the squared array in non-decreasing order.
3. To find a triplet;
   • Initialize three pointers l, r, t.
   • loop while l < r,
     • if arr[l] + arr[r] == arr[t] return true.
     • if arr[l] + arr[r] < arr[t], increment l pointer.
     • if arr[l] + arr[r] > arr[t], decrement r pointer.
   • if no triplet is found return false.

#include<iostream>
#include<vector>
#include<algorithm>

using std::vector;

bool isTriplet(vector<int> arr){
    int n = arr.size();

    for(int i = 0; i < n; i++)
        arr[i] = arr[i] * arr[i];

    sort(arr.begin(), arr.end());

    for(int i = n - 1; i >= 2; i--){
        int l = 0, r = i-1;
        while(l < r){
            if(arr[l] + arr[r] == arr[i])
                return true;
            else if(arr[l] + arr[r] < arr[i])
                l++;
            else
                r--;
        }
    }
    return false;
}

Analysis

The time complexity of this approach is O(N²).

Problem 2: Maximum sum subset

Problem Statement; Given a set of n integers where n <= 40, determine the maximum sum subset having a sum less than s.

Example 1.

Input: array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], s = 20
Output: 20
Explanation: the maximum possible sum is 20, it can be obtained by adding, 10, 9, 1.

Example 2.

Input: array = [32, 12, 19, 3, 1, 11, 5], s = 9
Output: 9
Explanation: the maximum sum obtained that is closer to s is 9, obtained by adding, 5, 3, 1.

Naive Approach.

We could use a brute force approach like in the previous problem where we get all possible subsets are return the maximum sum among them that is less than m.

Analysis.

N is at most 40 so there are O(2⁴⁰) steps. The time complexity is exponential O(2^N).

This is not optimal.

Optimized approach.

Again we will use meet-in-middle algorithm to optimize the time complexity to a better one.

Assuming n = 20, that is O(2²⁰) steps is not such a big number compared to O(2⁴⁰).

We can use the brute force approach twice for each subset and combine results from each subset to obtain a general solution.

Steps.

1. Split the array into two sets A and B each having n/2 items, that is 20 elements each.
2. Calculate all possible subsets and their sums for A and store them in array X and do the same for B and store them in array Y.
3. Sort array Y and itertate over X elements, for each element we use binary search to find the largest element in Y such that x + y is less than or equal t s.

#include<iostream>
#include<algorithm>

using std::sort;
using std::lower_bound;

typedef long long ll;
ll X[2000005], Y[2000005];

void calcSubSet(ll A[], ll X[], int n, int c){
    for(int i = 0; i < (1<<n); i++){
        ll s = 0;
        for(int j = 0; j < n; j++){
            if(i & (1<<j))
                s += A[j+c];
        }
        X[i] = s;
    }
}

ll solve(ll a[], int n, ll S){
    //subsets of 1st and 2nd halves
    calcSubSet(a, X, n/2, 0);
    calcSubSet(a, Y, n-n/2, n/2);

    int sizeX = 1 << (n/2);
    int sizeY = 1 << (n-n/2);
    
    //sort Y
    sort(Y, Y+sizeY);
    
    //keep track of max element
    ll max = 0;

    for(int i = 0; i < sizeX; i++){
        if(X[i] <= S){
            int p = lower_bound(Y, Y+sizeY, S-X[i]) - Y;

            if(p == sizeY || Y[p] != (S-X[i]))
                p--;
            
            if((Y[p] + X[i]) > max)
                max = Y[p] + X[i];
        }
    }
    return max;
}

Analysis.

The time complexity is O(2n2).

More examples using Meet in Middle

1. 4 sum problem.

Problem statement: Given an array of n integers and an integer target, find 4 values whose sum is equal to target.

Hint: Traverse the array using two pointers i, j, Compute sums of pairs before i and store in a data structure, move i. While traversing from j to end of array, look for the remaining pairs whose sum complements the stored pairs before i to add up to target. We improve O(n4) to O(n2) using meet in middle.

2. Increasing subsequences of length 3

Problem Statement: Given an array of integers, count the number of increasing subsequences of length 3.

Hint: We could write a brute force algorithm with O(n3) time complexity. To optimize, instead of looping three times, we could use the 2nd element of the 3 elements.
That is from the 2nd element, find elements less than it to the left and elements greater than it to the right. O(n2) time complexity.

3. 0-1 Knapsack.

Problem statement: Given a set of items and their weights. We are to combine them to get the maximum value with weight w that can fit into a knapsack of weight W. We cannot break elements, we take them or leave them.

Hint: Partition items into two subsets and compute the weights and values of each, then for each subset of A we find a subset of b with the greatest value such that their combined weight if less than W while keeping track of max value obtained so far.

With this article at OpenGenus, you must have the complete idea of Meet in Middle technique.