1
\$\begingroup\$

I solved this problem

Given three sorted arrays A, B and C of not necessarily same sizes.

Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively. i.e. minimize | max(a,b,c) - min(a,b,c) |.

Example :

Input:

A : [ 1, 4, 5, 8, 10 ] B : [ 6, 9, 15 ] C : [ 2, 3, 6, 6 ]

Output:

1

Explanation:

We get the minimum difference for a=5, b=6, c=6 as | max(a,b,c) - min(a,b,c) | = |6-5| = 1.

The idea behind my solution was if at each iteration we have the closest triplets we will be able to get the optimal absolute minimum.

I couldn't find a clean way to implement this logic. And my solution is this.

int Solution::solve(vector<int> &A, vector<int> &B, vector<int> &C) {
    int answer = INT_MAX;
    int a = 0, b = 0, c = 0;
    while(a < A.size() || b < B.size()  || c < C.size() )
    {
        // cout << a << ' ' << b << ' ' << c << endl;
        int MinVal = min(min(A[a], B[b]), C[c]);
        int MaxVal = max(max(A[a], B[b]), C[c]);
        bool na = false, nb = false, nc = false;
        answer = min(answer, abs(MaxVal - MinVal));
        if(a + 1 < A.size() && A[a + 1] <= MaxVal)
        {
            ++a;
        }
        else if(b + 1 < B.size() && B[b + 1] <= MaxVal)
        {
            ++b;
        }
        else if(c + 1 < C.size() && C[c + 1] <= MaxVal)
        {
            ++c;
        }
        else
        {
            // cout << "Next Max\n";
            int next_a = a + 1 < A.size() ? A[a + 1] : INT_MAX;
            int next_b = b + 1 < B.size() ? B[b + 1] : INT_MAX;
            int next_c = c + 1 < C.size() ? C[c + 1] : INT_MAX;
            // cout << next_a << ' ' << next_b << ' ' << next_c << endl;
            if(next_a <= min(next_b, next_c) && next_a != INT_MAX)
            {
                ++a;
            }
            else if(next_b <= min(next_a, next_c) && next_b != INT_MAX)
            {
                ++b;
            }
            else if(next_c < min(next_a, next_b) && next_c != INT_MAX)
            {
                ++c;
            }
            else
            {
                break;
            }

        }
    }
    return answer;
}

Could you please suggest how to avoid excessive if-else statements in the solution. Also, this solution wouldn't be scaleable for more array's so a more general approach would be helpful as well

\$\endgroup\$
  • \$\begingroup\$ You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include lines, any using declarations, and a main() that shows how to call your function. It can really help reviewers if they are able to compile and run your program. \$\endgroup\$ – Toby Speight Apr 9 '18 at 10:11
  • \$\begingroup\$ BTW, this is an interesting question, and I would like to answer it, but I'll give you time to add the extra code before I add my answer. \$\endgroup\$ – Toby Speight Apr 9 '18 at 10:38
  • \$\begingroup\$ This is a online judge which only requires us to write the particular method. The pluming the goes with this solution isn't really visible to us. The input is given to us and we are only required to return the answer. You can check out the link if you want to run your solution against the test cases. \$\endgroup\$ – thebenman Apr 9 '18 at 15:44
2
\$\begingroup\$

Headers and namespace

We're missing headers

#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>

Also, it appears the code assumes using namespace std. Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Code the solution, and adapt it to fit

The use of the Solution class appears to be an artefact of your test environment. Since the function doesn't need any state, prefer to write it as you normally would:

// we'll change this signature later
static int minimum_range(const std::vector<int> &A,
                         const std::vector<int> &B,
                         const std::vector<int> &C);

And then provide Solution as a thin wrapper around it, like:

int Solution::solve(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
    return minimum_range(a, b, c);
}

We can then call minimum_range from our test program much more simply:

int main()
{
    return
        + (0 != minimum_range(std::vector{5}))
        // add more tests here
        + (1 != minimum_range(std::vector{1, 4, 5, 8, 10}, std::vector{6, 9, 15}, std::vector{2, 3, 6, 6}));
}

We might make an exception to this general advice in the case of competitive performance-oriented programming; but then code review goes out of the window entirely, as speed trumps style and maintainability there.

Algorithm

The method is basically sound; it scales well to large vectors, but doesn't scale well to many vectors (as you note in the description).

For general code, prefer to think in iterators rather than indexes. The code will be equivalent, but usable with more types than just vectors and arrays.

