P#16 The last N elements

All problems are from https://www.dailycodingproblem.com/

 

My Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

Daily Coding Problem#16: The last N elements

Problem Description

 

Idea

My first approach is to use a List.

record orders to a list. inserting elements to the back takes constant time.

get_last(i) , List[-i] will do the job. Which will take contstant time too.

 

However, the last sentence of the task elarborates we have to be efficient in both time and space. How to be efficient in space? 

Since we need only the last maximum N values of the list, our minimum space complexity is O(N). 

So my idea is this -> Use deque.

 

deque is a data structure usually called as double-ended queue.

Insert/Deleting elements from front/back takes O(1) time. 

I knew this. However deque has another powerful feature.

Random Access takes O(1) time.

It implies that we can get the last ith element from the deque in O(1) time.

How does this work? One implemention to deque is partitioning constant-size arrays(possibly vectors). When insert, if it is needed, allocate a array and add it. (amortized O(1))

Since the size of arrays are constant, we can find the iterator of the nth element in constant time.

Check out this blog for details.

 

from collections import deque

dq = deque()

 

1. push back N-> dq.append(N)

2. pop back -> dq.pop()

3. push front N -> dq.appendleft(N)

4. pop front -> dq.popleft()

 

Implementation