DSA Interview Practice Sheet

Problem 1: Maximum Subarray Sum (Kadane’s

Algorithm)
Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number)
which has the largest sum, and return the sum.

Example:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6
Explanation: [4, -1, 2, 1] has the largest sum = 6

Logic & Explanation

1. A subarray is a continuous part of the array.
Example: For [1,2,3] → subarrays are [1], [1,2], [2,3], [1,2,3], [3].
2. Brute Force Approach
o Check all subarrays.
o Compute sum of each.
o Find the maximum.
Time Complexity → O(n^2) or O(n^3) (too slow for big inputs).
3. Optimized Approach (Kadane’s Algorithm)
o Idea: Keep a running sum (current_sum).
o If current_sum becomes negative, reset it to 0 (because negative sum won’t
help future subarrays).
o Keep track of max_sum (the maximum seen so far).

Steps:

o Initialize:
max_sum = nums[0], current_sum = 0
o Loop through array:
§ Add current element → current_sum += nums[i]
§ Update max_sum = max(max_sum, current_sum)
§ If current_sum < 0, reset current_sum = 0

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 Time Complexity: O(n)
Space Complexity: O(1)

Python Code
def max_subarray(nums):
max_sum = nums[0] # store the maximum sum found
current_sum = 0 # store the current running sum

for num in nums:

current_sum += num
max_sum = max(max_sum, current_sum)

# reset if current_sum becomes negative

if current_sum < 0:
current_sum = 0

return max_sum

# Example run
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray(arr))

Problem 2: Rotate an Array by k Steps

Problem Statement
Given an array, rotate the array to the right by k steps, where k is non-negative.

Example:

Input: nums = [1,2,3,4,5,6,7], k = 3

Output: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 step → [7,1,2,3,4,5,6]
Rotate 2 steps → [6,7,1,2,3,4,5]
Rotate 3 steps → [5,6,7,1,2,3,4]

Logic & Explanation

1. Brute Force Approach
o Rotate one step at a time → repeat k times.
o Time Complexity: O(n * k) (too slow when k is large).
2. Optimized Approach
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 o Observe that rotating k times to the right = moving the last k elements to the
front.
o Example: [1,2,3,4,5,6,7], k=3 → split into:
§ Last 3 elements: [5,6,7]
§ First part: [1,2,3,4]
§ Combine → [5,6,7,1,2,3,4]

Steps:

o Do k = k % n (because rotating n times gives the same array).

o Slice and rearrange: nums[-k:] + nums[:-k]

Time Complexity: O(n)

Space Complexity: O(n) (or O(1) if done in-place).

Python Code
def rotate_array(nums, k):
n = len(nums)
k = k % n # handle if k > n
return nums[-k:] + nums[:-k]

# Example run
arr = [1,2,3,4,5,6,7]
k = 3
print("Rotated Array:", rotate_array(arr, k))

Problem 3: Find the Missing Number in 1…n

Problem Statement
You are given an array containing n distinct numbers taken from 0, 1, 2, …, n.
Since one number is missing from the set, return that missing number.

Example:

Input: nums = [3, 0, 1]

Output: 2
Explanation: Numbers are from 0…3, and 2 is missing.

Logic & Explanation

1. Brute Force Approach
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 o Sort the array.
o Check which number in 0…n is missing.
o Time Complexity: O(n log n).
2. Better Approach (Hashing / Set)
o Put all numbers in a set.
o Iterate from 0…n and check which number is not in set.
o Time Complexity: O(n), Space: O(n).
3. Optimal Approach (Mathematical Formula)
o Sum of first n natural numbers = n*(n+1)//2.
o Missing number = (expected_sum - actual_sum).
o Time Complexity: O(n), Space: O(1).

Example:

nums = [3, 0, 1]
n = 3
expected_sum = 3*4/2 = 6
actual_sum = 3+0+1 = 4
missing = 6-4 = 2

Python Code
def find_missing_number(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum

# Example run
arr = [3, 0, 1]
print("Missing Number:", find_missing_number(arr))

Problem 4: Find the Duplicate Element

Problem Statement
You are given an array of n+1 integers where each integer is between 1 and n (inclusive).
There is only one duplicate number, return this duplicate.

Example:

Input: nums = [1, 3, 4, 2, 2]

Output: 2

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Logic & Explanation
1. Brute Force Approach
o Compare each element with every other.
o Time Complexity: O(n^2).
2. Sorting Approach
o Sort the array.
o Duplicate will appear consecutively.
o Time Complexity: O(n log n).
3. Hashing / Set Approach
o Keep a set.
o While iterating, if element already exists → that’s duplicate.
o Time Complexity: O(n), Space: O(n).
4. Optimal Approach (Floyd’s Cycle Detection Algorithm – Tortoise & Hare)
o Treat the array like a linked list where nums[i] points to nums[nums[i]].
o Since there’s a duplicate, there will be a cycle.
o Use slow & fast pointers to detect the cycle → entry point of cycle =
duplicate.
o Time Complexity: O(n), Space: O(1) → Best method (often asked in
Amazon, Microsoft).

Python Code (Using Set)

def find_duplicate(nums):
seen = set()
for num in nums:
if num in seen:
return num
[Link](num)
return -1 # if no duplicate (should not happen as per problem)

# Example run
arr = [1, 3, 4, 2, 2]
print("Duplicate Element:", find_duplicate(arr))

Python Code (Floyd’s Tortoise & Hare – Optimal)

def find_duplicate(nums):
# Phase 1: Detect cycle
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 # Phase 2: Find entrance to cycle
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]

return slow

# Example run
arr = [1, 3, 4, 2, 2]
print("Duplicate Element (Optimal):", find_duplicate(arr))

Problem 5: Merge Two Sorted Arrays

Problem Statement
You are given two sorted arrays arr1 and arr2.
Merge them into a single sorted array.

Example 1:

Input: arr1 = [1,3,5], arr2 = [2,4,6]

Output: [1,2,3,4,5,6]

Example 2 (different sizes):

Input: arr1 = [1,2,7,10], arr2 = [3,5,6]

Output: [1,2,3,5,6,7,10]

Logic & Explanation

