Find 2nd previous minimum in Array -> Interview Problem

6 years ago, # |

I'm not sure if it exists O(n) solution.

→ Reply

6 years ago, # |

Anything better,than O(N^2) solution ?

→ Reply

6 years ago, # ^ |

I can tell you a treap solution if you want.

→ Reply

6 years ago, # ^ |

Yes Tell ?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Okay. So you represent the numbers as a pair (number, index). Now for each number you want to find the second maximum index from the pairs with number < current number. This can be done with treap. Just split with current number or perform a standard search for the second maximum index in the part with keys < current number.

→ Reply

6 years ago, # ^ |

"standard search for the second maximum index in the part with keys" — wouldn't it lead to O(n^2)?

→ Reply

6 years ago, # ^ |

I doubt about it's complexity ?

→ Reply

6 years ago, # ^ |

I meant keep the first and second max in the subtree for every node and then split and take the second max.

→ Reply

Mama_Bullki

6 years ago, # ^ |

Build a sparse table of the given array for range minimum queries. Then for each index the answer could be found using two binary searches. This gives you O(n log n) time and space complexity.

→ Reply

6 years ago, # ^ |

I have no idea, how two Binary search is going to work here ? Please take care, I need previous second element by Order from current index.

→ Reply

Mama_Bullki

6 years ago, # ^ |

Find such an index i that min(a[i], .., a[cur - 1]) < a[cur] but min(a[i + 1], ..., a[cur - 1]) > = a[cur]. Thus a[i] — previous first element that is less then the current one.
Find such an index j such that min(a[j], ..., a[i - 1]) < a[cur] but min(a[j + 1], ..., a[i - 1]) > = a[cur]. a[j] is the answer for current element.
Implementation

→ Reply

6 years ago, # |

Are you familiar with Sorted Trees?

→ Reply

6 years ago, # ^ |

Yes ?

→ Reply

6 years ago, # ^ |

Then you can make it in O(n*logn)

→ Reply

6 years ago, # ^ |

How ?

→ Reply

6 years ago, # ^ |

← Rev. 6 →

You put element into it. Then try to get two steps(as you need second lesser element): downleft+right/left, if there less then 2 elements — go up-and-left or up-and-up in the tree (this is logn operation). If you succeeded — found some element there — this is your answer. Else return zero for this element.

→ Reply

6 years ago, # ^ |

The answer seems interesting, can you explain me it in Detail.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Nice point. Pardon me, I misunderstood the problem. I thought 2nd lesser element must be by value, but examples suggest you need 2nd lesser element by order. No trees needed — take a look at comments lower — I'd guess it would be of more use to stick to a stack.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Though you can solve it using sorted tree this way: you can iterate through element in reversed order (from last to first) and:

Add current element to tree
Paint every element bigger then current
Take elements bigger then current out of tree — current element is the answer for them
Take next element in backward order.
If no elements left (you iterated to the first) — every vertex left in tree has no 2nd min and answer for them is 0.

→ Reply

mindrolin

6 years ago, # |

Hi AZ01, I've got an O(n log n) algorithm which is very easy in implementation because it doesn't require any trees. It uses the trick with a stack about which you've mentioned. I've just developed it a bit. My idea is to go through the array once and remember previous smaller element with maximum index. Simultaneously, you save queries about previous 2nd element. Then, in the second loop, you just answer these queries. My implementation is below. I'm not sure if it's clear so tell me if you don't catch it.

// Szymon Golebiowski 2019
#include <bits/stdc++.h>
using namespace std;
constexpr pair<int, int> NONE = {-1, -1};

class increasing_stack_t {
  public:
    vector<pair<int, int>> s;

    void updateStack(int value, int index) {
        while (!s.empty() && value <= s.back().first)
            s.pop_back();
        s.push_back({value, index});
    }

    pair<int, int> lastLower(int value) {
        if (s.empty())
            return NONE;
        auto it = lower_bound(s.begin(), s.end(), make_pair(value, 0)) - 1;
        if (it >= s.begin())
            return *it;
        return NONE;
    }
} previous;

int main() {
    pair<int, int> a;
    int n;
    cin >> n;
    vector<int> values(n), results(n, 0);
    vector<vector<pair<int, int>>> queries(n);

    for (int i = 0; i < n; i++) {
        cin >> values[i];
        if (NONE != (a = previous.lastLower(values[i])))
            queries[a.second].push_back({values[i], i});
        previous.updateStack(values[i], i);
    }

    previous.s.clear();
    for (int i = 0; i < n; i++) {
        for (auto &el : queries[i])
            if (NONE != (a = previous.lastLower(el.first)))
                results[el.second] = a.first;
        previous.updateStack(values[i], i);
        cout << results[i] << " ";
    }
    cout << endl;

    return 0;
}

→ Reply

6 years ago, # ^ |

Hi mindrolin

The Approach work's fine. But I think when the Array in strictly decreasing, the solution will work in O(n^2) as the function update_stack can take upto max O(n).

→ Reply

radoslav11

6 years ago, # ^ |

Not really, as in update_stack at each step you pop an element and you cannot pop more than n elements (as every element you have pushed in the stack will be removed exactly once).

One update_stack can have O(n) complexity but the overall complexity will remain O(n).

→ Reply

