Problem Brief

Count Triples with Difference

INTERNOA

To view the original problem statement, pls check out the source image below 🐰

Imagine you have an empty collection of numbers, and you're given a list of instructions to add or remove numbers from this collection. Your task is to follow these instructions carefully and, after each one, count how many special groups of three numbers (we call them "triples") can be made from the numbers in your collection.

Here's how a triple works: you need to pick three numbers, let’s call them x, y, and z. For them to count as a triple, the difference between x and y must be the same as the difference between y and z. This means that if you rearrange the numbers correctly, they should form a nice pattern like x, y, z.

For each instruction, you either add a new number to your collection or remove all instances of a specific number from it. After every single instruction, you have to check how many triples you can make with the current set of numbers.

The story has a few rules to keep things interesting:

The numbers involved are very large and can range from extremely negative to extremely positive.

When you're asked to remove a number, you can be sure that the number is actually in the collection—no need to worry about trying to remove something that isn’t there.

Finally, no matter how many triples you end up counting, the result will always be small enough to fit in a standard counting device.

Your ultimate goal is to create a list of these counts after processing each instruction, showing how the number of possible triples changes as you add or remove numbers.

1Example 1

Input

queries = ["+4", "+5", "+6", "+4", "+3", "-4"], diff = 1

Output

[0, 0, 1, 2, 4, 0]

Explanation

🐡 To view the original example explanation, pls check out the source image below. Once upon a time, there was a list of numbers that started out completely empty. Each day, someone would give a set of instructions on what to do with the list, and your job was to follow those instructions carefully. One day, the instructions were as follows: Add the number 4 to the list. Now the list had just one number: [4]. Since there weren't enough numbers to make a group of three (a triple), you wrote down a 0 as the answer. Add the number 5 to the list. Now the list looked like this: [4, 5]. Still, there weren't enough numbers to form a triple, so you wrote down another 0. Add the number 6 to the list. The list now contained [4, 5, 6]. This was exciting because with these three numbers, you could make a special triple where the difference between each pair of numbers was the same: (6, 5, 4). You proudly wrote down 1 as the answer. Add another 4 to the list. Now the list had [4, 5, 6, 4]. With this new addition, you could create the triple (6, 5, 4) in two different ways! This meant the count of triples doubled, so you wrote down 2. Add the number 3 to the list. The list grew to [4, 5, 6, 4, 3]. This was a special moment because now there were even more ways to create triples: both (6, 5, 4) and (5, 4, 3) could be made twice each! You excitedly wrote down 4 as the answer. Remove all the 4s from the list. With a bit of sadness, you removed both 4s, leaving the list as [5, 6, 3]. Unfortunately, this meant there were no more triples to be found, so you had to write down 0 as the final answer. And so, at the end of the day, the answers you collected were [0, 0, 1, 2, 4, 0], showing how the list of numbers evolved and how many triples could be formed after each instruction.

Constraints

Limits and guarantees your solution can rely on.

🐥🧡🐝