1. Brute Force
o Combine both arrays → arr1 + arr2.
o Sort the result.
o Time Complexity: O((m+n) log(m+n)).
2. Optimal (Two Pointers Technique)
o Since both arrays are already sorted:
§ Keep two pointers → i for arr1, j for arr2.
§ Compare elements at arr1[i] and arr2[j].
§ Pick the smaller and move that pointer.
§ Continue until one array finishes.
§ Copy remaining elements.
o Time Complexity: O(m+n)
o Space Complexity: O(m+n)

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Python Code (Two Pointers Method)
def merge_sorted_arrays(arr1, arr2):
i, j = 0, 0
merged = []

# Compare elements from both arrays

while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
[Link](arr1[i])
i += 1
else:
[Link](arr2[j])
j += 1

# Add remaining elements

while i < len(arr1):
[Link](arr1[i])
i += 1
while j < len(arr2):
[Link](arr2[j])
j += 1

return merged

# Example run
arr1 = [1,3,5]
arr2 = [2,4,6]
print("Merged Array:", merge_sorted_arrays(arr1, arr2))

Problem 6: Sort an Array of 0s, 1s, and 2s

Problem Statement
Given an array nums containing only 0, 1, and 2, sort the array in-place (without using built-
in sort).

Example:

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Logic & Explanation

1. Brute Force
o Just sort using Python’s built-in sort().
o Time Complexity: O(n log n) (not allowed in interviews).
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 2. Counting Approach
o Count number of 0s, 1s, and 2s.
o Rewrite the array.
o Time Complexity: O(n), Space: O(1).
o Not considered best in interviews because it requires 2 passes.
3. Optimal Approach (Dutch National Flag Algorithm)
o Use three pointers:
§ low → boundary for 0s.
§ mid → current element.
§ high → boundary for 2s.
o Rules:
§ If nums[mid] == 0 → swap with low, move both low & mid.
§ If nums[mid] == 1 → just move mid.
§ If nums[mid] == 2 → swap with high, move high (but don’t move
mid).
o Time Complexity: O(n)
o Space Complexity: O(1)

Python Code (Dutch National Flag Algorithm)

def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1

while mid <= high:

if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums

# Example run
arr = [2,0,2,1,1,0]
print("Sorted Array:", sort_colors(arr))

Problem 7: Two Sum (Find Pair with Given Sum)

Problem Statement

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Given an array of integers nums and an integer target, return indices of the two numbers
such that they add up to target.

You may assume that each input has exactly one solution, and you may not use the same
element twice.

Example:

Input: nums = [2,7,11,15], target = 9

Output: [0,1] # because nums[0] + nums[1] = 2 + 7 = 9

Logic & Explanation

1. Brute Force
o Check all pairs (i, j).
o If nums[i] + nums[j] == target, return indices.
o Time Complexity: O(n^2).
2. Optimal Approach (Hash Map)
o Use a dictionary (hash map) to store numbers and their indices.
o While iterating:
§ For each number x, check if (target - x) is already in map.
§ If yes → found the pair.
§ Otherwise, store x in map.
o Time Complexity: O(n)
o Space Complexity: O(n)

Python Code (Hash Map Method)

def two_sum(nums, target):
num_map = {} # value → index

for i, num in enumerate(nums):

complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i

return [] # if no solution (but guaranteed one solution)

# Example run
arr = [2, 7, 11, 15]
target = 9
print("Indices:", two_sum(arr, target))

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 Problem 8: Maximum Product Subarray
Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number)
which has the largest product, and return the product.

Example:

Input: nums = [2,3,-2,4]

Output: 6
Explanation: [2,3] has the largest product = 6

Logic & Explanation

1. Why not simple Kadane’s Algorithm?
o Kadane’s works for sum, but product is tricky because:
§ Negative × Negative = Positive
§ Zero resets the product

Example:

nums = [2,3,-2,4]
max product is 6 (from [2,3])

But if array has [-2, 3, -4],

max product is 24 (from [-2, 3, -4]) because negatives flip signs.

2. Key Idea
o At each step, we need to keep track of:
§ max_product (maximum till now)
§ min_product (minimum till now, because multiplying with negative
may give new max)
o Formula:
o temp = max_product
o max_product = max(num, num*max_product, num*min_product)
o min_product = min(num, num*temp, num*min_product)
o Update result = max(result, max_product)
3. Time Complexity: O(n)
Space Complexity: O(1)

Python Code
def max_product_subarray(nums):
max_product = nums[0]
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 min_product = nums[0]
result = nums[0]

for num in nums[1:]:

temp = max_product
max_product = max(num, num * max_product, num * min_product)
min_product = min(num, num * temp, num * min_product)
result = max(result, max_product)

return result

# Example run
arr = [2,3,-2,4]
print("Maximum Product Subarray:", max_product_subarray(arr))

Problem 9: Longest Substring Without Repeating

Characters
Problem Statement
Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with length 3.

Logic & Explanation

This is a sliding window problem.

1. We need to maintain a window (substring) that contains no duplicate characters.

2. Use a set or dictionary to track characters inside the window.
3. Expand the window using a right pointer.
4. If a duplicate is found → shrink the window from the left.
5. Keep updating the maximum length found so far.

Example Walkthrough:
s = "abcabcbb"

• Start → left=0, right=0 → window = "a", max=1

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 • Expand → "ab", max=2
• Expand → "abc", max=3
• Duplicate "a" → shrink left → "bca" still valid
• Continue → "abc", "cab", max stays 3

Time Complexity: O(n)

(because each character is processed at most twice)

Space Complexity: O(n)

(for storing characters in set/dict)

Python Code
def length_of_longest_substring(s):
char_index = {} # stores last index of each character
left = 0
max_length = 0

for right in range(len(s)):

if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1 # move left pointer
char_index[s[right]] = right
max_length = max(max_length, right - left + 1)

return max_length

# Example run
s = "abcabcbb"
print("Length of Longest Substring:", length_of_longest_substring(s))

Problem 10: Check if Two Strings are Anagrams

Problem Statement
Two strings are called anagrams if they contain the same characters with the same
frequency, but possibly in a different order.

