See the original problem on HackerRank.
Solutions
We will implement a class named DiscardDeck to encapsulate the solution. Below is the code to process the input and utilize this class in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
int main()
{
int N;
cin >> N;
DiscardDeck deck; // we'll implement this in a moment
int cmd, value;
while (N--)
{
cin >> cmd;
switch (cmd)
{
case 1:
cin >> value;
deck.discard(value);
break;
case 2:
deck.pick();
break;
case 3:
cout << deck.peek() << "\n";
break;
case 4:
cout << deck.peekSmallest() << "\n";
break;
}
}
}
|
Here is the same in Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def main():
import sys
input = sys.stdin.read
data = input().splitlines()
deck = DiscardDeck() # we'll implement this in a moment
N = int(data[0])
results = []
for i in range(1, N + 1):
command = data[i].split()
if command[0] == "1":
value = int(command[1])
deck.discard(value)
elif command[0] == "2":
deck.pick()
elif command[0] == "3":
results.append(deck.peek())
elif command[0] == "4":
results.append(deck.peekSmallest())
print("\n".join(map(str, results)))
if __name__=="__main__":
main()
|
The naive solution simply involves recalculating the smallest value each time an operation is performed. This approach requires a linear-time operation through the entire data structure every time to find the minimum:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class DiscardDeck
{
public:
void discard(int value)
{
m_data.push_back(value);
}
void pick()
{
m_data.pop_back();
}
int peek()
{
return m_data.back();
}
int peekSmallest() // O(N)
{
return *std::min_element(begin(m_data), end(m_data));
}
private:
std::vector<int> m_data;
};
|
The last test case is designed to populate the deck with a large amount of cards and then repeatedly retrieve the smallest value many times. This causes the solution to exceed the allowed time limits.
A logarithmic solution
A suboptimal working solution consists in using two data structures:
- a
vector for storing data
- a
multiset for keeping data in order
An element is added to both the main stack and the supporting structure to ensure that both peek and peekSmallest operations can be performed in constant time. However, the discard and pick operations have logarithmic time complexity due to the need to maintain the sorted order of the supporting structure. Also, it adds an extra data structure.
Here is the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class DiscardDeck
{
public:
void discard(int value) // O(logN)
{
m_mins.insert(value);
m_data.push_back(value);
}
void pick() // O(logN)
{
const auto back = peek();
m_mins.erase(m_mins.lower_bound(back));
m_data.pop_back();
}
int peek() // O(1)
{
return m_data.back();
}
int peekSmallest() // O(1)
{
return *begin(m_mins);
}
private:
std::vector<int> m_data;
std::multiset<int> m_mins;
};
|
You might be tempted to replace the line m_mins.erase(m_mins.lower_bound(back)); with m_mins.erase(back). However, the latter would remove all occurrences of back. In contrast, m_mins.erase(m_mins.lower_bound(back)); ensures that only the first occurrence of back is removed.
While this solution may not be the most optimal, it successfully handles all test cases.
An optimal solution
An efficient solution uses a stack with this idea: each time a new value is pushed onto the stack, the smallest value at that moment is also updated and stored alongside it. This means that for every entry in the stack, the current smallest value is tracked and stored together with the value itself, ensuring constant-time of all the operations.
Here is the idea in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class DiscardDeck
{
public:
void discard(int value)
{
if (m_data.empty())
{
m_data.emplace(value, value);
}
else
{
m_data.emplace(value, min(value, peekSmallest()));
}
}
void pick()
{
m_data.pop();
}
int peek()
{
return m_data.top().first;
}
int peekSmallest()
{
return m_data.top().second;
}
private:
stack<pair<int, int>> m_data;
};
|
Here is the same idea in Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class DiscardDeck:
def __init__(self):
self.m_data = []
def discard(self, value):
if not self.m_data:
self.m_data.append((value, value))
else:
self.m_data.append((value, min(value, self.peekSmallest())))
def pick(self):
if self.m_data:
self.m_data.pop()
def peek(self):
if self.m_data:
return self.m_data[-1][0]
def peekSmallest(self):
if self.m_data:
return self.m_data[-1][1]
|
Note that we can also take this opportunity to design our own simple stack, as shown in this Java code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class DiscardDeck
{
private Node head;
public void discard(int value) {
if (head == null)
head = new Node(value, value, null);
else
head = new Node(value, Math.min(value, head.min), head);
}
public void pick() {
head = head.next;
}
public int peek() {
return head.val;
}
public int peekSmallest() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
|
In this case, we rely on the garbage collector to automatically deallocate unreferenced nodes. By replacing the head with its next element, the previous head becomes unreferenced, and the garbage collector will handle the memory cleanup, freeing the resources associated with that node.