Time Complexities

Data Structure & Algorithm	Time Complexity	Space Complexity	Notes
Stacks - Push (Add)	O(1)	O(1)	Constant time operation
Stacks - Pop (Delete)	O(1)	O(1)	Constant time operation
Stacks - Insert (at specific position)	O(n)	O(1)	Requires shifting elements
Stacks - Peek	O(1)	O(1)	Constant time operation
Queue - Enqueue (Add)	O(1)	O(1)	Constant time operation
Queue - Dequeue (Remove)	O(1)	O(1)	Constant time operation
Array - Access	O(1)	-	Direct index access
Array - Search (unsorted)	O(n)	O(1)	Linear search
Array - Insert/Delete (at end)	O(1)	-	Amortized for dynamic arrays
Array - Insert/Delete (at beginning/middle)	O(n)	O(1)	Requires shifting elements
Linked List - Access	O(n)	-	Traversal required
Linked List - Search	O(n)	O(1)	Linear search
Linked List - Insert/Delete (at beginning)	O(1)	O(1)	Constant time operation
Linked List - Insert/Delete (at end/middle)	O(n)	O(1)	Traversal required

Binary Search

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  *# Target not found*

Two Pointers

def two_pointers(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        *# Process elements at left and right# Move pointers based on condition*
        left += 1
        right -= 1

Sliding Window

def fixed_sliding_window(arr, k):
	
	L = 0
	
	for R in range(len(arr)):
		currSum += arr[R]
		window_size = R - L + 1
		
		# If the window size is K.. We process the stuff
		if window_size == k:
			maxSum = max(currSum, maxSum)
			
			# Update the window
			currSum -= arr[L]
			L += 1
		
	return maxSum

Sorting — Insertion Sort, Selection & Merge Sort

*# Insertion Sort*
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

*# Selection Sort*
def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

*# Merge Sort*
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Graphs — Recursive, DFS, BFS

*# DFS (Recursive)*
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

*# BFS*
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Stacks / Queues

*# Stack implementation*
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0

*# Queue implementation*
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.popleft()
    
    def front(self):
        return self.items[0]
    
    def is_empty(self):
        return len(self.items) == 0