Example:

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Input: s1 = "listen", s2 = "silent"
Output: True
Explanation: Both have the same letters, just in different order.

Logic & Explanation

We can solve in multiple ways:

Approach 1: Sorting (Easy but slower)

1. Sort both strings.

2. If they are equal → return True.
3. Else → False.

• Time: O(n log n)

Approach 2: Frequency Count (Efficient)

1. Count characters of both strings using a dictionary (or [Link]).

2. If both counts match → strings are anagrams.

• Time: O(n)
• Space: O(1) (since alphabet size is fixed)

Python Code
Approach 1: Sorting
def are_anagrams_sorting(s1, s2):
return sorted(s1) == sorted(s2)

# Example run
print(are_anagrams_sorting("listen", "silent")) # True
print(are_anagrams_sorting("hello", "world")) # False

Approach 2: Frequency Dictionary

from collections import Counter

def are_anagrams_count(s1, s2):

return Counter(s1) == Counter(s2)

# Example run
print(are_anagrams_count("listen", "silent")) # True
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
print(are_anagrams_count("race", "care")) # True
print(are_anagrams_count("rat", "car")) # False

Problem 11: Reverse Words in a String

Problem Statement
Given a string s containing words separated by spaces, reverse the order of words.

• Words are separated by one or more spaces.

• The reversed string should have single spaces between words and no leading/trailing
spaces.

Example:

Input: s = " hello world "

Output: "world hello"

Logic & Explanation

1. Step 1: Split the string into words
o Remove extra spaces using split().
o Example: " hello world ".split() → ["hello", "world"]
2. Step 2: Reverse the list of words
o words[::-1]
3. Step 3: Join words with a single space
o ' '.join(reversed_words)

Time Complexity: O(n)

Space Complexity: O(n)

Python Code
def reverse_words(s):
# Split string into words and remove extra spaces
words = [Link]()
# Reverse the list of words
reversed_words = words[::-1]
# Join words with a single space
return ' '.join(reversed_words)

# Example run

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
s = " hello world "
print("Reversed Words:", reverse_words(s))

Problem 12: Substring Search (Implement strStr /

KMP Basics)
Problem Statement
Given two strings haystack and needle, return the index of the first occurrence of needle
in haystack, or -1 if needle is not part of haystack.

Example:

Input: haystack = "hello", needle = "ll"

Output: 2

Logic & Explanation

Approach 1: Simple Sliding Window (Naive)

1. Loop over haystack from index 0 to len(haystack) - len(needle)

2. For each index, check if substring matches needle.
3. If yes → return index, else continue.

• Time Complexity: O(n*m) (n = len(haystack), m = len(needle))

• Space Complexity: O(1)

Approach 2: KMP Algorithm (Optimized)

• KMP (Knuth-Morris-Pratt) uses a prefix table (LPS array) to skip unnecessary

comparisons.
• Time Complexity: O(n + m)
• Space Complexity: O(m)

For interviews, often the naive solution is enough unless asked for optimization.

Python Code
Approach 1: Naive

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
def str_str(haystack, needle):
if not needle:
return 0 # empty needle

n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i + m] == needle:
return i
return -1

# Example run
haystack = "hello"
needle = "ll"
print("First Occurrence Index:", str_str(haystack, needle))

Approach 2: Using Python Built-in (Shortcut)

haystack = "hello"
needle = "ll"
print([Link](needle)) # returns 2

Recursion & Backtracking

Problem 13: Factorial of a Number

Problem Statement:
Compute factorial of n (n! = n * (n-1) * ... * 1) using recursion.

Logic:

• Base Case: factorial(0) = 1

• Recursive Case: factorial(n) = n * factorial(n-1)

Python Code:

def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n-1)

# Example
print("5! =", factorial(5))

Output:

5! = 120

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem 14: Fibonacci Using Recursion
Problem Statement:
Print the nth Fibonacci number: 0, 1, 1, 2, 3, 5, ...

Logic:

• Base Case: fib(0)=0, fib(1)=1

• Recursive: fib(n) = fib(n-1) + fib(n-2)

Python Code:

def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)

# Example
print("Fibonacci(6) =", fibonacci(6))

Output:

Fibonacci(6) = 8

Problem 15: Print All Permutations of a String

Problem Statement:
Generate all permutations of a string "ABC".

Logic:

• Swap each character with others recursively.

• Base Case: when start index reaches end of string → print.

Python Code:

def permute(s, start=0):

if start == len(s) - 1:
print("".join(s))
return
for i in range(start, len(s)):
s[start], s[i] = s[i], s[start]
permute(s, start + 1)
s[start], s[i] = s[i], s[start] # backtrack

# Example
permute(list("ABC"))

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Output:

ABC
ACB
BAC
BCA
CBA
CAB

Problem 16: Tower of Hanoi

Problem Statement:
Move n disks from source to destination using auxiliary rod following rules:

1. Only one disk at a time.

2. Bigger disk cannot be on top of smaller disk.

Logic:

• Move n-1 disks to auxiliary.

• Move nth disk to destination.
• Move n-1 disks from auxiliary to destination.

Python Code:

def tower_of_hanoi(n, source, auxiliary, destination):

if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n-1, source, destination, auxiliary)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n-1, auxiliary, source, destination)

# Example
tower_of_hanoi(3, 'A', 'B', 'C')

Output:

Move disk 1 from A to C

Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Problem 17: Generate All Subsets of a Set (Power Set)

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem Statement:
Generate all subsets of [1,2,3].

Logic:

• Include current element → recurse

• Exclude current element → recurse

Python Code:

def subsets(nums, index=0, current=[]):

if index == len(nums):
print(current)
return
# Include nums[index]
subsets(nums, index + 1, current + [nums[index]])
# Exclude nums[index]
subsets(nums, index + 1, current)

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

Output:

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

Problem 18: N-Queens Problem

Problem Statement:
Place N queens on an N×N chessboard so that no two queens threaten each other. Print all
solutions.

Logic:

• Use backtracking row by row.

• Check column, diagonal, anti-diagonal before placing.

Python Code (N=4 example):

