CODEWITHSUNDEEP
pythonalgorithmdata-structuresstack
Krishnavamsi
Krishnavamsi

Reputation: 31

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

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.

Upvotes: 2

Views: 48

Answers (2)

Maurice Meyer
Maurice Meyer

Reputation: 18106

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]

Upvotes: 1

hidden
hidden

Reputation: 192

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)

Upvotes: 0

Related Questions