If we keep a collection of iterators (one for each of the arrays), then at each step, we want to advance the one that points to the smallest element (added complication - we need to tie-break by choosing the one that advances the least). We have finished when that one reaches the end of its array; that means we also need to remember the end iterator for each array. That means we end up storing a range for each input vector.

template<typename Iter>
struct range
{
    Iter current;
    Iter const end;
};

template<typename T>
range<typename std::vector<T>::const_iterator> make_range(const std::vector<T> &v)
{
    return {v.begin(), v.end()};
}

Now we can transform the vectors into ranges:

static int minimum_range(const std::vector<int> &A,
                         const std::vector<int> &B,
                         const std::vector<int> &C)
{
    auto range = { make_range(A), make_range(B), make_range(C) };

    auto minmax_range = std::minmax_element(range.begin(), range.end());

For the std::minmax_element() call to work, we'll need a suitable < operator in our range. Add this:

bool operator<(const range& other) const
{
    if (current == end) return false;
    if (other.current == other.end) return true;
    auto a = *current, b = *other.current;
    if (a != b) return a < b;

    // it's a draw - which one advances least?
    if (current+1 == end) return false;
    if (other.current+1 == other.end) return true;
    a = current[1], b = other.current[1];
    return a < b;
}

Now let's go back to the algorithm and make it iterate:

auto minmax_range = std::minmax_element(r.begin(), r.end());
auto& min_range = minmax_range.first;
auto& max_range = minmax_range.second;
int best = **max_range - **min_range;

while ((++*min_range).current != min_range->end) {
    minmax_range = std::minmax_element(r.begin(), r.end());
    best = std::min(best, **max_range - **min_range);
    if (best == 0) {
        break;   // we can't improve on zero
    }
}

There's some stuff to explain there. We create aliases for the minmax_range, which is a pair of iterators to range objects. We use the dereference operator, which needs defining in range to give the current first element of the range:

auto operator*() const { return *current; }

The loop control starts by incrementing the lowest range - that needs an implementation:

range& operator++() { ++current; return *this; }

If that produced a range that has reached the end, then we've considered all the possibilities.

Inside the loop, we find the new min and max (remember that min_range and max_range still alias the members of minmax_range), and update best if required.

Extension to many inputs

We can now use a std::initializer_list to supply an arbitrary number of collections of any kind of (comparable) element. I'll use C++17 for this (so we can write an implicit constructor for range, using a deduction guide).

#include <algorithm>
#include <vector>

template<typename Iter>
struct range
{
    Iter current;
    Iter const end;

    template<typename T>
    range(const T& v)
        : current{v.begin()},
          end{v.end()}
    {
    }

    explicit operator bool() const { return current != end; }

    auto operator*() const { return *current; }

    range& operator++() { ++current; return *this; }

    bool operator<(const range& other) const
    {
        return *this && (!other || *current < *other.current);
    }
};

// deduction guide
template<typename Container>
range(Container c) -> range<typename Container::const_iterator>;


template<typename Iter>
static auto minimum_range(std::initializer_list<range<Iter>> containers)
{
    using std::begin;
    using std::end;

    // Copy initializer list to read/write container
    std::vector r(begin(containers), end(containers));

    auto minmax_range = std::minmax_element(begin(r), end(r));
    auto& min_range = minmax_range.first;
    auto& max_range = minmax_range.second;
    auto best = **max_range - **min_range;

    while (++*min_range) {
        minmax_range = std::minmax_element(begin(r), end(r));
        best = std::min(best, **max_range - **min_range);
    }

    return best;
}

// convert containers to ranges and forward
template<typename... Args>
static auto minimum_range(const Args&... args)
{
    return minimum_range({range(args)...});
}
#include <list>
int main()
{
    return
        + (0 != minimum_range(std::list{5}))
        + (0.5 != minimum_range(std::vector{0.0}, std::vector{0.0}, std::vector{0.5}))
        + (6 != minimum_range(std::vector{6,30}, std::vector{10,12}, std::vector{6,15,30}, std::vector{12}))
        + (1 != minimum_range(std::vector{0, 6, 10}, std::vector{5}, std::vector{5}))
        // add more tests here
        + (1 != minimum_range(std::list{1, 4, 5, 8, 10}, std::list{6, 9, 15}, std::list{2, 3, 6, 6}));
}

I was unable to construct a test that proves the need for the tie-break in operator<, so I removed that code. I shouldn't have written it in the first place without a test to exercise it, of course...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.