Description of the problem
In a deck of cards, every card has a unique integer. You can order the deck in any order you want.
Initially, all the cards start face down (unrevealed) in one deck.
Now, you do the following steps repeatedly, until all cards are revealed:
- Take the top card of the deck, reveal it, and take it out of the deck.
- If there are still cards in the deck, put the next top card of the deck at the bottom of the deck.
- If there are still unrevealed cards, go back to step 1. Otherwise, stop.
Return an ordering of the deck that would reveal the cards in increasing order.
The first entry in the answer is considered to be the top of the deck.
Example 1:Input: [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation:
We get the deck in the order [17,13,11,2,3,5,7] (this order doesn't matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom. The deck is now [13,17].
We reveal 13, and move 17 to the bottom. The deck is now [17].
We reveal 17.Since all the cards revealed are in increasing order, the answer is correct.
For LeetCode 950, this guide contains two solutions:
Solution 1: Index and concatenation
# Stats:
#=========================
# Runtime. Memory.
# 68ms. 13.4 MB
#=========================
deck = [17,13,11,2,3,5,7]
class Solution:
def deckRevealedIncreasing(self, deck):
a = []
for x in sorted(deck)[::-1]:
a = [x] + a[-1:] + a[:-1]
return a
Returns:
[2, 13, 3, 11, 5, 17, 7]Let’s break this down and take a closer look at what each piece of code is doing.
deck = [17,13,11,2,3,5,7]
a = []
# Loop through a new version of the list in reverse order
for x in sorted(deck)[::-1]:
# sorted(deck)[::-1] = [17, 13, 11, 7, 5, 3, 2]
# Start appending to list 'a':
# -------------------------------
# [x] = current item in 'deck'
# a[-1:] = last item currently in 'a'
# a[:-1] = all items except the last item currently in 'a'
# -------------------------------
# On each pass:
# 'x' becomes index 0 in 'a'
# The item at index -1 in 'a' moves to index 1 in 'a'
# All remaining items in 'a' are appended to the new copy of 'a'
a = [x] + a[-1:] + a[:-1]
# After iterating the full 'deck' list, return the final version of list 'a'
print(a)
# a = [2, 13, 3, 11, 5, 17, 7]
Now let’s check how the loop creates the final returned value. We’ll print the values that get concatenated at each loop iteration, so you can see how the values are assigned and ordered.
deck = [17,13,11,2,3,5,7]
a = []
i = 1
# Printing each iteration, to show how list 'a' is built up
for x in sorted(deck)[::-1]:
print("\nIteration:", i)
print("x =", x)
print("a[-1:] =", a[-1:])
print("a[:-1] =", a[:-1])
a = [x] + a[-1:] + a[:-1]
print("[x] + a[-1:] + a[:-1] = {}".format(a))
i += 1
Output:
Iteration: 1
x = 17
a[-1:] = []
a[:-1] = []
[x] + a[-1:] + a[:-1] = [17]
Iteration: 2
x = 13
a[-1:] = [17]
a[:-1] = []
[x] + a[-1:] + a[:-1] = [13, 17]
Iteration: 3
x = 11
a[-1:] = [17]
a[:-1] = [13]
[x] + a[-1:] + a[:-1] = [11, 17, 13]
Iteration: 4
x = 7
a[-1:] = [13]
a[:-1] = [11, 17]
[x] + a[-1:] + a[:-1] = [7, 13, 11, 17]
Iteration: 5
x = 5
a[-1:] = [17]
a[:-1] = [7, 13, 11]
[x] + a[-1:] + a[:-1] = [5, 17, 7, 13, 11]
Iteration: 6
x = 3
a[-1:] = [11]
a[:-1] = [5, 17, 7, 13]
[x] + a[-1:] + a[:-1] = [3, 11, 5, 17, 7, 13]
Iteration: 7
x = 2
a[-1:] = [13]
a[:-1] = [3, 11, 5, 17, 7]
[x] + a[-1:] + a[:-1] = [2, 13, 3, 11, 5, 17, 7]So, we know the solution works, but is it the most performant? Upon submission, LeetCode provides the following stats:
- Runtime: 68ms
- Faster than: 23.38% of Python3 online submissions
- Memory usage: 13.4 MB
- Less than: 19.58% of Python3 online submissions
Performance isn’t great. Ideally, we’d like to see a runtime that’s 80-90%+ faster, and memory usage that’s 80-90%+ less than other online Python3 submissions.
Another solution we can investigate involves using collections.deque().
Solution 2: Using collections.deque()
The Python documentation describes collections.deque() as: A list-like container with fast appends and pops on either end.
# Stats:
#=========================
# Runtime. Memory.
# 44ms. 13.1 MB
#=========================
import collections
class Solution:
def deckRevealedIncreasing(self, deck):
# deque(): list-like container with fast appends and pops on either end
d = collections.deque()
for x in sorted(deck)[::-1]: # Returns a new list in reverse order
d.rotate() # Rotate the deque
d.appendleft(x) # Add x to the left side of the deque
return list(d) # Create a new list containing the contents of deque
Returns:
[2, 13, 3, 11, 5, 17, 7]So, this returns the correct result. Let’s take a closer look at the results of each iteration.
import collections
deck = [17, 13, 11, 2, 3, 5, 7]
d = collections.deque()
i = 1
for x in sorted(deck)[::-1]:
print("\nIteration:", i)
print("x = {}".format(x))
print("START: d = {}".format(d))
d.rotate()
print("After rotate(): d = {}".format(d))
d.appendleft(x)
print("After appendleft(x): d = {}".format(d))
i += 1
Output:
Iteration: 1
x = 17
START: d = deque([])
After rotate(): d = deque([])
After appendleft(x): d = deque([17])
Iteration: 2
x = 13
START: d = deque([17])
After rotate(): d = deque([17])
After appendleft(x): d = deque([13, 17])
Iteration: 3
x = 11
START: d = deque([13, 17])
After rotate(): d = deque([17, 13])
After appendleft(x): d = deque([11, 17, 13])
Iteration: 4
x = 7
START: d = deque([11, 17, 13])
After rotate(): d = deque([13, 11, 17])
After appendleft(x): d = deque([7, 13, 11, 17])
Iteration: 5
x = 5
START: d = deque([7, 13, 11, 17])
After rotate(): d = deque([17, 7, 13, 11])
After appendleft(x): d = deque([5, 17, 7, 13, 11])
Iteration: 6
x = 3
START: d = deque([5, 17, 7, 13, 11])
After rotate(): d = deque([11, 5, 17, 7, 13])
After appendleft(x): d = deque([3, 11, 5, 17, 7, 13])
Iteration: 7
x = 2
START: d = deque([3, 11, 5, 17, 7, 13])
After rotate(): d = deque([13, 3, 11, 5, 17, 7])
After appendleft(x): d = deque([2, 13, 3, 11, 5, 17, 7])So, using collections.deque() also works, but is it a more efficient solution? Upon submission, LeetCode provides the following stats:
- Runtime: 44ms
- Faster than: 95.94% of Python3 online submissions
- Memory usage: 13.1 MB
- Less than: 86.78% of Python3 online submissions
Performance is much better. We’re starting to get up into the top 5-15% of submissions, with a solution that’s faster and requires less memory than Solution 1.
