Solving Min Stack to Find the Root of a Chord
So far, in my previous posts on stacks, I have been discussing array-based stacks. Array-based stacks use a fixed size of memory. They are simple to create, but you can run into memory problems. One example is stack overflow. Max for Live is a platform to build your own instruments and effects in Ableton Live, a digital audio workstation (DAW). Max for Live is based on Max, a visual programming language used by musicians, artists, and designers to create interactive installations and performance tools. With Max, you connect objects with patch cords to process data, audio, and video. Stack overflow happens when you overload Max with the list of things (aka a stack) that Max has to do, eventually overflowing the amount of memory space available. One way that this can happen is through an infinite loop. It causes Max to shut down its internal scheduler and stop performing operations. What we need is dynamic memory for these stacks, so that memory can expand as needed. How might we do this? Using linked lists! Check out my previous posts on linked lists to learn more about them.
Learning Data Structures and Algorithms with Music is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber.
Linked-list based stacks provide dynamic memory, but require extra space since they utilize pointers. Linked-list based and array-based stacks still both offer O(1) time complexity. Let’s see how to implement a linked list-based stack.
First, we have to define the Node class. This class defines the node that is storing the data and the reference (i.e. pointer) to the next node. We initialize with the node pointing to nothing since None means “no object,” or “no node” in this case.
class Node:
def __init__(self, data):
self.data = data
self.next = None
Next, we need to update the definition of the stack class that I previously used with arrays. The key insight is that instead of tracking a list of items, we’ll track the stack’s top node. When the stack is empty, top is None.
class Stack:
def __init__(self):
self.top: Node | None = None
Next, we will create the push(), pop(), peek(), and is_empty() methods.
The push() method has a few components to it:
We need to define a new node
We need to make this new node point to the stack’s top
We need to update the stack’s top to be this new node
def push(self, item): node = Node(item)
node.next = self.top
self.top = node
For the pop() method, we still need to check if the stack is empty. Additionally, we remove the stack’s top from the stack and return the element we just removed.
def is_empty(self):
return self.top == None
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
element = self.top.data
self.top = self.top.next
return element
To check if the stack is empty, we just check if the stack’s top is None. The element that we return is the data in the stack’s top. To proceed with a stack that no longer has the popped element, we have the stack’s top point to the next element in the stack.
Lastly, we have the peek() method, which just returns the stack’s top, but it doesn’t change the original stack.
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
return self.top.data
So here the full linked-list Stack implementation:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top: Node | None = None
def push(self, data):
node = Node(data)
node.next = self.top
self.top = node
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
element = self.top.data
self.top = self.top.next
return element
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
return self.top.data
def is_empty(self):
return self.top == None
One thing that I wondered about is whether we can connect these linked-list stacks to music. A question that I came across on Leetcode was the MinStack problem. One way to solve this problem is to use a linked-list and its solution is also a cool way to find the root note of a scale. The root note is the first note in a scale.
For this question, we have to design a stack that supports push, pop, top (another work for peek), and retrieving the minimum element in constant time. For the Node class, the main difference is that we need to add a minimum attribute that holds the minimum element.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.min = None
To find the minimum element, we have to do comparisons using Python’s built-in minimum (min()) function. However, what is the minimum element if the stack is empty? It is the minimum element. So we have to add this check to the method. To be consistent with the Leetcode methods, I will use top() which is the same as the peek() method that I wrote before. To reduce confusion, I will rename the stack’s top to the stack’s head.
def push(self, data):
node = Node(data) # Creates a Node object
if self.head == None:
node.min = data
node.next = self.head
self.head = node
else:
node.min = min(data, self.head.min)
node.next = self.head
self.head = node
For the push() method, if the stack is empty (None), then the element that we are pushing is the minimum element of the stack. The new node’s next pointer is pointing to the stack’s head (fka top) and the new node is set to the stack’s head. If the stack is not empty, then I find the minimum of the new element and the stack’s current minimum and set that answer to the node’s minimum. I point the new node’s next pointer to the stack’s head. Lastly, I set the new node to the stack’s head.
There is no difference between the top() and peek() methods. These methods return the value of the stack’s head without modifying the stack.
def top(self): # same as peek()
if self.head == None:
raise IndexError("Sorry, your stack is empty")
return self.head.data
There is no difference with the pop() method either, it returns the value of the stack’s head and it modifies the stack by removing the stack’s head from it.
def pop(self):
if self.head == None:
raise IndexError("Sorry, your stack is empty")
else:
element = self.head.data
self.head = self.head.next
return element
Lastly, we need a method that gets the minimum element, getMin(). We still need to check if it’s empty first. If it’s not empty, we return the minimum value in the stack’s head.
def getMin(self):
if self.head == None:
raise IndexError("Sorry, your stack is empty")
return self.head.min
Here is a full solution for the MinStack question.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.min = None
class MinStack:
def __init__(self):
self.head: Node | None = None
def getMin(self):
if self.head == None:
raise IndexError("Sorry, your stack is empty")
return self.head.min
def top(self): # same as peek()
if self.head == None:
raise IndexError("Sorry, your stack is empty")
return self.head.data
def push(self, data):
node = Node(data) # Creates a Node object
if self.head == None:
node.min = data
node.next = self.head
self.head = node
else:
node.min = min(data, self.head.min)
node.next = self.head
self.head = node
def pop(self):
if self.head == None:
raise IndexError("Sorry, your stack is empty")
else:
element = self.head.data
self.head = self.head.next
return element
Now, bringing it all together, let’s find the root of the chord using MinStack.
from music21 import note, stream
# D Major Scale MIDI Numbers
# D4 (Middle D): 62
# E4: 64
# F#4: 66
# G4: 67
# A4: 69
# B4: 71
# C#5: 73
# D5 (Octave Up): 74
midi_notes = [62, 64, 66, 67, 69, 71, 73, 74]
# Create a Stream to hold the notes
s = stream.Stream()
# Convert each MIDI number to a Note and append to stream
for midi_num in midi_notes:
n = note.Note(midi=midi_num)
s.append(n)
# Play the notes via MIDI
s.show('midi')
s.show()
Now, we need to push these MIDI note numbers into the MinStack. Then, we can run the getMin() method. It tells me ‘62,’ which is correct and matches D4, the middle D.
min_stack_root = MinStack()
for midi_num in midi_notes:
min_stack_root.push(midi_num)
min_stack_root.getMin()
# 62 is the answer
Then we need to put this into a Stream and create a Note object with this MIDI number in order to play it.
s_root = stream.Stream()
n_root = note.Note(midi=min_stack_root.getMin())
s_root.append(n_root)
s_root.show('midi')
s_root.show()
Let’s make this a little more interesting and shuffle the scale and find the root note.
## D Major out of order
midi_notes_shuffle = [71, 69, 74, 66, 67, 62, 64, 73]
# Create a Stream to hold the notes
s_shuffle = stream.Stream()
# Convert each MIDI number to a Note and append to stream
for midi_num in midi_notes_shuffle:
n_shuffle = note.Note(midi=midi_num)
s_shuffle.append(n_shuffle)
# Display the notation as text
#s.show('text')
# Play the notes via MIDI
s_shuffle.show('midi')
s_shuffle.show()
Now, we find the minimum, which is again 62, the root note of the D major scale.
min_stack_shuffle = MinStack()
for midi_num in midi_notes_shuffle:
min_stack_shuffle.push(midi_num)
min_stack_shuffle.getMin()
# 62 is the answer
To be fair, there is no real advantage to implementing a linked-list based stack or an array-based stack for this MinStack question. In general, linked lists have one advantage: they don’t need to resize like Python lists do when they run out of space. But for most practical purposes, Python’s list-based stack is simpler to implement.
Learning Data Structures and Algorithms with Music is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber