Minimum Range - C++ Solution

1. Introduction

In this blog post, we tackle a more complex problem in array processing: efficiently finding the minimum range that includes at least one element from each of three sorted arrays. This problem is a great example of using pointers and min-heaps in C++ to deal with multiple sorted data structures.

Problem

Given three sorted arrays of variable lengths, the task is to find the smallest range that contains at least one element from each array.

Examples:

- Input: [[3, 6, 8, 10, 15], [1, 5, 12], [4, 8, 15, 16]]

Output: (3, 5)

- Input: [[2, 3, 4, 8, 10, 15], [1, 5, 12], [7, 8, 15, 16]]

Output: (4, 7)

- Input: [[1], [1, 2], [0, 1]]

Output: (1, 1)

- Input: [[], [], []]

Output: (-1, -1)

2. Solution Steps

1. Use pointers to iterate over each of the three arrays.

2. Keep track of the current maximum and minimum elements among the pointers.

3. Update the minimum range whenever a smaller range is found.

4. Move the pointer that points to the current minimum element to find the next possible range.

5. Repeat the process until one of the arrays is completely traversed.

3. Code Program

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to find the minimum range
pair<int, int> findMinRange(vector<int> arr1, vector<int> arr2, vector<int> arr3) {
    int i = 0, j = 0, k = 0;
    int minRange = INT_MAX;
    pair<int, int> range = {-1, -1};

    while (i < arr1.size() && j < arr2.size() && k < arr3.size()) {
        int minVal = min({arr1[i], arr2[j], arr3[k]});
        int maxVal = max({arr1[i], arr2[j], arr3[k]});

        // Update the range if a smaller one is found
        if (maxVal - minVal < minRange) {
            minRange = maxVal - minVal;
            range = {minVal, maxVal};
        }

        // Move the pointer that points to the current minimum
        if (arr1[i] == minVal) {
            i++;
        } else if (arr2[j] == minVal) {
            j++;
        } else {
            k++;
        }
    }

    return range;
}

int main() {
    vector<int> arr1 = {3, 6, 8, 10, 15};
    vector<int> arr2 = {1, 5, 12};
    vector<int> arr3 = {4, 8, 15, 16};
    auto result = findMinRange(arr1, arr2, arr3);
    cout << "Minimum Range: (" << result.first << ", " << result.second << ")" << endl;
    return 0;
}

Output:

Minimum Range: (3, 5)

Explanation:

The findMinRange function iterates over the three arrays using pointers. At each step, it finds the current minimum and maximum among the elements pointed to by the pointers. If the range between this min and max is smaller than the previously found ranges, it updates the minimum range. The pointer pointing to the current minimum value is then incremented to explore new ranges. This process continues until one of the arrays is fully traversed, resulting in finding the minimum range that includes at least one element from each array.