Data Structures & AlgorithmsCheat Sheet

Master coding interviews with essential DSA concepts, algorithms, and complexity analysis

Back to Cheat Sheets

Interview Ready

Time Complexity

Code Examples

1
Arrays & Strings

Array Access

Access any element in constant time using its index

arr[index] - Direct access to element at index

basicinterviewcoding

Time: O(1)Space: O(1)

Example:

arr = [1,2,3,4]; arr[2] returns 3

Pro Tip:

Arrays provide constant time access but fixed size

Linear Search

Search for an element by checking each position sequentially

for i in range(len(arr)): if arr[i] == target: return i

basicinterviewcoding

Time: O(n)Space: O(1)

Example:

Find 5 in [1,3,5,7,9] → check positions 0,1,2 → found at index 2

Pro Tip:

Use when array is unsorted or small

Binary Search

Search in sorted array by repeatedly dividing search space in half

left, right = 0, len(arr)-1; while left <= right: mid = (left+right)//2

intermediateinterviewalgorithms

Time: O(log n)Space: O(1)

Example:

Find 7 in [1,3,5,7,9] → mid=5, 7>5, search right half → found

Pro Tip:

Only works on sorted arrays, much faster than linear search

Two Pointers Technique

Use two pointers moving towards each other to solve problems efficiently

left, right = 0, len(arr)-1; while left < right: # process and move pointers

intermediateinterviewalgorithms

Time: O(n)Space: O(1)

Example:

Find pair with sum=10 in [1,2,3,4,5,6] → left=0, right=5, check sum

Pro Tip:

Great for sorted arrays, palindromes, and pair problems

Fixed Sliding Window

Maintain a window of fixed size k and slide it through the array

window_sum = sum(arr[:k]); for i in range(k, len(arr)): window_sum += arr[i] - arr[i-k]

intermediateinterviewoptimization

Time: O(n)Space: O(1)

Example:

Max sum of 3 consecutive elements: [1,4,2,9,5] → windows: [1,4,2]=7, [4,2,9]=15, [2,9,5]=16

Pro Tip:

Avoid recalculating sum by adding new element and removing old one

Kadane's Algorithm (Max Subarray)

Find maximum sum of contiguous subarray in linear time

max_sum = current_sum = arr[0]; for i in range(1, len(arr)): current_sum = max(arr[i], current_sum + arr[i])

intermediateinterviewalgorithms

Time: O(n)Space: O(1)

Example:

[-2,1,-3,4,-1,2,1,-5,4] → max subarray [4,-1,2,1] with sum 6

Pro Tip:

Reset current sum to current element if it becomes negative

Prefix Sum Array

Precompute cumulative sums for fast range sum queries

prefix[i] = prefix[i-1] + arr[i]; range_sum(l,r) = prefix[r] - prefix[l-1]

intermediateinterviewrange-queries

Time: O(n) build, O(1) querySpace: O(n)

Example:

arr=[1,2,3,4,5] → prefix=[1,3,6,10,15]; sum(1,3) = 15-1 = 14

Pro Tip:

Handle edge cases with 0-indexed arrays carefully

Dutch National Flag (3-way Partition)

Partition array into three parts (0s, 1s, 2s) in single pass

low = mid = 0; high = len(arr)-1; while mid <= high: if arr[mid] == 0: swap(low,mid), low++, mid++

advancedinterviewsorting

Time: O(n)Space: O(1)

Example:

[2,0,2,1,1,0] → [0,0,1,1,2,2] using three pointers

Pro Tip:

Classic problem for sorting 0s, 1s, and 2s

2
Linked Lists

Linked List Traversal

Visit each node in the linked list sequentially

current = head; while current: print(current.data); current = current.next

basicinterviewcoding

Time: O(n)Space: O(1)

Example:

1→2→3→NULL: visit 1, then 2, then 3

Pro Tip:

Always check if current node is not None before accessing

Linked List Insertion

Insert a new node at any position in the linked list

new_node.next = current.next; current.next = new_node

intermediateinterviewcoding

Time: O(1) at position, O(n) to find positionSpace: O(1)

Example:

Insert 5 between 2 and 3: 1→2→5→3→NULL

Pro Tip:

Update next pointers in correct order to avoid losing nodes

Cycle Detection (Floyd's)

Detect if linked list has a cycle using two pointers at different speeds

slow = fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next

advancedinterviewalgorithms

Time: O(n)Space: O(1)

Example:

1→2→3→4→2 (cycle): slow and fast will eventually meet

Pro Tip:

Tortoise and hare algorithm - if there's a cycle, they will meet

Reverse Linked List

Reverse the direction of pointers in a linked list

prev = None; while current: next_temp = current.next; current.next = prev; prev = current; current = next_temp

intermediateinterviewalgorithms

Time: O(n)Space: O(1)

Example:

1→2→3→4→NULL becomes 4→3→2→1→NULL

Pro Tip:

Keep track of previous, current, and next nodes to avoid losing references

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list

dummy = ListNode(0); current = dummy; while l1 and l2: if l1.val <= l2.val: current.next = l1; l1 = l1.next

intermediateinterviewmerge

Time: O(n + m)Space: O(1)

Example:

1→2→4 + 1→3→4 = 1→1→2→3→4→4

Pro Tip:

Use dummy node to simplify edge cases

Find Middle Node

Find the middle node of a linked list using two pointers

slow = fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next

intermediateinterviewalgorithms

Time: O(n)Space: O(1)

Example:

1→2→3→4→5: slow stops at 3 (middle node)

Pro Tip:

When fast reaches end, slow is at middle

Data Structures & AlgorithmsCheat Sheet

1Arrays & Strings

Array Access

Linear Search

Binary Search

Two Pointers Technique

Fixed Sliding Window

Kadane's Algorithm (Max Subarray)

Prefix Sum Array

Dutch National Flag (3-way Partition)

2Linked Lists

Linked List Traversal

Linked List Insertion

Cycle Detection (Floyd's)

Reverse Linked List

Merge Two Sorted Lists

Find Middle Node

1
Arrays & Strings

2
Linked Lists