•Article•6 months ago

Two pointers technique

The Two Pointers technique is a strategy commonly used in computer science and programming for solving problems involving arrays or sequences. It involves using two pointers that traverse the array or sequence from different positions, often moving in opposite directions or at different speeds. This technique is particularly useful for solving problems related to searching, optimization, or manipulation of arrays efficiently.

Here's a breakdown of how the Two Pointers technique works:

Initialization: Initially, you set up two pointers, usually at different positions within the array or sequence.
Movement: You iteratively move the pointers based on certain conditions until they meet or reach a specific condition. The movement of pointers can be controlled based on the problem requirements. For example, one pointer might move faster than the other, or they might move in opposite directions.
Condition Checking: At each step of iteration, you check certain conditions based on the problem requirements. These conditions often determine whether to move the pointers, update some variables, or perform other operations.
Termination: The process continues until one or both pointers reach the end of the array or sequence, or until some other termination condition is met.

The Two Pointers technique is especially useful in problems that involve searching for pairs or subarrays that meet specific criteria, finding optimal solutions, or manipulating sequences efficiently without using nested loops. It often provides a more efficient solution compared to brute-force approaches, especially for problems with linear or logarithmic time complexity requirements.

Huseyn and Yaroslav are playing a card game. There are n cards laid out in a row on the table, each with a different number written on it. The players take turns. Huseyn starts the game. On each turn, a player can take either the leftmost or the rightmost card. The player will always choose the card with the highest number. The game ends when there are no cards left on the table. Find the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Input. The first line contains the number of cards $n (1 \leq n \leq 10000)$ on the table. The second line contains $n$ positive integers, each indicating the number on a card. All numbers are not greater than $1 0^{9}$ .

Output. Print the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Open problem

Huseyn arranged $n$ cards in a row with numbers $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . Then he collected them and rearranged them in a different order: $a_{1}, a_{3}, a_{5}, ..., a_{6}, a_{4}, a_{2}$ . This is the sequence he gave to Yaroslav. Your task is to help Yaroslav restore Hussein's original sequence.

For example, if Yaroslav received the sequence $(2, 4, 9, 4, 7, 6)$ , then he should return the sequence $(2, 6, 4, 7, 9, 4)$ to Huseyn.

Input. The first line contains one integer $n (1 \leq n \leq 10000)$ , representing the number of cards. The second line contains $n$ positive integers written on the cards. All numbers are no greater than $1 0^{9}$ .

Output. Print Huseyn's original sequence.

Open problem

Huseyn has a string consisting of characters $0$ and $1$ . To entertain himself, he came up with the following game. Huseyn can perform one of two operations on the string:

append $0$ to the left end, and $1$ to the right end;
append $0$ to the right end, and $1$ to the left end;

For example, from the string $010$ , Huseyn can obtain $00101$ or $10100$ .

You are given a string obtained after all of Huseyn's operations (it is possible that he did not perform any operation). Determine the smallest possible length the string could have initially had.

Input. A single string of length no more than $1 0^{5}$ , consisting only of characters $0$ and $1$ .

Output. Print the smallest possible length of the string that Huseyn could have initially had.

Open problem

Let's consider the input string $s$ — the resulting string after Huseyn has performed all operations. Initialize two pointers: $i = 0$ at the start of the string and $j = n - 1$ at the end.

If $s_{i} \neq = s_{j}$ , then the characters at the ends of the string are different: either $0$ on the left and $1$ on the right, or $1$ on the left and $0$ on the right. This means the previous string could have been extended by applying one of the specified operations. In this case, move both pointers $i$ and $j$ one position towards each other and check again whether the substring $s [i ... j]$ could have been obtained through Huseyn's operations.

As soon as the current substring $s [i ... j]$ satisfies $s_{i} = s_{j}$ , it can no longer be produced by the given operations. Print its length — this is the original string that Huseyn had.

Example

Let's perform Huseyn's operations in reverse order.

The string $s = "1"$ was originally the one Huseyn had.

Read the input data.

cin >> n >> x;
v.resize(n);
for (i = 0; i < n; i++)
  cin >> v[i];

Sort the input array.

sort(v.begin(), v.end());

Iterate through the values $k = 0, 1, ..., n - 3$ .

