Find 2nd previous minimum in Array -> Interview Problem

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:05:20
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя AZ01

Find 2nd previous minimum in Array -> Interview Problem

Автор AZ01, история, 6 лет назад, По-английски

Hi, I am looking for O(n)(Better than O(N^2)) solution of this Problem. The problem is to find the 2nd previous minimum element in Array ,If there is no minimum value we can return 0 ;

Example : Array = [2,4,5,3,1,7,10,8]

Result =[0,0,2,0,0,3, 1,1]

Array = [1,2,3,4,2,3,7,8,2,1]

Result= [0,0,1,2,0,2,2,3,0,0]

All I know is, we can find previous minimum element in O(n) using a Stack. But I don't know how to solve for 2nd previous minimum. Any Suggestions?

Update :- I need previous minimum by order, have a close look at examples.

Update 2: : I found a O(n) solution given by Bashca && AghaTizi. You can see the implementation here or in Comment below.

Thanks for your contribution.

stack, #interview

AZ01
6 лет назад
58

Комментарии (50)

Показать архивные | Написать комментарий?

IhateProgramming

6 лет назад, # |

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

→ Ответить

AZ01

6 лет назад, # |

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

→ Ответить

IhateProgramming

6 лет назад, # ^ |

I can tell you a treap solution if you want.

→ Ответить

AZ01

6 лет назад, # ^ |

Yes Tell ?

→ Ответить

IhateProgramming

6 лет назад, # ^ |

← 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.

→ Ответить

agarus

6 лет назад, # ^ |

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

→ Ответить

AZ01

6 лет назад, # ^ |

I doubt about it's complexity ?

→ Ответить

IhateProgramming

6 лет назад, # ^ |

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

→ Ответить

Mama_Bullki

6 лет назад, # ^ |

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.

→ Ответить

AZ01

6 лет назад, # ^ |

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.

→ Ответить

Mama_Bullki

6 лет назад, # ^ |

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

→ Ответить

agarus

6 лет назад, # |

Are you familiar with Sorted Trees?

→ Ответить

AZ01

6 лет назад, # ^ |

Yes ?

→ Ответить

agarus

6 лет назад, # ^ |

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

→ Ответить

AZ01

6 лет назад, # ^ |

How ?

→ Ответить

agarus

6 лет назад, # ^ |

← 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.

→ Ответить

AZ01

6 лет назад, # ^ |

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

→ Ответить

agarus

6 лет назад, # ^ |

← 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.

→ Ответить

agarus

6 лет назад, # ^ |

← 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.

→ Ответить

mindrolin

6 лет назад, # |

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;
}

→ Ответить

AZ01

6 лет назад, # ^ |

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).

→ Ответить

radoslav11

6 лет назад, # ^ |

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).

→ Ответить

AZ01

6 лет назад, # ^ |

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);

→ Ответить

radoslav11

6 лет назад, # ^ |

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

→ Ответить

AghaTizi

6 лет назад, # |

← 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.

→ Ответить

agarus

6 лет назад, # ^ |

← 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?

→ Ответить

AghaTizi

6 лет назад, # ^ |

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

→ Ответить

AZ01

6 лет назад, # ^ |

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?

→ Ответить

AghaTizi

6 лет назад, # ^ |

Bashca has coded the same approach below.

→ Ответить

Bashca

6 лет назад, # |

you can use solution to previous, two times.

→ Ответить

AZ01

6 лет назад, # ^ |

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

→ Ответить

Bashca

6 лет назад, # ^ |

+10

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

→ Ответить

pajenegod

6 лет назад, # ^ |

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.

→ Ответить

Bashca

6 лет назад, # ^ |

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

→ Ответить

MotaSanyal

6 лет назад, # ^ |

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.

→ Ответить

Bashca

6 лет назад, # ^ |

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

→ Ответить

MotaSanyal

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Bashca

6 лет назад, # ^ |

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.

→ Ответить

MotaSanyal

6 лет назад, # ^ |

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?

→ Ответить

Bashca

6 лет назад, # ^ |

Yes, g[i] is a vector.

→ Ответить

Bashca

6 лет назад, # ^ |

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

→ Ответить

AZ01

6 лет назад, # ^ |

Just for Knowledge Purpose,

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

→ Ответить

Bashca

6 лет назад, # ^ |

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

→ Ответить

Bashca

6 лет назад, # ^ |

down votes? really?

→ Ответить

agarus

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

komolakanto

6 лет назад, # |

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?

→ Ответить

AZ01

6 лет назад, # ^ |

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)).

→ Ответить

komolakanto

6 лет назад, # ^ |

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.

→ Ответить

AZ01

6 лет назад, # ^ |

I think, I have to close the Blog Post. I found the O(n) solution coded in above comment by Fischer.

→ Ответить

NiKS001

6 лет назад, # |

One more way to solve this problem is using square root decomposition:

Divide the array into sqrt(n) blocks of size sqrt(n) each.
For each block you maintain the minimum element encountered
You can skip a block if the minimum is greater the current element

Total time complexity would be O(n*sqrt(n))

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 15:29:41 (k3).

Десктопная версия, переключиться на мобильную.

При поддержке