DSA Cheatsheet (Very Easy)

1. Arrays

Core concept: Array stores elements in continuous memory, so index access is fast.

Time: Access O(1), Search O(n).

arr = [10, 20, 30, 40]
print(arr[2])

Output: 30

2. Two Pointers

Core concept: Use two indexes to reduce nested loops in sorted arrays/strings.

a = [1, 2, 3, 4, 6]
target = 7
l, r = 0, len(a)-1
while l < r:
    s = a[l] + a[r]
    if s == target:
        print(l, r)
        break
    if s < target:
        l += 1
    else:
        r -= 1

Output: 0 4

3. Sliding Window

Core concept: Keep a moving window for subarray/substring problems.

a = [2,1,5,1,3,2]
k = 3
cur = sum(a[:k])
best = cur
for i in range(k, len(a)):
    cur += a[i] - a[i-k]
    best = max(best, cur)
print(best)

Output: 9

4. Linked List

Core concept: Nodes connected by pointers; insertion/deletion is easy when pointer is known.

# reverse linked list logic
prev = None
cur = head
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
head = prev

Output: List is reversed.

5. Stack

Core concept: LIFO (Last In First Out), useful in parentheses and next greater element problems.

s = []
s.append(10)
s.append(20)
print(s.pop())

Output: 20

6. Queue

Core concept: FIFO (First In First Out), used heavily in BFS.

from collections import deque
q = deque([1,2,3])
q.append(4)
print(q.popleft())

Output: 1

7. Binary Search

Core concept: Repeatedly divide sorted range into half.

Time: O(log n)

a = [1,3,5,7,9]
x = 7
l, r = 0, len(a)-1
while l <= r:
    m = (l+r)//2
    if a[m] == x:
        print(m)
        break
    if a[m] < x:
        l = m+1
    else:
        r = m-1

Output: 3

8. Trees (DFS)

Core concept: DFS goes deep first; recursion is common.

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val, end=" ")
    inorder(root.right)

Output: Inorder traversal sequence.

9. Graph BFS

Core concept: BFS visits level by level and finds shortest path in unweighted graph.

from collections import deque
g = {0:[1,2], 1:[3], 2:[3], 3:[]}
q = deque([0]); vis = {0}
while q:
    u = q.popleft()
    print(u, end=" ")
    for v in g[u]:
        if v not in vis:
            vis.add(v)
            q.append(v)

Output: 0 1 2 3

10. Recursion & Backtracking

Core concept: Build solution step by step, undo step when path fails.

res = []
def backtrack(path, nums):
    if len(path) == len(nums):
        res.append(path[:]); return
    for x in nums:
        if x in path:
            continue
        path.append(x)
        backtrack(path, nums)
        path.pop()

Output: Generates all permutations.

11. Dynamic Programming

Core concept: Store repeated subproblem answers to avoid recomputation.

# Fibonacci DP
n = 6
dp = [0,1] + [0]*(n-1)
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

Output: 8

12. Complexity Quick Table

Interview tip: Always say time and space complexity after your solution.