for (k = 0; k < n - 2; k++)
{

Find a pair of indices $(i, j)$ such that $i > k$ and $v_{i} + v_{j} = x - v_{k} (i < j)$ . Initialize the indices $i$ and $j$ .

  i = k + 1; j = n - 1;
  s = x - v[k];

Use the two-pointer technique to find the desired pair $(i, j)$ .

  while (i < j)
  {
    if (v[i] + v[j] == s)
    {

If the pair $(i, j)$ is found, print the desired triplet of numbers $(v_{k}, v_{i}, v_{j})$ .

      printf("%d %d %d\n", v[k], v[i], v[j]);
      return 0;
    }

If $v [i] + v [j] < s$ , then move pointer $i$ one position to the right;

If $v [i] + v [j] > s$ , then move pointer $j$ one position to the left;

    if (v[i] + v[j] < s) i++; else j--;
  }
}

If the triplet of numbers is not found, print $- 1$ .

cout << -1 << endl;

The interval $A [i ... j]$ will be called good if the numbers in it lie in the range $[A_{i}; 2 \cdot A_{i}]$ inclusive (meaning $A_{j} \leq 2 \cdot A_{i}$ ).

We implement a sliding window using two pointers $i$ and $j$ and maintain it so that the current interval $[i ... j]$ is good, while the interval $[i ... j + 1]$ is bad.

For example, for the following sequence:

the intervals $[2; 2], [2; 3], [2; 4]$ , and $[2; 5]$ are good.
the intervals $[2; 6], [2; 7]$ are bad.

If $A_{j} \leq 2 \cdot A_{i}$ , extend the current interval to $А [i ... j + 1]$ . Otherwise, reduce it to $А [i + 1... j]$ . Before moving the pointer $i$ , print the number of elements lying between $A_{i}$ and $2 \cdot A_{i}$ inclusive. It equals $j - i$ .

The algorithm’s complexity is linear, i.e. $O (n)$ .

Example

Let’s consider the movement of pointers for the given example.

For the given condition $A_{j} \leq 2 \cdot A_{i}$ , so we move the pointer $j$ forward.

Now $A_{j} > 2 \cdot A_{i}$ . We need to move the pointer $i$ forward. However, before moving it, print the number of elements lying between $A_{i}$ and $2 \cdot A_{i}$ inclusive. It is equal to $j - i = 6 - 2 = 4$ .

Move $j$ forward until $A_{j} \leq 2 \cdot A_{i}$ .

Now $A_{j} > 2 \cdot A_{i}$ . Print the answer for $i = 3$ (it equals $j - i = 8 - 3 = 5$ ) and increase $i$ by $1$ .

Store the hotel costs in the $a$ array. We’ll call the interval $[i ... j]$ good if the sum of hotel costs within it does not exceed $m$ .

Let’s implement a sliding window using two indices $i$ and $j$ , and maintain it so that the current interval $[i ... j]$ is good. Let $s$ be the sum of hotel costs within the interval $[i ... j]$ . If $s + a [j + 1] \leq m$ , then expand the current interval to $a [i ... j + 1]$ . Otherwise, shrink it to $a [i + 1... j]$ . Find the maximum among the costs of all considered good intervals.

Example

Consider the movement of pointers for the given example.

When $i = 0, j$ moves forward until the sum of numbers in the interval $[i ... j]$ does not exceed $m = 12$ . Stop at the interval $[0...3]$ because the sum there is equal to $10$ , while the sum in the interval $[0...4]$ is equal to $15$ .
When $i = 1$ , we cannot move $j$ forward because the sum in the interval $[1...4]$ is equal to $13$ .
When $i = 2$ move $j$ forward to the interval $[2...4]$ .

The maximum value among all good intervals is equal to $12$ and is achieved in the interval $[2...4]$ .

Read the input data.

scanf("%d %lld", &n, &m);

Initialize the variables:

in $res$ , the maximum value among the costs of all processed good intervals is computed;
in $s$ , the sum of numbers in the current interval $[i ... j]$ is maintained. All the numbers in the current interval $[i ... j]$ are stored in the queue $q$ ;

s = res = 0;

Process the hotel costs sequentially.

for (i = 0; i < n; i++)
{

Read and add the cost $v a l$ of the current hotel to the queue.

  scanf("%d", &val);
  q.push(val);

Update the sum $s$ within the interval. All elements of the current interval are stored in the queue $q$ .

  s += val;

If the sum of numbers in the current interval exceeds $s$ , we remove elements from the beginning of the interval.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Compute the maximum value $res$ among the sums of elements in good intervals (where the cost of hotels does not exceed $m$ ).

  if (s > res) res = s;
}

Print the answer.

printf("%lld\n", res);