def solve_nqueens(n):
board = [-1]*n # board[i] = column of queen in row i
def is_safe(row, col):
for r in range(row):
c = board[r]

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 if c == col or abs(r - row) == abs(c - col):
return False
return True
def place_queen(row):
if row == n:
print(board)
return
for col in range(n):
if is_safe(row, col):
board[row] = col
place_queen(row+1)
board[row] = -1 # backtrack
place_queen(0)

# Example
solve_nqueens(4)

Output (column positions per row):

[1, 3, 0, 2]
[2, 0, 3, 1]

Problem 19: Rat in a Maze

Problem Statement:
Find all paths for a rat from top-left (0,0) to bottom-right (n-1,n-1) in a maze (1=path,
0=blocked).

Logic:

• Move in four directions recursively (Down, Right, Up, Left).

• Mark visited cells.
• Backtrack to explore all paths.

Python Code:

def rat_in_maze(maze):
n = len(maze)
path = []
visited = [[False]*n for _ in range(n)]

def backtrack(x, y):

if x == n-1 and y == n-1:
print(path)
return
moves = [(0,1),(1,0),(0,-1),(-1,0)] # R, D, L, U
for dx, dy in moves:
nx, ny = x+dx, y+dy
if 0<=nx<n and 0<=ny<n and maze[nx][ny]==1 and not
visited[nx][ny]:
visited[nx][ny] = True
[Link]((nx,ny))
backtrack(nx, ny)

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 [Link]()
visited[nx][ny] = False

visited[0][0] = True
[Link]((0,0))
backtrack(0,0)

# Example
maze = [[1,0,0],
[1,1,0],
[0,1,1]]
rat_in_maze(maze)

Output (paths as coordinates):

[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)]

Problem 20: Word Search in a Grid

Problem Statement:
Given a 2D grid of letters and a word, check if the word exists in the grid (horizontally or
vertically, letters must be adjacent).

Logic:

• Use DFS for each cell that matches the first character.
• Track visited cells.
• Recurse for next character in 4 directions.

Python Code:

def exist(board, word):

rows, cols = len(board), len(board[0])
def dfs(r, c, index):
if index == len(word):
return True
if r<0 or r>=rows or c<0 or c>=cols or board[r][c] != word[index]:
return False
temp = board[r][c]
board[r][c] = "#" # mark visited
found = (dfs(r+1,c,index+1) or dfs(r-1,c,index+1) or
dfs(r,c+1,index+1) or dfs(r,c-1,index+1))
board[r][c] = temp
return found
for i in range(rows):
for j in range(cols):
if dfs(i,j,0):
return True
return False

# Example
board = [["A","B","C","E"],
["S","F","C","S"],

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 ["A","D","E","E"]]
word = "ABCCED"
print("Word Found:", exist(board, word))

Output:

Word Found: True

Searching & Sorting

Problem 21: Binary Search

Problem Statement:
Given a sorted array nums and a target value target, return the index of target in nums, or
-1 if not found.

Logic:

• Use divide & conquer.

• Check middle element:
o If equal → return index
o If target < mid → search left
o If target > mid → search right

Python Code:

def binary_search(nums, target):

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

# Example
arr = [1,3,5,7,9]
print("Index of 5:", binary_search(arr, 5))

Output:

Index of 5: 2

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem 22: First and Last Occurrence (in Sorted Array)
Problem Statement:
Find first and last positions of target in a sorted array.

Logic:

• Use binary search twice: once for first occurrence, once for last occurrence.

Python Code:

def first_last_occurrence(nums, target):

def binary_search_left():
left, right = 0, len(nums)-1
idx = -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
idx = mid
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return idx

def binary_search_right():
left, right = 0, len(nums)-1
idx = -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
idx = mid
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return idx

return [binary_search_left(), binary_search_right()]

# Example
arr = [1,2,2,2,3,4]
print("First & Last Occurrence of 2:", first_last_occurrence(arr,2))

Output:

First & Last Occurrence of 2: [1, 3]

Problem 23: Merge Two Sorted Arrays

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem Statement:
Already covered in Arrays section – Two Pointers Method can be reused.

Problem 24: Find Peak Element

Problem Statement:
A peak element is greater than its neighbors. Return any peak element index.

Logic:

• Use binary search:

o If mid < mid+1 → peak is on the right
o Else → peak is on the left

Python Code:

def find_peak(nums):
left, right = 0, len(nums)-1
while left < right:
mid = (left + right)//2
if nums[mid] < nums[mid+1]:
left = mid + 1
else:
right = mid
return left

# Example
arr = [1,3,4,2,1]
print("Peak Element Index:", find_peak(arr))

Output:

Peak Element Index: 2

Problem 25: Search in Rotated Sorted Array

Problem Statement:
Array is rotated at some pivot. Find index of target.

Logic:

• Binary search with rotation check:

o If left half sorted → check if target in left
o Else → target in right half

Python Code:

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
def search_rotated(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid -1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1

# Example
arr = [4,5,6,7,0,1,2]
print("Index of 0:", search_rotated(arr,0))

Output:

Index of 0: 4

Problem 26: Count Inversions in Array

Problem Statement:
Count number of pairs (i,j) such that i<j and arr[i]>arr[j].

Logic:

• Use Merge Sort modification → count during merge.

Python Code:

def count_inversions(arr):
def merge_sort(nums):
if len(nums) <=1:
return nums,0
mid = len(nums)//2
left,inv_left = merge_sort(nums[:mid])
right,inv_right = merge_sort(nums[mid:])
merged, inv_count = [], inv_left + inv_right
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])
inv_count += len(left)-i
j+=1
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 merged += left[i:] + right[j:]
return merged, inv_count
_, count = merge_sort(arr)
return count

# Example
arr = [2,4,1,3,5]
print("Inversions Count:", count_inversions(arr))

Output:

Inversions Count: 3

Problem 27: Kth Smallest / Largest Element

Problem Statement:
Find kth smallest/largest element in an unsorted array.

Logic:

• Use Heap / QuickSelect for optimal solution.

Python Code (Kth Largest using Heap):

import heapq

def kth_largest(nums, k):

return [Link](k, nums)[-1]

# Example
arr = [3,2,1,5,6,4]
print("2nd Largest:", kth_largest(arr,2))

