DSA Problems & Solutions

Python Edition
10 core topics · 25 curated problems · clean Python solutions with complexity
analysis

Table of Contents
1. Arrays
2. Linked Lists
3. Stacks & Queues
4. Trees & Binary Search Trees
5. Graphs
6. Dynamic Programming
7. Sorting & Searching
8. Hashing
9. Heaps & Priority Queues
10. Recursion & Backtracking
 1. Arrays

Two Sum Easy

Problem
Given an array of integers nums and an integer target, return indices of the two numbers that add up to
target.

Approach
Use a hash map to store each number's index. For every element, check if (target - element) already
exists in the map.

Complexity
Time: O(n) | Space: O(n)

Python Solution

def two_sum(nums, target):

seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []

# Example
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]

Mediu
Maximum Subarray (Kadane's Algorithm) m

Problem
Find the contiguous subarray with the largest sum.

Approach
Track the current running sum. Reset to 0 when it goes negative. Update the global max at every step.

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

Python Solution
 def max_subarray(nums):
max_sum = nums[0]
current = nums[0]
for n in nums[1:]:
current = max(n, current + n)
max_sum = max(max_sum, current)
return max_sum

# Example
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4])) # 6

Mediu
Rotate Array m

Problem
Rotate an array to the right by k steps in-place.

Approach
Reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements.

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

Python Solution

def rotate(nums, k):

n = len(nums)
k %= n
[Link]()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])

# Example
arr = [1,2,3,4,5,6,7]
rotate(arr, 3)
print(arr) # [5, 6, 7, 1, 2, 3, 4]
 2. Linked Lists

Reverse a Linked List Easy

Problem
Reverse a singly linked list iteratively.

Approach
Use three pointers: prev, curr, next. Iteratively flip the next pointer of each node.

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

Python Solution

class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

def reverse_list(head):
prev, curr = None, head
while curr:
nxt = [Link]
[Link] = prev
prev = curr
curr = nxt
return prev

Mediu
Detect Cycle in Linked List m

Problem
Determine if a linked list has a cycle.

Approach
Floyd's two-pointer (slow/fast). If they ever meet, a cycle exists.

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

Python Solution
def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow is fast:
return True
return False
 3. Stacks & Queues

Valid Parentheses Easy

Problem
Given a string of brackets, determine if it is valid (correctly opened and closed).

Approach
Use a stack. Push opening brackets; for closing brackets, pop and check for a match.

Complexity
Time: O(n) | Space: O(n)

Python Solution

def is_valid(s):
stack = []
mapping = {')':'(', '}':'{', ']':'['}
for ch in s:
if ch in mapping:
top = [Link]() if stack else '#'
if mapping[ch] != top:
return False
else:
[Link](ch)
return not stack

print(is_valid('()[]{}')) # True
print(is_valid('([)]')) # False

Mediu
Implement Queue using Two Stacks m

Problem
Implement a FIFO queue using only two stacks.

Approach
Push to stack1. On pop/peek, if stack2 is empty, transfer all elements from stack1 to stack2 (reversing
order), then pop from stack2.

Complexity
Time: O(1) amortised | Space: O(n)

Python Solution
class MyQueue:
def __init__(self):
self.s1, self.s2 = [], []

def push(self, x):

[Link](x)

def _transfer(self):
if not self.s2:
while self.s1:
[Link]([Link]())

def pop(self):
self._transfer()
return [Link]()

def peek(self):
self._transfer()
return self.s2[-1]

def empty(self):
return not self.s1 and not self.s2
 4. Trees & Binary Search Trees

Binary Tree Inorder Traversal Easy

Problem
Return the inorder traversal (left, root, right) of a binary tree.

Approach
Recursive DFS: traverse left subtree, visit root, traverse right subtree.

Complexity
Time: O(n) | Space: O(h) where h = height

Python Solution

class TreeNode:
def __init__(self, val=0, left=None, right=None):
[Link] = val
[Link] = left
[Link] = right

def inorder(root):
res = []
def dfs(node):
if not node: return
dfs([Link])
[Link]([Link])
dfs([Link])
dfs(root)
return res

Maximum Depth of Binary Tree Easy

Problem
Find the maximum depth (number of nodes along the longest root-to-leaf path).

Approach
DFS: depth = 1 + max(depth(left), depth(right)). Base case: None returns 0.

Complexity
Time: O(n) | Space: O(h)

Python Solution
 def max_depth(root):
if not root:
return 0
return 1 + max(max_depth([Link]), max_depth([Link]))

Mediu
Validate Binary Search Tree m

Problem
Determine if a binary tree is a valid BST.

Approach
Pass min/max bounds through recursion. Every node must be strictly between its allowed range.

Complexity
Time: O(n) | Space: O(h)

Python Solution

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):

if not root:
return True
if not (lo < [Link] < hi):
return False
return (is_valid_bst([Link], lo, [Link]) and
is_valid_bst([Link], [Link], hi))
 5. Graphs

Mediu
BFS – Shortest Path in Unweighted Graph m

Problem
Find the shortest path between two nodes in an unweighted directed graph.

Approach
Use a queue (BFS). Track visited nodes to avoid cycles. Level = distance from source.

Complexity
Time: O(V + E) | Space: O(V)

Python Solution

from collections import deque

def bfs(graph, start, end):

queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = [Link]()
if node == end:
return path
for nb in [Link](node, []):
if nb not in visited:
[Link](nb)
[Link]((nb, path + [nb]))
return []