Let's implement a sliding window using two pointers, $i$ and $j$ . For each fixed $i = 1, 2, ...$ , expand the interval $[i ... j]$ as much as possible so that the sum of its elements does not exceed $x$ . In other words, for each $i$ , search for the largest possible $j$ such that the sum of elements in the interval $[i ... j]$ does not exceed $x$ , while the sum of elements in the interval $[i ... j + 1]$ exceeds $x$ .

Let $s$ be the sum of numbers in the interval $[i ... j]$ . If $s + a [j + 1] \leq m$ , expand the interval to $[i ... j + 1]$ . Otherwise, shrink it to $[i + 1... j]$ . Count the number of intervals with a sum of $x$ .

Example

Let's examine the movement of the pointers for the given example.

$i = 0$ , $j$ moves forward until the sum of the numbers in the interval $[i ... j]$ exceeds $x = 7$ . We stop at the interval $[0...2]$ , since the sum of the numbers in it is $7$ , while in the interval $[0...3]$ , the sum of the numbers is already $9$ .
$i = 1$ , $j$ moves forward to $3$ . The sum of the numbers in the interval $[1...3]$ is $7$ , while in the interval $[1...4]$ , it is already $14$ .
$i = 2$ , the considered interval is $[2...3]$ . The sum of the numbers in it is $3$ , but we cannot move the index $j$ forward because the sum of the numbers in the interval $[2...4]$ is $10$ , which is greater than $x = 7$ .
$i = 3$ , the considered interval is $[3...3]$ . The sum of the numbers in it is $2$ , but we cannot move the index $j$ forward because the sum of the numbers in the interval $[3...4]$ is $9$ , which is greater than $x = 7$ .
$i = 4$ , the considered interval is $[4...4]$ . The sum of the numbers in it is $7$ .

The number of subarrays with a sum of $x = 7$ is $3$ . They start at indices $0, 1$ , and $4$ .

Ziya will take part in the sequence competition tomorrow. The number $x \geq 0$ is called the top of some sequence if the sequence $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ is a subsequence of this sequence. The strength of each sequence is considered to be its largest vertex.

Tomorrow all students will go to the competition and the winner of the strongest sequence will be the winner. Zia has the sequence $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . He wants to take over the competition scoring system and remove sequences from it with more force than himself. However, Zia does not know the power of his own consistency, but really wants to win. Help him calculate the strength of his own sequence.

Input. The first line contains the number $n (1 \leq n \leq 1 0^{5})$ of numbers in Zia's sequence. The next line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ — the elements of the sequence.

Output. Print one number — the strength of the given sequence.

Open problem

Let $v$ be the input array of numbers. Initialize the pointers $i = 0$ at the beginning of the array and $j = n - 1$ at the end of the array. We will count the strength of the sequence in the variable $k$ . Initially, set $k = 1$ .

While the pointers $i$ and $j$ do not meet, perform the following actions:

Move the pointer $i$ one position to the right if it does not point to the number $k$ .
Move the pointer $j$ one position to the left if it does not point to the number $k$ .
If both pointers point to the number $k$ , increase $k$ by one and move each pointer one position in the corresponding direction.

After the algorithm completes, the answer will be the value $k - 1$ .

Example

Consider the second test. Initialize the pointers. Move the pointer $i$ to the right and the pointer $j$ to the left until they both point to the number $1$ .

Move the pointer $i$ to the right and the pointer $j$ to the left until they both point to the number $2$ .

The pointers meet, we stop the algorithm. The answer will be the value $k = 2$ .

Today, $n$ programmers have gathered. Each programmer has a rating that reflects his strength. The rating is an integer between $0$ and $1 0^{9}$ . Your rating as a programmer is $m$ . From all the programmers gathered today, you want to choose two for your team. They must be selected in such a way that their total rating is maximized but does not exceed your rating, as you want to be the leader of this team.

Input. The first line contains two integers: $n (2 \leq n \leq 1 0^{5})$ — the number of programmers, and $m (0 \leq m \leq 1 0^{9})$ — your rating. The second line contains $n$ integers $r_{1}, r_{2}, ..., r_{n} (0 \leq r_{i} \leq 1 0^{9})$ — the ratings of the programmers.

Output. Print a single integer — the maximum sum of the ratings of the selected programmers, or $- 1$ if it is impossible to find such two people.

Open problem

Bessie the cow, always a fan of shiny objects, has taken up a hobby of mining diamonds in her spare time! She has collected $n$ diamonds of varying sizes, and she wants to arrange some of them in a display case in the barn.