Output:

2nd Largest: 5

Problem 28: Sort an Array (QuickSort)

Logic:

• Pick a pivot, partition array, recursively sort left and right.

Python Code:

def quicksort(arr):
if len(arr)<=1:
return arr
pivot = arr[len(arr)//2]

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 left = [x for x in arr if x<pivot]
middle = [x for x in arr if x==pivot]
right = [x for x in arr if x>pivot]
return quicksort(left)+middle+quicksort(right)

# Example
arr = [3,6,8,10,1,2,1]
print("Sorted Array:", quicksort(arr))

Output:

Sorted Array: [1, 1, 2, 3, 6, 8, 10]

Problem 29: Search in 2D Matrix

Problem Statement:
Matrix is sorted row-wise & column-wise. Check if target exists.

Logic:

• Start from top-right:

o If > target → move left
o If < target → move down

Python Code:

def search_matrix(matrix, target):

if not matrix: return False
row, col = 0, len(matrix[0])-1
while row<len(matrix) and col>=0:
if matrix[row][col]==target:
return True
elif matrix[row][col]>target:
col -= 1
else:
row += 1
return False

# Example
matrix = [[1,4,7,11],
[2,5,8,12],
[3,6,9,16]]
print("Target 5 Found:", search_matrix(matrix,5))

Output:

Target 5 Found: True

Linked List, Stack & Queue

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem 30: Reverse a Linked List
Problem Statement:
Reverse a singly linked list.

Logic:

• Use three pointers: prev, curr, next.

• Traverse the list, reverse [Link] = prev.

Python Code:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = [Link]
[Link] = prev
prev = curr
curr = next_node
return prev

# Example
head = Node(1)
[Link] = Node(2)
[Link] = Node(3)

rev_head = reverse_linked_list(head)
curr = rev_head
while curr:
print([Link], end=" ")
curr = [Link]

Output:

3 2 1

Problem 31: Detect Cycle in Linked List (Floyd’s

Algorithm)
Problem Statement:
Check if a linked list has a cycle.

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Logic:

• Use slow and fast pointers:

o Slow moves 1 step, fast moves 2 steps.
o If they meet → cycle exists.

Python Code:

def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
return True
return False

# Example
head = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = head # cycle
print("Cycle Detected:", has_cycle(head))

Output:

Cycle Detected: True

Problem 32: Find Middle of a Linked List

Problem Statement:
Find the middle node of a linked list.

Logic:

• Use slow and fast pointers:

o Slow moves 1 step, fast moves 2 steps.
o When fast reaches end, slow is at middle.

Python Code:

def find_middle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
return [Link]

# Example
head = Node(1)
[Link] = Node(2)
[Link] = Node(3)
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
[Link] = Node(4)
print("Middle Node:", find_middle(head))

Output:

Middle Node: 2

Problem 33: Merge Two Sorted Linked Lists

Problem Statement:
Merge two sorted linked lists into a single sorted list.

Logic:

• Use dummy node and two pointers to traverse both lists.

Python Code:

def merge_sorted_lists(l1, l2):

dummy = Node(0)
tail = dummy
while l1 and l2:
if [Link] < [Link]:
[Link] = l1
l1 = [Link]
else:
[Link] = l2
l2 = [Link]
tail = [Link]
[Link] = l1 or l2
return [Link]

# Example
l1 = Node(1); [Link] = Node(3); [Link] = Node(5)
l2 = Node(2); [Link] = Node(4); [Link] = Node(6)
merged = merge_sorted_lists(l1,l2)
curr = merged
while curr:
print([Link], end=" ")
curr = [Link]

Output:

1 2 3 4 5 6

Problem 34: Implement Stack using Array & Linked List

Logic (Array):

• Use Python list with append() and pop().

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
class StackArray:
def __init__(self):
[Link] = []
def push(self, val):
[Link](val)
def pop(self):
if [Link]:
return [Link]()
def peek(self):
return [Link][-1] if [Link] else None

# Example
s = StackArray()
[Link](1); [Link](2); [Link](3)
print("Top:", [Link]())
print("Pop:", [Link]())

Output:

Top: 3
Pop: 3

Logic (Linked List):

• Use head as top.

class StackNode:
def __init__(self, data):
[Link] = data
[Link] = None

class StackLinkedList:
def __init__(self):
[Link] = None
def push(self, val):
node = StackNode(val)
[Link] = [Link]
[Link] = node
def pop(self):
if [Link]:
val = [Link]
[Link] = [Link]
return val
def peek(self):
return [Link] if [Link] else None

# Example
s = StackLinkedList()
[Link](1); [Link](2)
print("Top:", [Link]())
print("Pop:", [Link]())

Output:

Top: 2
Pop: 2

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem 35: Implement Queue using Array & Linked
List
Logic (Array):

• Use append() for enqueue, pop(0) for dequeue.

class QueueArray:
def __init__(self):
self.q = []
def enqueue(self, val):
[Link](val)
def dequeue(self):
return [Link](0) if self.q else None
def front(self):
return self.q[0] if self.q else None

# Example
q = QueueArray()
[Link](1); [Link](2)
print("Front:", [Link]())
print("Dequeue:", [Link]())

Output:

Front: 1
Dequeue: 1

Logic (Linked List):

• Use head = front, tail = rear.

class QueueNode:
def __init__(self, data):
[Link] = data
[Link] = None

class QueueLinkedList:
def __init__(self):
[Link] = [Link] = None
def enqueue(self, val):
node = QueueNode(val)
if not [Link]:
[Link] = [Link] = node
return
[Link] = node
[Link] = node
def dequeue(self):
if [Link]:
val = [Link]
[Link] = [Link]
if not [Link]:

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 [Link] = None
return val
def peek(self):
return [Link] if [Link] else None

# Example
q = QueueLinkedList()
[Link](1); [Link](2)
print("Front:", [Link]())
print("Dequeue:", [Link]())

Output:

Front: 1
Dequeue: 1

Problem 36: Implement Two Stacks in One Array

Logic:

• Use one array with two pointers: top1 from start, top2 from end.
• Push/Pop accordingly, stop when top1+1 == top2.

class TwoStacks:
def __init__(self, n):
[Link] = n
[Link] = [None]*n
self.top1 = -1
self.top2 = n
def push1(self, val):
if self.top1+1 == self.top2:
print("Overflow")
return
self.top1 += 1
[Link][self.top1] = val
def push2(self, val):
if self.top1+1 == self.top2:
print("Overflow")
return
self.top2 -= 1
[Link][self.top2] = val
def pop1(self):
if self.top1==-1: return None
val = [Link][self.top1]
self.top1 -=1
return val
def pop2(self):
if self.top2==[Link]: return None
val = [Link][self.top2]
self.top2 +=1
return val

# Example
s = TwoStacks(5)
s.push1(1); s.push2(5)
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
print("Pop1:", s.pop1())
print("Pop2:", s.pop2())

Output:

Pop1: 1
Pop2: 5

Problem 37: Next Greater Element (Stack)

Problem Statement:
For each element in array, find next greater element to its right.

Logic:

• Use stack to track candidates from right.

• Pop smaller elements, current element’s NGE = stack top.

def next_greater(nums):
res = [-1]*len(nums)
stack = []
for i in range(len(nums)-1,-1,-1):
while stack and stack[-1]<=nums[i]:
[Link]()
res[i] = stack[-1] if stack else -1
[Link](nums[i])
return res

# Example
arr = [4,5,2,25]
print("Next Greater:", next_greater(arr))

Output:

Next Greater: [5, 25, 25, -1]

Problem 38: Balanced Parentheses (Stack)

Problem Statement:
Check if parentheses in string are balanced ((), {}, []).

Logic:

• Use stack: push opening, pop on closing if matches.

def is_balanced(s):
stack = []
mapping = {')':'(', '}':'{', ']':'['}
for char in s:

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 if char in "({[":
[Link](char)
elif char in ")}]":
if not stack or stack[-1]!=mapping[char]:
return False
[Link]()
return not stack

# Example
s = "{[()]}"
print("Balanced:", is_balanced(s))

Output:

Balanced: True

Problem 39: Implement Circular Queue

Logic:

• Use array and modulo arithmetic for circular movement.

class CircularQueue:
def __init__(self, k):
self.q = [None]*k
[Link] = [Link] = -1
[Link] = k

def enqueue(self, val):

if ([Link]+1) % [Link] == [Link]:
print("Overflow - Queue is Full")
return
if [Link] == -1: # first element
[Link] = 0
[Link] = ([Link]+1) % [Link]
self.q[[Link]] = val

def dequeue(self):
if [Link] == -1:
print("Underflow - Queue is Empty")
return None
val = self.q[[Link]]
if [Link] == [Link]: # only one element left
[Link] = [Link] = -1
else:
[Link] = ([Link]+1) % [Link]
return val

def front(self):
return self.q[[Link]] if [Link] != -1 else None

def display(self):
if [Link] == -1:
print("Queue is Empty")
return

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 i = [Link]
elements = []
while True:
[Link](self.q[i])
if i == [Link]:
break
i = (i+1) % [Link]
print("Queue:", elements)

# Example
cq = CircularQueue(3)

[Link](1)
[Link](2)
[Link](3) # Queue is full now
[Link]()

print("Dequeue:", [Link]()) # removes 1

[Link]()

[Link](4) # Now 4 is inserted in place of 1 (circular)

[Link]()

print("Front Element:", [Link]())

print("Dequeue:", [Link]())
[Link]()

40. Inorder, Preorder, Postorder Traversals (Binary Tree)

Problem statement: Given the root of a binary tree, produce lists of node values in Inorder
(L, Root, R), Preorder (Root, L, R), and Postorder (L, R, Root).

Logic:

• Preorder: visit node, then left subtree, then right subtree.

• Inorder: left subtree, node, right subtree.
• Postorder: left, right, node.
Recursive implementations are straightforward; iterative versions use a stack
(iterative inorder uses a pointer + stack).

Pseudocode (recursive):

preorder(node):
if node is None: return
visit(node)
preorder([Link])
preorder([Link])

inorder(node):
if node is None: return
inorder([Link])
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 visit(node)
inorder([Link])

postorder(node):
if node is None: return
postorder([Link])
postorder([Link])
visit(node)

Python code (both recursive and iterative inorder/preorder/postorder):

# Binary Tree Node

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

# Recursive traversals
def preorder_recursive(root, res):
if not root: return
[Link]([Link])
preorder_recursive([Link], res)
preorder_recursive([Link], res)

def inorder_recursive(root, res):

if not root: return
inorder_recursive([Link], res)
[Link]([Link])
inorder_recursive([Link], res)

def postorder_recursive(root, res):

if not root: return
postorder_recursive([Link], res)
postorder_recursive([Link], res)
[Link]([Link])

# Iterative traversals (preorder, inorder)

def preorder_iterative(root):
if not root: return []
stack = [root]
res = []
while stack:
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
return res

def inorder_iterative(root):
res, stack = [], []
curr = root
while curr or stack:
while curr:
[Link](curr)
curr = [Link]
curr = [Link]()
[Link]([Link])

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 curr = [Link]
return res

def postorder_iterative(root):
# Two-stack method
if not root: return []
s1, s2 = [root], []
while s1:
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
return s2[::-1]

# Example usage:
# root = TreeNode(1); [Link] = TreeNode(2); [Link] = TreeNode(3)
# r = []; preorder_recursive(root, r); print(r)

41. Level Order Traversal (Breadth-First Search, BFS)

Problem statement: Given the root of a binary tree, return level-wise node values (list of
lists), left-to-right per level. Also return flat level-order list if needed.

Logic: Use a queue. Process nodes level-by-level by iterating level_size = len(queue)

and collecting child nodes for the next level.

Pseudocode:

if root is None: return []

queue = [root]
while queue not empty:
level_size = len(queue)
level = []
for i in range(level_size):
node = [Link](0)
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)