graph = {0:[1,2], 1:[3], 2:[3,4], 3:[5], 4:[5], 5:[]}

print(bfs(graph, 0, 5)) # [0, 1, 3, 5]

Mediu
Number of Islands (DFS) m

Problem
Given a 2D grid of '1' (land) and '0' (water), count the number of islands.

Approach
DFS from each unvisited land cell, marking all connected '1's as visited. Count each DFS launch.

Complexity
Time: O(m*n) | Space: O(m*n)
Python Solution

def num_islands(grid):
if not grid: return 0
count = 0
def dfs(r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
return
if grid[r][c] != '1': return
grid[r][c] = '0'
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(r+dr, c+dc)
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
 6. Dynamic Programming

Climbing Stairs Easy

Problem
You can climb 1 or 2 steps at a time. How many distinct ways can you climb n stairs?

Approach
Classic Fibonacci DP. ways[i] = ways[i-1] + ways[i-2]. Use two variables to save space.

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

Python Solution

def climb_stairs(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b

print(climb_stairs(5)) # 8

Mediu
0/1 Knapsack m

Problem
Given weights and values of n items, maximise value in a knapsack of capacity W.

Approach
Build a 2-D DP table dp[i][w] = max value using first i items with capacity w. Fill row by row.

Complexity
Time: O(n*W) | Space: O(n*W)

Python Solution
 def knapsack(W, weights, values, n):
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(W+1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
values[i-1] + dp[i-1][w - weights[i-1]])
return dp[n][W]

print(knapsack(50, [10,20,30], [60,100,120], 3)) # 220

Mediu
Longest Common Subsequence m

Problem
Find the length of the longest common subsequence of two strings.

Approach
2-D DP. If characters match: dp[i][j] = 1 + dp[i-1][j-1], else take max of dp[i-1][j] and dp[i][j-1].

Complexity
Time: O(m*n) | Space: O(m*n)

Python Solution

def lcs(text1, text2):

m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

print(lcs('abcde', 'ace')) # 3
 7. Sorting & Searching

Binary Search Easy

Problem
Search for a target in a sorted array. Return index or -1.

Approach
Maintain lo/hi pointers. Check midpoint; shift lo or hi based on comparison.

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

Python Solution

def binary_search(nums, target):

lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1

print(binary_search([1,3,5,7,9,11], 7)) # 3

Mediu
Merge Sort m

Problem
Sort an array using the merge sort algorithm.

Approach
Divide array in half recursively. Merge two sorted halves by comparing front elements.

Complexity
Time: O(n log n) | Space: O(n)

Python Solution
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):

result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result

print(merge_sort([38,27,43,3,9,82,10]))
# [3, 9, 10, 27, 38, 43, 82]
 8. Hashing

Mediu
Group Anagrams m

Problem
Group all anagrams together from a list of strings.

Approach
Use a hash map. Key = sorted tuple of characters. Append each word to its group.

Complexity
Time: O(n * k log k) | Space: O(n*k) where k = max word length

Python Solution

from collections import defaultdict

def group_anagrams(strs):
groups = defaultdict(list)
for word in strs:
key = tuple(sorted(word))
groups[key].append(word)
return list([Link]())

print(group_anagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
 9. Heaps & Priority Queues

Mediu
K Largest Elements m

Problem
Return the k largest elements from an array.

Approach
Maintain a min-heap of size k. If a new element is larger than the heap root, replace it.

Complexity
Time: O(n log k) | Space: O(k)

Python Solution

import heapq

def k_largest(nums, k):

return [Link](k, nums)

# Manual heap approach

def k_largest_manual(nums, k):
heap = nums[:k]
[Link](heap)
for n in nums[k:]:
if n > heap[0]:
[Link](heap, n)
return sorted(heap, reverse=True)

print(k_largest([3,2,1,5,6,4], 2)) # [6, 5]

 10. Recursion & Backtracking

Mediu
Generate All Subsets m

Problem
Return all possible subsets (power set) of a list of unique integers.

Approach
Backtracking: at each index decide to include or exclude the element. Add current subset to result.

Complexity
Time: O(2^n * n) | Space: O(2^n * n)

Python Solution

def subsets(nums):
result = []
def backtrack(start, current):
[Link](list(current))
for i in range(start, len(nums)):
[Link](nums[i])
backtrack(i + 1, current)
[Link]()
backtrack(0, [])
return result

print(subsets([1,2,3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

N-Queens Problem Hard

Problem
Place N queens on an N×N chessboard such that no two queens attack each other.

Approach
Backtracking row by row. Track columns, diagonals, and anti-diagonals used. Backtrack on conflict.

Complexity
Time: O(n!) | Space: O(n)

Python Solution
def solve_n_queens(n):
res = []
cols = diag1 = diag2 = set()
board = [['.']*n for _ in range(n)]
def bt(r):
if r == n:
[Link]([''.join(row) for row in board])
return
for c in range(n):
if c in cols or (r-c) in diag1 or (r+c) in diag2:
continue
board[r][c] = 'Q'
[Link](c); [Link](r-c); [Link](r+c)
bt(r + 1)
board[r][c] = '.'
[Link](c); [Link](r-c); [Link](r+c)
bt(0)
return res

print(len(solve_n_queens(8))) # 92 solutions
Practice Tips
1. Solve each problem on your own before reading the solution.

2. Understand the time and space complexity — don't just memorise code.

3. Re-implement solutions from scratch after 2–3 days.

4. Platforms: LeetCode, HackerRank, Codeforces, [Link]