Set array min forward and backward via recursion

Question

Let's say I have an array A = {a1, a2, ..., an}

Suppose A is divided in blocks of size b

What I'm trying to do is:

Let MinUntilHere and MinStartingHere be 2 arrays of size n, where:

MinUntilHere[i] = minimum from the beginning of i's block until i
MinStartingHere[i] = minimum from i until the end of i's block

I want to fill this 2 arrays in a single transversal in the array... I was trying the following pseudocode:

int fill(int pos = 0){

    if(pos >= n) return INF

    if(pos is the start index of a block){ //i % b == 0
        MinUntilHere[pos] = A[pos]
        MinStartingHere[pos] = min(A[pos], fill(i + 1))
    }
    else{
        MinUntilHere[pos] = min(A[pos], A[pos - 1])
        MinStartingHere[pos] = min(A[pos], fill(i + 1))
        return MinStartingHere[pos]
    }
}

but as you can see, it's not complete, since it can't detect when each block is over and some returns are missing. How can I make a function that go through the array only once and compute my answers?

Example:

Let A = {2,1,3,6,5,4} and b = 2, the arrays must be filled like this:

MinUntilHere =    {2,1,3,3,5,4}

MinStartingHere = {1,1,3,6,4,4}

MinUntilHere[0] = 2 cause from the beginning of 0's block until index 0, the minimum is 2.

MinUntilHere[1] = 1 cause from the beginning of 1's block until index 1, the minimum is min(1,2) = 1

End of Example

Shouldn't MinStartingHere be {1,1,3,6,4,4}?

Abhishek Bansal
– Abhishek Bansal

2016-08-05 16:01:48 +00:00
Commented Aug 5, 2016 at 16:01 — Abhishek Bansal
– Abhishek Bansal, Commented Aug 5, 2016 at 16:01
@AbhishekBansal sure, thanks for helping, fixed :)

Daniel
– Daniel

2016-08-05 16:04:54 +00:00
Commented Aug 5, 2016 at 16:04 — Daniel
– Daniel, Commented Aug 5, 2016 at 16:04

Jarod42 · Accepted Answer · 2016-08-05 17:59:37Z

You may use the following which does the job in 2 passes:

template <typename InputIt, typename OutputIt>
void ComputeMinUntilHere(InputIt begin, InputIt end, OutputIt output)
{
    if (begin == end) {
        return;
    }
    auto min = *begin;
    while (begin != end) {
        min = std::min(min, *begin);
        *output = min;
        ++begin;
        ++output;
    }
}

struct MinByBlock
{
    std::vector<int> minUntilHere;
    std::vector<int> minStartingHere;
};

MinByBlock ComputeMinByBlock(const std::vector<int>&v, std::size_t blockSize)
{
    MinByBlock res;
    res.minUntilHere.resize(v.size());
    res.minStartingHere.resize(v.size());
    for (std::size_t i = 0; i < v.size(); i += blockSize) {
        const auto blockBegin = v.begin() + i;
        const auto blockEndIndex = std::min(i + blockSize, v.size());
        const auto blockEnd = v.begin() + blockEndIndex;

        ComputeMinUntilHere(blockBegin, blockEnd, res.minUntilHere.begin() + i);
        ComputeMinUntilHere(std::make_reverse_iterator(blockEnd),
                            std::make_reverse_iterator(blockBegin),
                            std::make_reverse_iterator(res.minStartingHere.begin() + blockEndIndex));
    }
    return res;
}

Demo

You may notice than minUntilHere and minUntilHere are similar and just depends if you iterate from left to right or right to left.

ComputeMinUntilHere do the job for an entire range.

ComputeMinByBlock split the vector by independent blocks to fill result by block.

Abhishek Bansal · Accepted Answer · 2016-08-05 16:11:29Z

0

In the general case you cannot hope to fill the arrays in a single pass.

For example, if the block size is N (entire array), then to fill the entry MinUntilHere[i], you need to have looked at all items before i and to fill the entry MinStartingHere[i] you need to have looked at all items after i.

answered Aug 5, 2016 at 16:11

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

2 Comments

Daniel Over a year ago

this is the reason im using recursion. I can have a list L and do something like Min(pos) = if( pos >= |L| ) return INF; else return min(L[pos], Min(pos+1);

Jarod42 Over a year ago

One pass by array is sufficient BTW, so a total of 2 passes.

Daniel · Accepted Answer · 2016-08-06 03:44:10Z

Sorry guys, but I was able to find a linear solution (running the array just once) with code much smaller. This is the solution:

int fill(int pos = 0){

    if(pos >= |A|) return INF;

    int mod = pos % b;

    if(mod == 0){
        MinUntilHere[pos] = A[pos];
        MinStartingHere[pos] = min(A[pos], fill(pos + 1));
        return fill(pos + bsize);
    }
    else if(mod == bsize - 1){
        MinUntilHere[pos] = min(MinUntilHere[pos-1], A[pos]);
        return MinStartingHere[pos] = A[pos];
    }
    else{
        MinUntilHere[pos] = min(MinUntilHere[pos-1], A[pos]);
        return MinStartingHere[pos] = min(A[pos], fill(pos + 1));
    }

}

It works like this:

If I'm starting the block, set MinUntilHere as the A[pos] element, and make the MinStartingHere[pos] as the minimum of A[pos] and the return of fill(pos + a);
If It's not start nor end of a block, just make MinUntilHere[pos] = min(A[pos], MinUntilHere[pos-1]) and for the MinStartingHere, set him as the minimum between A[pos] and fill(pos+1) and return him (to the previous recursion)
If it's a block end, do the same for MinUntilHere, and for MinStartingHere, just set it as A[pos] and return it to the previous recursions.

An important detail is that when you start the block, you call a lot of recursions and then come back to the beginning of that block with the value for MinStartingHere, and AFTER that you call the method for pos + b, that means it will start to compute a new block after finishing the current one.

Thanks for the help anyway :)

Collectives™ on Stack Overflow

Set array min forward and backward via recursion

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related