Python code:

from collections import deque

def level_order(root):
if not root: return []
q = deque([root])
result = []
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = [Link]()
[Link]([Link])

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return result

def level_order_flat(root):
if not root: return []
q = deque([root])
res = []
while q:
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
return res

42. Height of a Binary Tree

Problem statement: Compute the height (maximum depth) of a binary tree. Height =
number of nodes in the longest root-to-leaf path (or you may define as edges; here we'll use
nodes).

Logic: Height = 1 + max(height(left), height(right)). Base case: None -> 0.

Pseudocode:

height(node):
if node is None: return 0
return 1 + max(height([Link]), height([Link]))

Python code:

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

43. Check if a Binary Tree is Balanced

Problem statement: A binary tree is height-balanced if for every node, the heights of left
and right subtrees differ by at most 1. Return True/False.

Logic: Naive approach computes heights repeatedly (O(n^2)). Optimal approach: postorder
traversal that returns height, or -1 sentinel if subtree is unbalanced. This yields O(n) time.

Pseudocode (optimal):

check(node):
if node is None: return 0
left_h = check([Link]); if left_h == -1: return -1
right_h = check([Link]); if right_h == -1: return -1
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 if abs(left_h - right_h) > 1: return -1
return 1 + max(left_h, right_h)

balanced = (check(root) != -1)

