Repeated element at top of the stack on basis of their second appearance

user_9552689 0
Viewed 37

I have an array which consist of duplicate elements e.g.

arr = [1, 2, 3, 0, 2, 1]

Now, I want to store elements in a stack in such a way that top of the stack will always give me an element which is repeated and it appear before all other repeated element which comes afterwards. for e.g.

arr = [1, 2, 3, 0, 2, 1, 3]
stack = [3, 1, 2]

Here, 1,2, and 3 are the repeated elements and 2 appear before all other repeated elements that's why it is at the top of stack, then 1 which comes before 3 then lastly 3

another example

arr = [1,2,0,2,3,0,1]
stack = [1, 0, 2]

you may assume elements are repeated only twice.

data-structures stack algorithm python
2 Answers

You could keep track of all unique elements elsewise add into the stack:

arr = [1, 2, 0, 2, 3, 0, 1]
unique = []
stack = []

for a in arr:
    if a not in unique:
        unique.append(a)
    else:
        stack.insert(0, a)
print(stack)

Out:

[1, 0, 2]
user_72168650

I see such an algorithm:

1. Find repeated elements
2. Iterate the initial list from the tail to the head
    2.1. Check if an element is in the repeated elements list
        2.1.1 If yes -> add this item to the new list
    2.2 break when len(newlist) == len(repeated_list)
user_147074300
Related