two pointers - Codeforces

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

До соревнования
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
13:51:43
Зарегистрироваться »

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

→ Трансляции

Leetcode Weekly 499 + Biweekly 181 Solution Discussion

aryanc403

До начала 33:46:42

Всё →

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

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

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

Всё →

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

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Всё →

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

→ Прямой эфир

Детальнее →

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

two pointers

Автор hollow, 14 лет назад, По-английски

In many problems i see the tag "two pointers". I assume its a technique. I dont have an idea on it can anybody give any type of reference. Thanks.

algorithm, two pointers

hollow
14 лет назад
29

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

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

goo.gl_SsAhv

14 лет назад, скрыть # |

← Rev. 5 →

+10

I will try to describe this method on example of a problem.
Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.
i and j our pointers, at first step i is points to the first element of a, and j points to the last element of b.

i = 0; j = b.size() - 1;

move first pointer one by one through the array a, and correct position of the second pointer if needed

while (i < a.size())
{
   while(a[i] + b[j] > X && j > 0) j--;
   if (a[i] + b[j] == X) writeAnswer(i, j);
   i++;
}

Also, there was the same question in Russian, maybe it can helps. link to google-translated version
http://mirror.codeforces.com/blog/entry/4136

→ Ответить

riadwaw

14 лет назад, скрыть # ^ |

In addition to post of goo.gl_SsAhv:
The feature of this method is that solutions are O(n) (n=b.size() using his terminology) despite of possibility of decreasing second pointer with O(n) while 1 iteration of outer cycle made. It's right because every pointer will change only O(n) times.

→ Ответить

harsh_verma

9 лет назад, скрыть # ^ |

amm... should it not be O(a.size()+b.size()) in worst case like if x=101 , a=1 2 5 7 8 100 , b= 1 2 3 4 47

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

and what if we have to find all the pairs that sums up to X ?

→ Ответить

kingofnumbers

13 лет назад, скрыть # ^ |

← Rev. 3 →

the same approach works as well, just continue moving your pointers and count the number of pairs.

actually the "writeAnswer" function in goo.gl_SsAhv code will be called for all such pairs

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

I guess in that case we need to do this : writeAnswer(i++,j--), right ?

→ Ответить

kingofnumbers

13 лет назад, скрыть # ^ |

← Rev. 3 →

no. this code works fine:


#include <iostream>
using namespace std;

int n,a[100001],b[100001];

void writeAnswer(int ii,int jj){
	cout<<a[ii]<<" "<<b[jj]<<endl;
}
int X;
int main(){
	cin>>n>>X;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	int i=0,j=n-1;
	while (i < n)
		{
			 while(a[i] + b[j] > X && j > 0) j--;
		 if (a[i] + b[j] == X) writeAnswer(i, j);
				 i++;
		}

	while(1); //pause
}

this code may not work when the array values is not unique, anyway the main point is to understand two pointers technique

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

i guess writeAnswer(i++,j--); thingy would also work provided all elements in the array are unique.

→ Ответить

kingofnumbers

13 лет назад, скрыть # ^ |

I don't think so, try it up and see why :)

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

← Rev. 2 →

can you think of a test case where my idea fails. Because for almost all inputs that i have, its working fine !

→ Ответить

kingofnumbers

13 лет назад, скрыть # ^ |

← Rev. 4 →

5 6
1 2 3 4 5
1 2 3 4 5

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

well, it gave me as expected, it gave me two pairs : 1,5 2,4

hence passed !

→ Ответить

kingofnumbers

13 лет назад, скрыть # ^ |

correct output:

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

i came up with this problem : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=515

it reminded me of almost the same algorithm as used here except it needs perhaps more than two pointers.

can you help me in figuring out how to approach above mentioned problem given in the link.

→ Ответить

goo.gl_SsAhv

13 лет назад, скрыть # ^ |

it is just a bruteforce. There is total 2^12 subsets, try all.

→ Ответить

ron2794

13 лет назад, скрыть # ^ |

is there any more efficient algorithm if input size is much larger than this complete search ?

→ Ответить

goo.gl_SsAhv

13 лет назад, скрыть # ^ |

← Rev. 2 →

answer can be vey big, so there is no big difference. there is O(sum * n * n + total_size_of_answer) dfs like approach. vertex is a pair (sum, last_used_number). in this graph you have to find all paths between two vertices, but the anwser can be very big as it mentioned above.

→ Ответить

shikhorroy

11 лет назад, скрыть # ^ |

← Rev. 2 →

Is there any condition for arrays 'a' and 'b', like all the elements will be unique or others? If not, then how your given code will give correct ans under the following condition:

a.size() = 6;
X = 6;
a[] = {1, 2, 3, 4, 5, 6};
b[] = {1, 2, 3, 5, 5, 6};

@goo.gl_SsAhv

→ Ответить

Gassa

11 лет назад, скрыть # ^ |

Why don't you try it for yourself?

If you mean "why the possible answer i=0, j=3 is not displayed", well, be more specific next time, and it's because the original problem is to find any one pair of indices. What if the problem asks to find all such pairs?

The maximum running time is O(mn) instead of O(m+n), e.g., when X=2 and all elements of a and b are equal to 1. So we can actually use the straightforward algorithm (for i, for j, check a[i]+b[j]) instead of the two pointers method.
The above bound can be improved to O(s) where s is the number of pairs in the answer. You can still patch the algorithm (while equal, go up and down) to make it output all s pairs in O(s).
If you need the number of pairs and not the pairs themselves, it can also be done in O(m+n) by maintaining highest and lowest possible values of j instead of a single variable.

→ Ответить

CodingKnight

8 лет назад, скрыть # ^ |

And since X - a[ i ] is independent of the second pointer j, your two-pointers example can be rewritten as follows.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int m, n, X; cin >> m >> n >> X; int a[ m + 1 ], b[ n + 1 ]; 
    
    for( int i = 1; i <= m; cin >> a[ i++ ] );

    for( int j = 1; j <= n; cin >> b[ j++ ] );
    
    for( int i = 1, j = n; i <= m; i++ )
    {
        int Y = X - a[ i ];
        
        while( j >= 1 and b[ j ] > Y )
            j--;
            
        if( j >= 1 and b[ j ] == Y )
            cout << i << ' ' << j << '\n';
    }
}

→ Ответить

mohammad74

7 лет назад, скрыть # |

If array elements are not distinct, the worst case is when all elements of both arrays are equal and the sum we are looking for is a[0] + b[0]. In this case all n² pairs of indices form the needed summation, thus the best approach is an O(n²) brute force, so an O(n) solution will not work.

→ Ответить

zed_b

7 лет назад, скрыть # ^ |

If you need the indices of all pairs, you may have O(n^2) results, so a O(n) is not possible, but if you need just how many index pairs there are, it's still solveable in O(n), just count how many there equal there are of a and b, and result is equalA*equalB.

→ Ответить

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

Время на сервере: 25.04.2026 03:43:18 (h1).

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

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