Python code:

def is_balanced(root):
def helper(node):
if not node: return 0
lh = helper([Link])
if lh == -1: return -1
rh = helper([Link])
if rh == -1: return -1
if abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return helper(root) != -1

44. Lowest Common Ancestor (LCA) of Two Nodes

(general binary tree)
Problem statement: Given root and two node values p and q (or nodes), find the lowest
common ancestor (LCA): the lowest node in the tree that has both p and q as descendants (a
node can be a descendant of itself).

Logic: Postorder recursion: if current node is p or q, return it. Otherwise, get left =
recurse(left), right = recurse(right).

• If left and right both non-null → current node is LCA.

• Else propagate whichever non-null child result exists.

Pseudocode:

LCA(node, p, q):
if node is None: return None
if node is p or node is q: return node
left = LCA([Link], p, q)
right = LCA([Link], p, q)
if left and right: return node
return left if left else right

Python code (values or node references):

def lowest_common_ancestor(root, p_val, q_val):

# returns the TreeNode or None
if not root: return None
if [Link] == p_val or [Link] == q_val:
return root
left = lowest_common_ancestor([Link], p_val, q_val)
right = lowest_common_ancestor([Link], p_val, q_val)
if left and right:
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 return root
return left if left else right

Notes: If you have references to node objects instead of values, compare nodes directly (if
root is p or root is q).

45. Check if a Binary Tree is a Binary Search Tree (BST)

Problem statement: Determine whether a binary tree is a valid BST: for every node, all
values in left subtree < [Link] < all values in right subtree (strict).

Logic: Use recursion with allowable (min_val, max_val) range that every node must fall
into. Initial range is (-inf, +inf).

Pseudocode:

is_bst(node, low, high):

if node is None: return True
if not (low < [Link] < high): return False
return is_bst([Link], low, [Link]) and is_bst([Link], [Link],
high)

Python code:

import math

def is_bst(root):
def helper(node, low, high):
if not node: return True
if not (low < [Link] < high): return False
return helper([Link], low, [Link]) and helper([Link],
[Link], high)
return helper(root, -[Link], [Link])

Alternative: Inorder traversal must produce strictly increasing sequence; you can check that
iteratively.

46. Diameter of a Binary Tree

Problem statement: The diameter (or width) is the number of nodes on the longest path
between any two nodes. (Some define as number of edges — adjust accordingly.)

Logic: For each node, longest path through it = left_height + right_height + 1 (if
counting nodes). We can compute heights bottom-up and keep a global maximum diameter.
O(n) time.

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Pseudocode:

max_diameter = 0
height(node):
if node is None: return 0
lh = height([Link])
rh = height([Link])
max_diameter = max(max_diameter, lh + rh + 1)
return 1 + max(lh, rh)

Python code:

def diameter_of_binary_tree(root):
# returns diameter in nodes; to get edges subtract 1
max_dia = 0
def height(node):
nonlocal max_dia
if not node: return 0
lh = height([Link])
rh = height([Link])
# path through node (count nodes)
max_dia = max(max_dia, lh + rh + 1)
return 1 + max(lh, rh)
height(root)
return max_dia # nodes; for edges return max_dia - 1 if desired

47. Count Leaf Nodes

Problem statement: Count the number of leaf nodes (nodes with no children) in a binary
tree.

Logic: Simple recursion: if node is leaf (not [Link] and not [Link]) count 1;
else sum counts in subtrees.

Pseudocode:

count_leaves(node):
if node is None: return 0
if [Link] is None and [Link] is None: return 1
return count_leaves([Link]) + count_leaves([Link])

Python code:

def count_leaf_nodes(root):
if not root: return 0
if not [Link] and not [Link]:
return 1
return count_leaf_nodes([Link]) + count_leaf_nodes([Link])

48. BFS & DFS in Graphs

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
Problem statement: Given an undirected/directed graph represented by adjacency lists,
implement BFS and DFS traversals (return visited order), handle disconnected graphs.

Logic:

• BFS: use queue, mark visited when enqueued.

• DFS (recursive): mark visited then recurse into neighbors.
• For disconnected graphs, loop through all vertices and start BFS/DFS from unvisited
ones.

Pseudocode (BFS):

BFS(graph):
visited = set()
for each vertex v:
if v not visited:
queue = [v]; [Link](v)
while queue:
node = [Link](0)
visit(node)
for nbr in graph[node]:
if nbr not visited:
[Link](nbr); [Link](nbr)

Python code (adjacency dict):

from collections import deque

def bfs_graph(adj):
# adj: dict {node: [neighbors]}
visited = set()
order = []
for start in adj:
if start in visited: continue
q = deque([start])
[Link](start)
while q:
node = [Link]()
[Link](node)
for nbr in [Link](node, []):
if nbr not in visited:
[Link](nbr)
[Link](nbr)
return order

def dfs_graph_recursive(adj):
visited = set()
order = []
def dfs(u):
[Link](u)
[Link](u)
for v in [Link](u, []):
if v not in visited:
dfs(v)
for node in adj:
if node not in visited:
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 dfs(node)
return order