6 years ago, # ^ |

Yes, Sorry for misunderstanding.

But what about last_lower() function, The worst case of using lower_bound on Array is O(n). I still doubt about it's complexity. I think it's greater than O(nlogn) and less than O(n*n);

→ Reply

radoslav11

6 years ago, # ^ |

Lower_bound for array is O(logn) — it's O(n) for std::set. The complexity of the above solution is O(nlogn).

→ Reply

AghaTizi

6 years ago, # |

← Rev. 2 →

Consider p_i to be the maximum index that p_i < i and a_{p_i} < a_i. This can be done in O(n) using a stack.

Consider S_i to be the set of indices like j that p_j = i. Add all elements of S_i behind i and color them red. So like for array [2, 1, 4, 3, 5], p = [0, 0, 2, 2, 4], the new array becomes like this: [2, 4r, 3r, 1, 4, 5r, 3, 5]. (by 4r I mean a red 4).

Construct p for the new array in O(n). The answer is p of red elements! It's easy to prove that so I'll leave it up to you.

→ Reply

6 years ago, # ^ |

← Rev. 3 →

-10

Could you elaborate this approach a little more, please. I can't make it together.

How can you produce p in O(n) using stack? (Or where to look if its standard problem)
Looks like p = [0, 0, 2, 2, 4] is prev-min-by-value, and for array [2, 1, 4, 3, 5 ] that leads answer ans = [0, 0, 1, 1, 3]. At first I thought this is what TS asked for, but then realized problem is asking for a prev-min-by-order, and right answer should be [0, 0, 2, 2, 4]. Am I getting it right? If so, can you solution be tweaked to do this kind of min-search lineary?

→ Reply

AghaTizi

6 years ago, # ^ |

This
I don't really understand what you're saying. I've written the definition of p!

→ Reply

6 years ago, # ^ |

It's really hard to understand, How you have created p and new Array(O(n)). Can you elaborate the steps by taking an Example?

→ Reply

AghaTizi

6 years ago, # ^ |

Bashca has coded the same approach below.

→ Reply

6 years ago, # |

you can use solution to previous, two times.

→ Reply

6 years ago, # ^ |

I don't know ,How that is going to work ?

→ Reply

6 years ago, # ^ |

+10

this is my implementation, in the second time, give priority to those who had their minimum in the current element. O(n).

→ Reply

pajenegod

6 years ago, # ^ |

About the push back on line 32.

Don't know why you would push back something that essentially is a query onto the stack. If I understand the algorithm correctly then I think you could/should just remove that line. But maybe you see it in a different way.

→ Reply

6 years ago, # ^ |

oh, yeah. The code is correct but, that line is unnecessary. thanks you.

→ Reply

MotaSanyal

6 years ago, # ^ |

Bashca can you please explain how does this code has a time complexity of O(n). I am especially confused with the 2nd for loop that you have used after clearing the vector s. It has a nested for loop that runs from 1 to g[i]. If I am not wrong, g does store the index of the 1st minimum of each element in the array.

→ Reply

6 years ago, # ^ |

MotaSanyal the nested for loop doesn’t run from 1 to g[i], it runs for all element in g[i], they are O(n) for all i. for auto

→ Reply

MotaSanyal

6 years ago, # ^ |

← Rev. 2 →

Can you please explain your idea ? I am not getting it

→ Reply

6 years ago, # ^ |

Ok, in the first part we calculate previous minimum for all element, in the second part we calculate the previous element for all element with index < to current minimum. This is easy, only process the answer for element before his minimum previous element.

→ Reply

MotaSanyal

6 years ago, # ^ |

Actually I am not much accustomed to the syntax of c++ as I code in Python. If u could kindly explain what does g[i] stores, it will be helpful for me. Is g[i] a vector?

→ Reply

6 years ago, # ^ |

Yes, g[i] is a vector.

→ Reply

6 years ago, # ^ |

I appreciate that you ask, and that you do not give me votes against if you did not understand. :)

→ Reply

6 years ago, # ^ |

Just for Knowledge Purpose,

Why you have implemented stack using Array (why not Stack STL itself). Do implementing Stack using Array create any Difference ?

→ Reply

6 years ago, # ^ |

It’s not difference. I prefer vector because it has []

→ Reply

6 years ago, # ^ |

down votes? really?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Yep. Very "constructive" discussion. And "pedagogic" reaction.

→ Reply

komolakanto

6 years ago, # |

Could you please define 2nd previous minimum? I don't understand why in your first example, the 2nd previous minimum for 7 is 3 or for 10 or 8 is 1. How can 1 ever be a 2nd minimum if there is only one 1 in the array?

→ Reply

6 years ago, # ^ |

Example : A = [1,10,15,8,12] res= [0,0,1,0,10];

for value 12, the 2nd previous minimum is 10 not 1, as After 8, 10 is smaller than 12. Actually you have to traverse in backward direction from current index and return 2nd minimum(not global(0 to i-1)).

→ Reply

komolakanto

6 years ago, # ^ |

In that case, a balanced binary tree seems like a good approach. Just adding a function to find the 2nd minimum each time.
Can't see how this can be done using a stack in O(n). Even if minimums are mapped in constant time, they would keep changing.
I hope you find the O(n) implementation someday and share it with us.

→ Reply