[1, 5, 3, 9, 2, 4, 6, 7, 8] and we need to find the index of a value in this list using linear search.1.
(n) grows.| Name | Time Complexity | Description |
|---|---|---|
| Constant Time | O(1) | The runtime remains steady regardless of input size. e.g.: accessing an element in an array by index, inserting/deleting in a hash table. |
| Logarithmic Time | O(log n) | Runtime increases slowly as input grows. e.g.: binary search on a sorted array, operations on balanced binary search trees. |
| Linear Time | O(n) | Runtime grows in direct proportion to input size. e.g.: finding the max or min element in an unsorted array. |
| Quasilinear Time | O(n log n) | A blend of linear and logarithmic growth. e.g.: efficient sorting algorithms like merge sort, quick sort, and heap sort. |
| Quadratic Time | O(n^2) | Runtime grows exponentially with input size. e.g.: simple sorting algorithms: bubble_sort, insertion_sort, selection_sort |
| Cubic Time | O(n^3) | Runtime escalates rapidly as input size increases. e.g.: multiplying two dense matrices using the naive algorithm. |
| Exponential Time | O(2^n) | Runtime doubles with each new input element. e.g.: recursive algorithms that divide problems into multiple subproblems, like the traveling salesman problem |
| Factorial Time | O(n!) | Runtime skyrockets with input size. e.g.: permutation-generation problems, solving combinatorial puzzles, and brute-force approaches. |
| Square Root Time | O(sqrt(n)) | Runtime increases relative to the square root of input. e.g.: searching within a range, such as the Sieve of Eratosthenes for finding all primes up to n. |
O(1)O(n)O(log n)O(n^2)bubble_sort(), insertion_sort() and selection_sort()O(n^3)O(n logn)merge sort, quick sort, and heap sort.O(2^n)O(n!)O(sqrt(n))n.(n).if a > b:
return True
else:
return False
get_first which returns the first element of a list.def get_first(data):
return data[0]
if __name__ == '__main__':
data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
print(get_first(data))
for index in range(0, len(data), 3):
print(data[index])
def binary_search(data, value):
n = len(data)
left = 0
right = n - 1
while left <= right:
middle = (left + right) // 2
if value < data[middle]:
right = middle - 1
elif value > data[middle]:
left = middle + 1
else:
return middle
raise ValueError('Value is not in the list')
if __name__ == '__main__':
data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(data, 8))
Python’s min function returns the minimum or smallest item in a list.
To study the complexity of this algorithm, you’ll develop an alternative version that returns the index of the minimum item.
The algorithm assumes that the list is not empty and that the items are in arbitrary order.
The algorithm begins by treating the first position as that of the minimum item.
It then searches to the right for an item that is smaller if it is found, resets the position of the minimum item to the current position.
When the algorithm reaches the end of the list, it returns the position of the minimum item.
Example:
def indexOfMin(lyst):
"""Returns the index of the minimum item."""
minIndex = 0
currentIndex = 1
while currentIndex < len(lyst):
if lyst[currentIndex] < lyst[minIndex]:
minIndex = currentIndex
currentIndex += 1
return minIndex
Python’s in operator is implemented as a method named contains in the list class.
This method searches for a particular item (called the target item ) within a list of arbitrarily arranged items.
True.Otherwise, the method moves on to the next position and compares its item
with the target.
If the method arrives at the last position and still cannot find the target, it
returns False .
This kind of search is called a sequential search or a linear search . A more
useful sequential search function would return the index of a target if it’s found, or 21
otherwise.
Here is the Python code for a sequential search function:
def sequentialSearch(target, lyst):
"""
Returns the position of the target item if found, or -1
"""
position = 0
while position < len(lyst):
if target == lyst[position]:
return position
position += 1
return -1
The analysis of a sequential search is a bit different from the analysis of a search for a mini-
A sequential search is necessary for data that are not arranged in any particular order.
When searching sorted data, you can use a binary search.
To understand how a binary search works, think about what happens when you look up
a person’s number in a phone book (the hard-copy kind in use during the 20th century).
The data in a phone book are already sorted, so you don’t do a sequential search.
Instead, you estimate the name’s alphabetical position in the book and open the book as close to
that position as possible.
After you open the book, you determine if the target name lies, alphabetically, on an earlier page or a later page, and flip back or forward through the
pages as necessary.
You repeat this process until you find the name or conclude that it’s not in the book.
Now consider an example of a binary search in Python.
To begin, assume that the items in the list are sorted in ascending order (as they are in a phone book).
The search algorithm goes directly to the middle position in the list and compares the item at that
position to the target.
If there is a match, the algorithm returns the position. Otherwise,
if the target is less than the current item, the algorithm searches the portion of the list
before the middle position.
If the target is greater than the current item, the algorithm
searches the portion of the list after the middle position.
The search process stops when the target is found, or the current beginning position is greater than the current
ending position.
def binarySearch(target, sortedLyst):
left = 0
right = len(sortedLyst) - 1
while left <= right:
midpoint = (left + right) // 2
if target == sortedLyst[midpoint]:
return midpoint
elif target < sortedLyst[midpoint]:
right = midpoint - 1
else:
left = midpoint + 1
return -1
There is just one loop with no nested or hidden loops. Once again, the worst case occurs
when the target is not in the list.
How many times does the loop run in the worst case? This is equal to the number of times the size of the list can be divided by 2 until the quotient is 1.
For a list of size n, you essentially perform the reduction n/2/2 … /2 until the result is 1.
Let k be the number of times you divide n by 2.
To solve for k, you have n /2 k 5 1 , and n 5 2 k , and k 5 log 2 n.
Thus, the worst-case complexity of binary search is O(log 2 n ).
Figure 3-7 shows the portions of the list being searched in a binary search with a list of
9 items and a target item, 10, that is not in the list.
The items compared to the target are
shaded. Note that none of the items in the left half of the original list are visited.
The binary search for the target item 10 requires four comparisons, whereas a sequential
search would have required 10 comparisons.
This algorithm actually appears to perform better as the problem size gets larger.
Our list of nine items requires at most four compari-sons, whereas a list of 1,000,000 items requires at most only 20 comparisons!
Binary search is certainly more efficient than sequential search.
However, the kind of search algorithm you choose depends on the organization of the data in the list. There is an addi-
tional overall cost to a binary search, having to do with keeping the list in sorted order.
In a moment, you’ll examine some strategies for sorting a list and analyze their complexity.
But first, you’ll read a few words about comparing data items.
Steps of the binary search:
Computer scientists have devised many ingenious strategies for sorting a list of items.
Several of those are considered here.
The algorithms examined in this section are easy to write but are inefficient; the algorithms discussed in the next section are harder to write but are more efficient.
(This is a common trade-off.)
Each of the Python sort functions that are developed operates on a list of integers and uses a swap function to exchange the positions of two items in the list.
def swap(lyst, i, j):
"""Exchanges the items at positions i and j."""
# You could say lyst[i], lyst[j] = lyst[j], lyst[i]
# but the following code shows what is really going on
temp = lyst[i]
lyst[i] = lyst[j]
lyst[j] = temp
Perhaps the simplest strategy is to search the entire list for the position of the smallest item.
If that position does not equal the first position, the algorithm swaps the items at those positions.
The algorithm then returns to the second position and repeats this process, swapping the smallest item with the item at the second position, if necessary.
When the algorithm reaches the last position in the overall process, the list is sorted.
The algorithm is called selection sort because each pass through the main loop selects a single item to be moved.
Figure 3-8 shows the states of a list of five items after each search and swap pass of a selection sort.
The two items just swapped on each pass have asterisks next to them, and the sorted portion of the list is shaded.
Here is the Python function for a selection sort:
This function includes a nested loop. For a list of size n, the outer loop exe
def selectionSort(lyst):
i = 0
while i < len(lyst) - 1:
# Do n - 1 searches
minIndex = i
# for the smallest
j = i + 1
while j < len(lyst):
# Start a search
if lyst[j] < lyst[minIndex]:
minIndex = j
j += 1
if minIndex != i:
# Exchange if needed
swap(lyst, minIndex, i)
i += 1
swapped flag - Exits early if no swaps occur, making it more efficient for nearly sorted lists.swapped flag optimization.def bubbleSort(lyst):
n = len(lyst)
while n > 1:
i = 1
while i < n:
if lyst[i] < lyst[i - 1]:
swap(lyst, i, i - 1)
i += 1
n -= 1
def bubbleSortWithTweak(lyst):
n = len(lyst)
while n > 1:
swapped = False
i = 1
while i < n:
if lyst[i] < lyst[i - 1]:
swap(lyst, i, i - 1)
swapped = True
i += 1
if not swapped:
return
n -= 1
# Exchange if needed
# Return if no swaps
# Note that this modification only improves best-case behavior. On the averag
def bubble_sort(arr):
"""
Sorts an array of integers in ascending order using Bubble Sort.
Args:
arr (list): List of integers to sort.
Returns:
list: Sorted list in ascending order.
"""
n = len(arr)
for i in range(n):
# Flag to detect any swaps
swapped = False
for j in range(0, n - i - 1):
# Swap if the element found is greater than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no two elements were swapped, break the loop
if not swapped:
break
# Example usage
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers) # Output: [1, 2, 5, 5, 6, 9]
pip install colorama
import colorama
CLEAR_SCREEN = '\u001b[2J'
START_OF_LINE = '\u001b[1G'
CLEAR_LINE = f'{START_OF_LINE}\u001b[0K'
PREVIOUS_LINE = colorama.Cursor.UP(1)
HIDE_CURSOR = '\u001b[?25l'
def format_data(data, position=None):
result = "[ "
inverse = False
for index, val in enumerate(data):
if (position is not None) and (position == index):
result += colorama.Back.LIGHTYELLOW_EX
inverse = True
result += f"{val}"
if (position is not None) and (index == position + 1) and inverse:
result += colorama.Back.RESET
inverse = False
result += " "
result += "]"
return result
def bubble_sort(data: list) -> None:
"""Sorts a list in place."""
n = len(data)
comparison_count = 0
for i in range(n - 1):
print(f"i = {i}. Starting inner loop with {format_data(data)}")
print(end="")
for j in range(n - 1):
print(f"{CLEAR_LINE}j = {j}, {format_data(data, j)}", end="")
comparison_count += 1
if data[j] > data[j + 1]:
print(
f"\t{colorama.Fore.RED}"
f"Swapping {data[j]} and {data[j + 1]}"
f"{colorama.Fore.RESET}", end=""
)
data[j], data[j + 1] = data[j + 1], data[j]
input(f"{PREVIOUS_LINE}")
print(f"{CLEAR_LINE}j = {j}, {format_data(data, j)}", end="")
# Pause
input(f"{PREVIOUS_LINE}")
print(f"End of pass {i}. `data` is now {format_data(data)}")
print(f"comparison_count is {comparison_count}")
colorama.init()
numbers = [3, 2, 4, 1, 5, 7, 6]
# numbers = [7, 6, 5, 4, 3, 2, 1]
print(f"{CLEAR_SCREEN}{HIDE_CURSOR}Sorting {format_data(numbers)}")
bubble_sort(numbers)
print(f"The sorted data is {format_data(numbers)}")
colorama.deinit()
Our modified bubble sort performs better than a selection sort for lists that are already sorted.
But our modified bubble sort can still perform poorly if many items are out of order in the list.
Another algorithm, called an insertion sort, attempts to exploit the partial ordering of the list in a different way.
The strategy is as follows:
1 to n 2 1, the ith item should be inserted into its proper place among the first i items in the list.i 2 1 cards in order, you pick the ith card and compare it to these cards until its proper spot is found.def insertionSort(lyst):
i = 1
while i < len(lyst):
itemToInsert = lyst[i]
j = i - 1
while j >= 0:
if itemToInsert < lyst[j]:
lyst[j + 1] = lyst[j]
j -= 1
else:
break
lyst[j + 1] = itemToInsert
i += 1
def quicksort(lst: list):
"Quicksort over a list-like sequence"
if len(lst) == 0:
return lst
pivot = lst[0]
pivots = [x for x in lst if x == pivot]
small = quicksort([x for x in lst if x < pivot])
large = quicksort([x for x in lst if x > pivot])
return small + pivots + large
distinct predecessor, and all items except the last have a distinct successor.predecessor and successor are replaced with those of parent and child.Trees have two main characteristics:
Node
Root
Child
Parent
Siblings
Leaf
Interior node
A node that has at least one child.
Edge/Branch/Link
Descendant
Ancestor
Path
Path length
Depth or level
Height
The length of the longest path in the tree; put differently, the maximum level
T – {r} is partitioned into disjointed subsets, each of which is a general tree.root node and then traverses the left subtree and the right subtree in a similar manner.inorder traversal algorithm traverses the left subtree, visits the root node, and traverses the right subtree.far to the left in the tree as possible before visiting a node.left subtree, traverses the right subtree, and visits the root node.Beginning with level 0, the level order traversal algorithm visits the nodes at each level in left-to-right order.sorted order.preorder, inorder, and postorder traversals of expression trees can be used to generate the prefix, infix, and postfix representations of the expressions,from abstractCollection import AbstractCollection
from bstnode import BSTNode
class LinkedBST(AbstractCollection):
"""A link-based binary search tree implementation."""
def __init__(self, sourceCollection = None):
"""Sets the initial state of self
- which includes the contents of sourceCollection, if it’s present
"""
self.root = None
AbstractCollection.__init__(sourceCollection)
def find(self, item):
"""Returns data if item is found or None otherwise."""
# Helper function to search the binary tree
def recurse(node):
if node is None:
return None
elif item == node.data:
return node.data
elif item < node.data:
return recurse(node.left)
else:
return recurse(node.right)
# Top-level call on the root node
return recurse(self.root)
def inorder(self):
"""Supports an inorder traversal on a view of self."""
lyst = list()
def recurse(node):
if node != None:
recurse(node.left)
lyst.append(node.data)
recurse(node.right)
recurse(self.root)
return iter(lyst)
def __str__(self):
"""Returns a string representation with the tree rotated
90 degrees counterclockwise."""
def recurse(node, level):
s = ""
if node != None:
s += recurse(node.right, level + 1)
s += "| " * level
s += str(node.data) + "\n"
s += recurse(node.left, level + 1)
return s
return recurse(self.root, 0)
def add(self, item):
"""Adds item to the tree."""
# Helper function to search for item’s position
def recurse(node):
# New item is less; go left until spot is found
if item < node.data:
if node.left == None:
node.left = BSTNode(item)
else:
recurse(node.left)
# go right until spot is found
elif node.right == None:
node.right = BSTNode(item)
else:
recurse(node.right)
# End of recurse
# Tree is empty, so new item goes at the root
if self.isEmpty():
self.root = BSTNode(item)
# Otherwise, search for the item’s spot
else:
recurse(self.root)
self.size += 1
from linkedbst import LinkedBST
from abstractCollection import AbstractCollection
from abstractset import AbstractSet
class TreeSortedSet(AbstractSet):
"""A tree-based implementation of a sorted set."""
def __init__(self, sourceCollection = None ):
self.items = LinkedBST()
if sourceCollection:
for item in sourceCollection:
self.add(item)
def __contains__(self, item):
"""Returns True if item is in the set or
False otherwise."""
return item in self.items
def __iter__(self):
"""Supports an inorder traversal on a view of self."""
return self.items.inorder()
def add(self, item):
"""Adds item to the set if it is not in the set."""
if not item in self:
self.items.add(item)
set V of vertices and a set E of edges, such that each edge in E connects two of the vertices in V.node is also used here as a synonym for vertex.Vertices and edges can be labeled or unlabeled.DFS is useful in scenarios like
How DFS Works:
Explanation:
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(f"Visiting {node}")
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
# Example graph and calling the function
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs_recursive(graph, 'A')
O(V + E), where V is the number of vertices and E is the number of edges.O(V), due to stack used for recursion (in recursive implementation) or an explicit stack (in iterative implementation).Explanation
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(f"Visiting {node}")
stack.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
return visited
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(f"Visiting {vertex}")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
def topological_sort_dfs(graph):
visited = set()
stack = []
def dfs(vertex):
visited.add(vertex)
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(vertex)
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return stack[::-1]
from collections import deque
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] = in_degree.get(v, 0) + 1
queue = deque([u for u in in_degree if in_degree[u] == 0])
topo_order = []
while queue:
u = queue.popleft()
topo_order.append(u)
for v in graph.get(u, []):
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(topo_order) == len(in_degree):
return topo_order
else:
raise Exception("Graph has at least one cycle")
class UnionFind:
def __init__(self, size):
self.parent = [i for i in range(size)]
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_y] < self.rank[root_x]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
def has_cycle_undirected(graph):
visited = set()
def dfs(vertex, parent):
visited.add(vertex)
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
if dfs(neighbor, vertex):
return True
elif neighbor != parent:
return True
return False
for vertex in graph:
if vertex not in visited:
if dfs(vertex, None):
return True
return False
def connected_components(graph):
visited = set()
components = []
def dfs(node, component):
visited.add(node)
component.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor, component)
for node in graph:
if node not in visited:
component = []
dfs(node, component)
components.append(component)
return components
from collections import deque
def is_bipartite(graph):
color = {}
for node in graph:
if node not in color:
queue = deque([node])
color[node] = 0
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in color:
color[neighbor] = 1 - color[current]
queue.append(neighbor)
elif color[neighbor] == color[current]:
return False
return True
def flood_fill_recursive(image, sr, sc, new_color):
rows, cols = len(image), len(image[0])
color_to_replace = image[sr][sc]
if color_to_replace == new_color:
return image
def dfs(r, c):
if (0 <= r < rows and 0 <= c < cols and image[r][c] == color_to_replace):
image[r][c] = new_color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
class UnionFind:
def __init__(self, size):
self.parent = [i for i in range(size)]
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_y] < self.rank[root_x]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal_mst(num_nodes, edges):
uf = UnionFind(num_nodes)
mst = []
total_weight = 0
edges.sort(key=lambda x: x[0])
for weight, u, v in edges:
if uf.union(u, v):
mst.append((u, v, weight))
total_weight += weight
return mst
import heapq
def dijkstra(graph, start):
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
Explanation:
num_vertices - 1 times, relaxing all edges.O(V * E)O(V) for storing distances.def bellman_ford(graph, start):
# graph: list of edges [(u, v, weight), ...]
num_vertices = len({u for edge in graph for u in edge[:2]})
distances = {vertex: float('inf') for edge in graph for vertex in edge[:2]}
distances[start] = 0
# Relax edges repeatedly
for _ in range(num_vertices - 1):
for u, v, weight in graph:
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Check for negative-weight cycles
for u, v, weight in graph:
if distances[u] + weight < distances[v]:
raise Exception("Graph contains a negative-weight cycle")
return distances
from collections import deque
def bfs_shortest_path(graph, start, target):
visited = set()
queue = deque([(start, [start])]) # Each element is a tuple (node, path_to_node)
visited.add(start)
while queue:
current_node, path = queue.popleft()
if current_node == target:
return path # Shortest path found
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None# Path not found
How It Works:
Time Complexity:
import heapq
def a_star(graph, start, goal, heuristic):
open_set = []
heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start, [start])) # (f_score, g_score, node, path)
closed_set = set()
while open_set:
f_score, g_score, current_node, path = heapq.heappop(open_set)
if current_node == goal:
return path # Shortest path found
if current_node in closed_set:
continue
closed_set.add(current_node)
for neighbor, weight in graph[current_node]:
if neighbor in closed_set:
continue
tentative_g_score = g_score + weight
tentative_f_score = tentative_g_score + heuristic(neighbor, goal)
heapq.heappush(open_set, (tentative_f_score, tentative_g_score, neighbor, path + [neighbor]))
return None # Path not found
O(V^3)O(V^2) for storing the distance array.def floyd_warshall(graph):
# Initialize distance and next_node matrices
nodes = list(graph.keys())
dist = {u: {v: float('inf') for v in nodes} for u in nodes}
next_node = {u: {v: None for v in nodes} for u in nodes}
# Initialize distances based on direct edges
for u in nodes:
dist[u][u] = 0
for v, weight in graph[u]:
dist[u][v] = weight
next_node[u][v] = v
# Floyd-Warshall algorithm
for k in nodes:
for i in nodes:
for j in nodes:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next_node[i][j] = next_node[i][k]
# Check for negative cycles
for u in nodes:
if dist[u][u] < 0:
raise Exception("Graph contains a negative-weight cycle")
return dist, next_node
top.
LIFO protocoltop of stack.
append pushes item to end of stack.pop removes element from end / top of the stack.push
s.push(item)top of s.pop
s.pop()s.s
raises exception if not met.peek
s.peek()raises a keyerror if the stack is empty.cear -> list
s.clear()isEmpty -> bool
s.isEmpty()True if s is empty or False otherwise.len -> int
s.__len__()len(s).
str
s.__str__()str(s). Returns the string representation of s.in
True if item is in s or False otherwise.+
s1.__add__(s2).s1 + s2.
new stack containing the items in s1 and s2.s.__iter__()
s.__eq__(anyObject)
"""
Typical Stack Data Structure.
"""
class Stack():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return self.items == []
def peek(self):
if not self.is_empty():
return self.items[-1]
def get_stack(self):
return self.items
myStack = Stack()
myStack.push("A")
myStack.push("B")
myStack.push("C")
myStack.push("D")
print(myStack.peek())
class AbstractCollection(object):
"""
p. 160
- The remaining code in the AbstractBag class includes the methods:
- isEmpty
- __len__
- __str__
- __add__
- count
- __eq__
- As they are implemented in:
- ArrayBag
- LinkedBag
"""
def __init__(self, sourceCollection = None):
"""
Sets the initial state of self:
- which includes the contents of sourceCollection, if present.
"""
self.size = 0
if sourceCollection:
for item in sourceCollection:
self.add(item)
def __eq__(self, other):
"""
Returns True if self equals other,
or
False otherwise.
"""
if self is other:
return True
if type(self) != type(other) or len(self) != len(other):
return False
otherIter = iter(other)
for item in self:
if item != next(otherIter):
return False
return True
from arrays import Array
from abstractstack import AbstractStack
class AbstractStack(AbstractCollection):
"""An abstract stack implementation."""
# Constructor
def __init__(self, sourceCollection):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
AbstractCollection.__init__(self, sourceCollection)
# Mutator methods
def add(self, item):
"""Adds item to self."""
self.push(item)
class Array(object):
# pg 109 / 91
"""Represents an array."""
def __init__(self, capacity, fillValue = None):
"""
Capacity:: is the static size of the array.
fillValue:: is placed at each position.
"""
self.items = list()
for count in range(capacity):
self.items.append(fillValue)
def __len__(self):
"""-> The capacity of the array."""
return len(self.items)
def __str__(self):
"""-> The string representation of the array."""
return str(self.items)
def __iter__(self):
"""Supports traversal with a for loop."""
return iter(self.items)
def __getitem__(self, index):
"""Subscript operator for access at index."""
return self.items[index]
def __setitem__(self, index, newItem):
"""Subscript operator for replacement at index."""
self.items[index] = newItem
class ArrayStack(AbstractStack):
"""An array-based stack implementation."""
DEFAULT_CAPACITY = 10# For all array stacks
def __init__(self, sourceCollection = None):
"""
Sets the initial state of self, which includes the contents of sourceCollection, if it's present.
"""
self.items = Array(ArrayStack.DEFAULT_CAPACITY)
AbstractStack.__init__(self, sourceCollection)
# Accessors
def __iter__(self):
"""
- Supports iteration over a view of self.
- Visits items from bottom to top of stack.
"""
cursor = 0
while cursor < len(self):
yield self.items[cursor]
cursor += 1
def peek(self):
"""Returns the item at top of the stack.
Precondition: the stack is not empty.
Raises KeyError if the stack is empty."""
# Check precondition here
return self.items[len(self) - 1]
# Mutators
def clear(self):
"""Makes self become empty."""
self.size = 0
self.items = Array(ArrayStack.DEFAULT_CAPACITY)
def push(self, item):
"""Inserts item at top of the stack."""
# Resize array here if necessary
self.items[len(self)] = item
self.size += 1
def pop(self):
"""Removes and returns the item at top of the stack.
- Precondition: the stack is not empty.
- Raises KeyError if the stack is empty.
- Postcondition: the top item is removed from the stack."""
# Check precondition here
oldItem = self.items[len(self) - 1]
self.size -= 1
# Resize the array here if necessary
return oldItem
# p. 189
from node import Node
from abstractstack import AbstractStack
class LinkedStack(AbstractStack):
""" Link-based stack implementation."""
def __init__(self, sourceCollection = None):
self.items = None
AbstractStack.__init__(self, sourceCollection)
# Accessors
def __iter__(self):
"""
- Supports iteration over a view of self.
- Visits items from bottom to top of stack.
"""
def visitNodes(node):
if node != None:
visitNodes(node.next)
tempList.append(node.data)
tempList = list()
visitNodes(self.items)
return iter(tempList)
def peek(self):
"""
Returns the item at top of the stack.
- Precondition: the stack is not empty.
"""
if self.isEmpty():
raise KeyError("The stack is empty.")
return self.items.data
# Mutators
def clear(self):
"""Makes self become empty."""
self.size = 0
self.items = None
def push(self, item):
"""Inserts item at top of the stack."""
self.items = Node(item, self.items)
self.size += 1
def pop(self):
"""
Removes and returns the item at top of the stack.
- Precondition: the stack is not empty
"""
if self.isEmpty():
raise KeyError("The stack is empty.")
oldItem = self.items.data
self.items = self.items.next
self.size -= 1
return oldItem
Matching Parentheses
from linkedstack import LinkedStack
def bracketsBalance(exp):
"""exp is a string that represents the expression"""
stk = LinkedStack() # Create a new stack
for ch in exp: # Scan across the expression
if ch in ['[', '(']: # Push an opening bracket
stk.push(ch)
elif ch in [']', ')']: # Process a closing bracket
if stk.isEmpty(): # Not balanced
return False
chFromStack = stk.pop()
# Brackets must be of same type and match up
if ch == ']' and chFromStack != '[' or \
ch == ')' and chFromStack != '(':
return False
return stk.isEmpty() # They all matched up
def main():
exp = input("Enter a bracketed expression: ")
if bracketsBalance(exp):
print("OK")
else:
print("Not OK")
if __name__ == "__main__":
main()
O(n2).O(n)K (easy)K distinct characters (medium)O(n²).O(n).complement = target - nums[i]).Input
nums = [2, 7, 11, 15]
target = 9
Step 1
{}num = 2complement = 9 - 2 = 72: 0 to hash table {2: 0}num = 7complement = 9 - 7 = 2[0, 1]Time Complexity
O(n)O(n)def twoSum(nums: list[int], target: int) -> list[int]:
num_map = {}# Hash table to store numbers and their indices
for i, num in enumerate(nums):
complement = target - num# Calculate the complement
# Check if complement is already in the hash table
if complement in num_map:
return [num_map[complement], i]# Return indices if complement found
# Add the current number and its index to the hash table
num_map[num] = i
return []#Default return if no solution found (not needed as per constraints)
Examples:
K Numbers (easy)K Frequent Numbers (medium)O(log n) time complexity and O(1) space complexity without converting the number into a string.Key Observations about Palindromes
x < 0) are not palindromes because of the negative sign.10, 120) cannot be palindromes unless the number itself is 0.x % 10).x // 10) step-by-step until the reversed half becomes greater than or equal to the remaining half.reversed_half // 10).def isPalindrome(x: int) -> bool:
# Edge cases: Negative numbers or numbers ending in 0 (except 0 itself)
if x < 0 or (x % 10 == 0 and x != 0):
return False
reversed_half = 0
while x > reversed_half:
# Append the last digit to reversed_half
reversed_half = reversed_half * 10 + x % 10
# Remove the last digit from x
x //= 10
# Check if the first half equals the reversed second half
# For odd-length numbers, ignore the middle digit in reversed_half
return x == reversed_half or x == reversed_half // 10
x = 1221x = 1221, reversed_half = 0reversed_half = 0 * 10 + 1221 % 10 = 1x = 1221 // 10 = 122reversed_half = 1 * 10 + 122 % 10 = 12x = 122 // 10 = 12x (12) is not greater than reversed_half (12) → Stop.x == reversed_half → 12 == 12 → Truex = 12321After iterations, we get:
x = 12reversed_half = 123Ignore the middle digit (3) by dividing by 10:
reversed_half // 10 = 12Check: x == reversed_half // 10 → 12 == 12 → True
Problems