def dfs_graph_iterative(adj, start):

visited = set()
stack = [start]
order = []
while stack:
node = [Link]()
if node in visited:
continue
[Link](node)
[Link](node)
# push neighbors in reverse if you want natural order
for nbr in reversed([Link](node, [])):
if nbr not in visited:
[Link](nbr)
return order

49. Detect Cycle in an Undirected Graph

Problem statement: Given an undirected graph (adjacency list), determine whether it
contains a cycle.

Logic: Use DFS with parent tracking (since undirected edges lead back to parent). While
visiting neighbors:

• If neighbor is not visited → DFS(neighbor, parent=node).

• If neighbor visited and neighbor != parent → found a cycle.

Alternatively, Union-Find (Disjoint Set) also works.

Pseudocode (DFS):

visited = set()
for each vertex v:
if v not visited:
if dfs(v, parent=-1): return True
return False

dfs(u, parent):
[Link](u)
for v in adj[u]:
if v not in visited:
if dfs(v, u): return True
elif v != parent:
return True
return False

Python code (DFS-based):

def has_cycle_undirected(adj):
visited = set()

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 def dfs(u, parent):
[Link](u)
for v in [Link](u, []):
if v not in visited:
if dfs(v, u):
return True
elif v != parent:
return True
return False

for node in adj:

if node not in visited:
if dfs(node, None):
return True
return False

# Union-Find version (optional)

def has_cycle_union_find(adj):
parent = {}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rx, ry = find(x), find(y)
if rx == ry: return False
parent[ry] = rx
return True

# initialize
for node in adj:
parent[node] = node
for u in adj:
for v in adj[u]:
if u < v: # ensure each undirected edge seen once (if nodes
comparable)
if not union(u, v):
return True
return False

Examples
# Build a sample tree:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
[Link] = TreeNode(2); [Link] = TreeNode(3)
[Link] = TreeNode(4); [Link] = TreeNode(5)

# Traversals:
print("Preorder recursive:", end=" "); r=[]; preorder_recursive(root, r);
print(r)
print("Inorder iterative:", inorder_iterative(root))
print("Level order:", level_order(root))
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
print("Height:", height(root))
print("Is balanced:", is_balanced(root))
print("LCA of 4 and 5:", lowest_common_ancestor(root, 4, 5).val)
print("Is BST:", is_bst(root))
print("Diameter (nodes):", diameter_of_binary_tree(root))
print("Leaf count:", count_leaf_nodes(root))

# Graph example:
adj = {1:[2,3], 2:[1,4], 3:[1], 4:[2]}
print("BFS order:", bfs_graph(adj))
print("DFS recursive:", dfs_graph_recursive(adj))
print("Has cycle:", has_cycle_undirected(adj))

50. Fibonacci using DP (Memoization & Tabulation)

Problem Statement: Compute nth Fibonacci number (F(n) = F(n-1) + F(n-2) with
F(0)=0, F(1)=1) efficiently.

Logic:

• Recursive naive: O(2^n). Too slow.

• Memoization (Top-Down): Store results in a dictionary/array to avoid
recomputation. O(n).
• Tabulation (Bottom-Up): Build array iteratively from base cases. O(n).
• Space-optimized: Use only two variables. O(1).

Python Code:

# Memoization
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

# Tabulation
def fib_tab(n):
if n <= 1: return n
dp = [0]*(n+1)
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

# Space optimized
def fib_opt(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a+b
return b

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
51. Longest Common Subsequence (LCS)
Problem Statement: Given two strings, find the length of the longest subsequence present in
both.

Logic:

• If s1[i] == s2[j]: LCS = 1 + LCS(i-1, j-1)

• Else: max(LCS(i-1, j), LCS(i, j-1)).
• DP Table of size (m+1)*(n+1).

Python Code:

def lcs(s1, s2):

m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[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]

# Example
# print(lcs("abcde", "ace")) # Output: 3

52. Longest Increasing Subsequence (LIS)

Problem Statement: Given an array, find the length of the longest increasing subsequence.

Logic:

• DP solution: dp[i] = 1 + max(dp[j]) for all j < i and arr[j] < arr[i].
O(n^2).
• Optimized solution: Use binary search with a sub list. O(n log n).

Python Code:

def lis_dp(nums):
n = len(nums)
dp = [1]*n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)

# Optimized (n log n)
import bisect
def lis_binary(nums):
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 sub = []
for x in nums:
i = bisect.bisect_left(sub, x)
if i == len(sub):
[Link](x)
else:
sub[i] = x
return len(sub)

53. Coin Change Problem

Problem Statement: Given coins of certain denominations and a target amount, find the
minimum number of coins to make the amount. If not possible, return -1.

Logic:

• DP array of size amount+1.

• Initialize dp[0]=0, others = inf.
• For each coin, update dp.

Python Code:

def coin_change(coins, amount):

dp = [float('inf')] * (amount+1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount+1):
dp[x] = min(dp[x], dp[x-coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

54. 0/1 Knapsack

Problem Statement: Given weights and values of n items, and capacity W, maximize value
without exceeding capacity. Each item may be included at most once.

Logic:

• Recursive relation:
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]) if wt[i-1]
<= w
• Else: dp[i-1][w].

Python Code:

def knapsack(weights, values, W):

n = len(values)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, W+1):
────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-
1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]

55. Minimum Cost Path in Grid

Problem Statement: Given an m x n grid with costs, find the minimum cost path from
(0,0) to (m-1,n-1) moving only right or down.

Logic:

• DP table where dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Python Code:

def min_cost_path(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]

56. Edit Distance Problem

Problem Statement: Given two strings s1, s2, find minimum operations (insert, delete,
replace) to convert s1 into s2.

Logic:

• If s1[i] == s2[j]: no operation.

• Else: 1 + min(insert, delete, replace).
• DP table size (m+1)*(n+1).

Python Code:

def edit_distance(s1, s2):

m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i # deletions

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer
 for j in range(n+1):
dp[0][j] = j # insertions
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[m][n]

────────────────────────────────────────────────────────────
Created by Nishant Thakur | 9354057409
Technical Trainer