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

A stack/deque problem
Автор hxano, история, 10 месяцев назад, По-английски

The problem goes as follows:

You are given an array a of N non-negative integers, indexed from 1 to N. Define prev(x) such that prev(x) is the largest integer that satifies both following conditions: prev(x) < x, and a[prev(x)] < x. Print prev(i) for each i from 1 to N.

This is a basic problem that can be solved using stacks. However, I've seen an interesting implementation that avoids data structures altogether. Here's the main code for it:

cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
a[0]=-inf;
for (int i=1; i<=n; ++i){
    int p=i-1;
    while (a[p]>=a[i]) p=sol[p];
    sol[i]=p;
}
for (int i=1; i<=n; ++i) cout<<sol[i]<<" "; cout<<"\n";
return 0;

It seems to me that this runs in O(n) on average, but I cannot find its worst-case complexity. I suspect it to be O(n^2) but have had no luck proving it so far (I once used this implementation in a practice problem and got TLEed). Any help would be greatly appreciated. Thanks!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

It is doing the same thing as the stack solution, using the sol array to keep the stack

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you have a proof for it?

    → Ответить
    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Proof of the complexity would be the same as for the stack. You do n pushes into the stack and each element is removed at most once, so the number of removals is at most n, thus the complexity is O(n).

      → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

not a proof, but if you clear the stack at the end, then number of iterations is exactly n

	int iterations = 0;
	for (int i=1; i<=n; ++i){
		int p=i-1;
		while (a[p]>=a[i]) p=sol[p], iterations++;
		sol[i]=p;
	}
	//clearing the stack at the end
	int p = n;
	while (p >= 1) p=sol[p], iterations++;
	assert(iterations == n);
→ Ответить