# Optimization of algorithm

Question:
There are N soldiers standing in a straight line with ID 1 to N: [1,2,3,4,5]

You are given array of IDs of length K in the order they are called : [3,1,2,1]

When a ID is called the soldiers with that ID will attack the enemy and he will do the same damage as number of soldiers infront of him and will stand in front of the line.

When 3 is called, he will do 2 damage, and stand in front of the line : [3,1,2,4,5]

When 1 is called he will do 1 damage: [1,3,2,4,5]

When 2 is called he will do 2 damage: [2,1,3,4,5]

When 1 is called he will do 1 damage: [1,2,3,4,5]

You have to return the damages done in order: Result: [2,1,2,1]

I know how to solve this question in O(NK) which is simply by modifying the array for each query but I am not sure how to optimize it.

• Where did you encounter this question? Can you credit the original source? Note that we require you to provide attribution for all material that is copied or originally written by others: cs.stackexchange.com/help/referencing. Does it indicate what running time is required?
– D.W.
Mar 28, 2023 at 3:47
• I got this question in an online exam for interview. It didn't mention what time complexity is expected but constraints was 10⁵ for N and K, so I think they expect ≤ O(nlogn) Mar 28, 2023 at 4:58
• Please edit the question to describe what approaches have you already considered. Why do you say "soldiers with that ID" - surely there can only be one soldier with that ID, right?
– D.W.
Mar 28, 2023 at 5:15
• Hint: can you use some data structure here, which tells you ranks of a given number ? Mar 28, 2023 at 5:23
• en.m.wikipedia.org/wiki/Order_statistic_tree Mar 28, 2023 at 7:18

Generally, if a soldier was called out before, its position in the line equals the number of distinct soldiers between the current and the previous callout. This is because of the fact that after a callout of a soldier, its position equals $$1$$, and this number will increase by $$1$$ after each new callout of another soldier standing behind him. So this problem is explicitly converted to: "How to count the number of distinct elements in a subarray?" which I would refer to Answer queries about the number of distinct numbers in a given range or Is it possible to query number of distinct integers in a range in O(lg N)?.
To find the answer for the first call of any soldier, you can append the reversed index array to the front. According to your provided example, the finalized array would be $$A = [5, 4, 3, 2, 1, 3, 1, 2, 1]$$
• For the first call out, soldier $$3$$'s corresponding position in $$A$$ are $$3$$ and $$6$$ (assume that $$A$$ is 1-indexed). The subarray between them is $$[2, 1]$$, and its number of distinct values equals $$2$$.
• For the second call out, soldier $$1$$'s corresponding position in $$A$$ are $$5$$ and $$7$$. The subarray between them is $$[3]$$, and its number of distinct values equals $$1$$.
• For the third call out, soldier $$2$$'s corresponding position in $$A$$ are $$4$$ and $$8$$. The subarray between them is $$[1, 3, 1]$$, and its number of distinct values equals $$2$$.
• For the fourth call out, soldier $$1$$'s corresponding position in $$A$$ are $$7$$ and $$9$$. The subarray between them is $$[2]$$, and its number of distinct values equals $$1$$.