Since Bessie wants the diamonds in the case to be relatively similar in size, she decides that she will not include two diamonds in the case if their sizes differ by more than $k$ (two diamonds can be displayed together in the case if their sizes differ by exactly $k$ ). Given $k$ , help Bessie determine the maximum number of diamonds she can display in the case.

Input. The first line contains $n (n \leq 1000)$ and $k (0 \leq k \leq 10000)$ . The next $n$ lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed $10000$ .

Output. Print the maximum number of diamonds that Bessie can showcase.

Open problem

First, compute the volume of water in the container formed by the outermost vertical lines, i.e., between the lines of the pair $(l, r) = (1, n)$ . Then, move the pointers $l$ and $r$ towards each other:

if $h_{l} < h_{r}$ , increase $l$ by $1$ ;
if $h_{l} \geq h_{r}$ , decrease $r$ by $1$ ;

The volume of water between the lines $l$ and $r$ is equal to $min (h_{l}, h_{r}) * (r - l)$ . Among all the calculated values, find the maximum.

The problem can be solved in $O (n^{2})$ . However, due to the constraint $n \leq 1 0^{5}$ , such a solution would result in a time limit exceeded (TLE). It is sufficient to iterate over the pairs of lines $(i, j)$ , where $1 \leq i < j \leq n$ , and for each such pair, calculate the volume of water they can hold. Among all the computed values, find the maximum volume.

Example

The container from the first test looks like this:

The maximum amount of water can be held between the lines $2$ and $9$ . The water level height is $7$ , and the volume of water is $7 \cdot 7 = 49$ .

Let the array $v$ store the identification numbers of the songs. Using two pointers, we will maintain a sliding window $[i; j]$ in which the songs do not repeat. In other words, all the songs in the segment $[i; j]$ are unique. The songs from this segment will be stored in a set $s$ . For each value of $i$ , we will try to extend the segment to the maximum possible length. That is, for a fixed $i$ , we will search for such a $j$ that in the segment $[i; j]$ the songs do not repeat, but in the segment $[i; j + 1]$ duplicates already appear.

When processing the current song at index $j + 1$ , there are two possible cases:

If the song $v_{j + 1}$ is not present in the segment $[i; j]$ , add it to this segment, extending it to $[i; j + 1]$ ;
If the song $v_{j + 1}$ is already present in the segment, shift the left boundary $i$ to the right until $v_{j + 1}$ disappears from the segment $[i; j]$ . Then, add $v_{j + 1}$ to the segment, extending it to $[i; j + 1]$ . With each shift of $i$ , remove the corresponding elements from the set $s$ ;

Among all possible segments $[i; j]$ with unique songs, find the maximum length. This will be the answer to the problem.

Example

Let’s consider how the segments with unique songs will change for the first example.

The length of the longest segment is $5$ .

Read the input data. The identification numbers of the songs are stored in the array $v$ .

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Maintain the segment $[i; j - 1]$ of unique songs (i.e., the songs from $v_{i}$ to $v_{j - 1}$ do not repeat). In the set $s$ , store the identification numbers of the songs from this segment. The variable $res$ tracks the length of the longest fragment with unique songs.

i = res = 0;
for (j = 0; j < n; j++)
{

Consider the current song at index $j$ . If it is already in the set $s$ , it will not be possible to extend the current segment $[i; j - 1]$ by including the $j$ -th song. In this case, we need to shift the left boundary $i$ , removing the song $v_{i}$ from the set $s$ , until the $j$ -th song disappears from the set $s$ .

  while (s.find(v[j]) != s.end())
  {
    s.erase(v[i]);
    i++;
  }

Add the $j$ -th song to the segment and, accordingly, to the set $s$ . Thus, the segment $[i; j]$ will not contain any repeated songs.

  s.insert(v[j]);

Among all possible segments $[i; j]$ , find the longest one. The length of the segment $[i; j]$ is $j - i + 1$ .

  res = max(res, j - i + 1);
}

Print the answer.

printf("%d\n", res);

List of problems

Comments (5)

azimzadenihad•5 months ago

thanks for all

Eltaj13•6 months ago

Thanks for the problems!

drizzy•6 months ago

Thanks for the problems! Will there be future topic contests like these ?

medv•6 months ago•2 revision

drizzy Thanks a lot if you liked it. By the way, problems "Competition of sequences", "The best team" and "Radio 106 FM" are taken from the past official Azerbaijan School Competitions

drizzy•6 months ago

medv Please continue this series of topic wise contests. Thanks

Loading

Just a moment, getting data from the server