Data Structures and Algorithms Tutorial 4 of 486
Foundations 17/41
Fundamentals
- Conditional Statements in DSA
- For Loop
- While Loop
- Functions
- Classes and Objects in DSA
- Order of Growth
- Asymptotic Analysis
- Big-O Notation
- Theta Notation
- Big-Omega Notation
- Time Complexity
- Space Complexity
- Input and Output
Maths, Pattern & Recursion
- Recursion
- Analysis of Recursion
- Even or Odd
- Sum of Natural Numbers
- Closest Number
- Sum of Consecutive Numbers
- Solid Rectangle
- Floyd's Triangle
- Hollow Rectangle
- Print 1 to N
- Print N to 1
- Factorial
- GCD
- Power
- Pyramid
- Hollow Diamond
- Count Digits
- Prime Testing
- Armstrong Number
- Trailing Zeros
- Prime Factors
- All Divisors
- Butterfly Pattern
- Palindrome Number
- Tower of Hanoi
- Non-Attacking Knights
- Josephus Problem
- Water Jug Problem
Core Data Structures 0/224
Array & String
- Array Basics
- String Basics
- Matrix Basics
- Is Sorted
- Multiply with Adjacent
- Reverse Array
- Reverse in Groups
- Rotate Array
- Generate All Subarrays
- Arrange by Sign
- Stock Buy/Sell - One Transaction
- Stock Buy/Sell - Multiple Transactions
- Leaders in Array
- Same Strings
- Palindrome String
- Toggle Case
- Remove Occurrences
- Remove Spaces
- Check Subsequence
- First Non-Repeating Character
- Pangram
- Majority Element
- Majority Element II
- Sorted Subsequence of 3
- Count Strictly Increasing Subarrays
- Next Permutation
- Kadane's Algorithm
- Sum of All Subarrays
- Maximum Product Subarray
- Implement atoi
- URLify
- Multiply Large Numbers
- Diagonal Traversal
- Magic Square
- Boundary Traversal
- Spiral Matrix
- Toeplitz Matrix
- Matrix Zig-Zag
- Transpose of Matrix
- Rotate Matrix by 90 Degrees
- Conway's Game of Life
- Queries in a Matrix
- Set Matrix Zeroes
- Maximum Circular Subarray Sum
- Next Smallest Palindrome
- Lexicographic Rank
- Text Justification
Linked List
- Linked List Basics
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Reverse Singly Linked List
- Reverse Doubly Linked List
- Reverse in Groups
- Reorder List
- Find Middle
- Remove Nth From End
- Check Palindrome
- Detect Cycle
- Intersection of Y-Shaped Lists
- Sort 0s 1s 2s
- Add Two Numbers
- Merge K Sorted Lists
- Browser History
- Twitter Design
- LRU Cache
- LFU Cache
- Flatten Linked List
- Clone Linked List With Random Pointer
Stack
- Stack Basics
- Reverse Stack
- Sort Stack
- Balanced Parentheses
- Postfix Evaluation
- Infix Evaluation
- Infix to Postfix
- Redundant Brackets
- Longest Valid Parentheses
- Stack Using Queues
- Two Stacks in an Array
- K Stacks in an Array
- Stack With getMin
- Remove K Digits
- Next Greater Element
- Stock Span Problem
- Previous Smaller Element
- Largest Rectangle in Histogram
- Trapping Rain Water
- Decode String
Queue
- Queue Basics
- Circular Queue
- Queue Using Stacks
- FIFO Page Replacement
- Reverse a Queue
- Reverse First K Elements
- Interleave Queue
- K Queues in an Array
- First Non-Repeating Character in a Stream
- Minimum Knight Steps
Deque
- Deque Basics
- Circular Array Implementation
- Lexicographically Largest Permutation
- Generate Bitonic Sequence
- Sliding Window Maximum
- Longest Subarray With Difference <= X
- Minimum Deques to Sort Array
Hashing
- Hashing Basics
- Linear Probing
- Separate Chaining
- Quadratic Probing
- Distinct in Array
- Is Subset
- Union of Arrays
- Intersection of Arrays
- Two Sum
- Fizz Buzz
- Pair Sums Divisible by K
- Roman to Integer
- Isomorphic Strings
- Count Frequencies
- Most Frequent Element
- Maximum Subsets
- Anagrams
- Longest Consecutive Subsequence
- Consecutive Subsequence
Heap
- Heap Basics
- Check for Heap
- Heap Sort
- Kth Largest
- K Largest Elements
- Height of Heap
- Connect N Ropes
- Nearly Sorted Array
- BST to Min Heap
- K Max Sum Combinations
- Median in a Stream
- Kth Largest in a Stream
- Merge K Sorted Arrays/Lists
- Range Covering K Sorted Lists
- Skyline Problem
- Sort by Frequency
Binary Tree
- Binary Tree Basics
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal
- Size of Tree
- Depth of Tree
- Maximum Width
- Check Balanced Tree
- Identical Trees
- Mirror Tree
- Sum Tree
- Left View
- Right View
- Path Sum
- Maximum Path Sum
- Serialize and Deserialize
- Iterative Inorder
- Iterative Preorder
- Iterative Postorder
- Morris Inorder
- Diameter of Tree
- Boundary Traversal
- Tree From Preorder and Inorder
- Connect Nodes at Same Level
- Invert Tree
- Flatten Tree
- Vertical Traversal
- Bottom View
- Top View
- Spiral Level Order
- Lowest Common Ancestor
- Distance K
- Subtree Check
Binary Search Tree
- BST Basics
- Search in BST
- Insert in BST
- Delete in BST
- Ceil in BST
- Floor in BST
- Predecessor and Successor
- Kth Smallest Element
- Two Sum in BST
- Sorted Array to BST
- Merge Two BSTs
- Validate BST
- Lowest Common Ancestor
- Recover BST
- Largest BST Subtree
Trie
- Implement Trie
- Longest Word With All Prefixes
- Count Distinct Substrings
- Maximum XOR of Two Numbers
- Maximum XOR Queries
- Pairs With XOR Less Than K
- Search Suggestions System
- Palindrome Pairs
Graph
- Graph Representation
- BFS Traversal
- DFS Traversal
- Flood Fill
- Number of Islands
- Connected Components in Undirected Graph
- Cycle in Undirected Graph
- Cycle in Directed Graph
- Bipartite Graph
- Rotten Oranges
- Topological Sort
- Course Schedule I
- Course Schedule II
- Alien Dictionary
- Dijkstra's Algorithm
- Floyd Warshall
- Bellman-Ford
- Minimum Cost Path
- Shortest Cycle in Undirected Graph
- Distance of Nearest 1
- Word Ladder
- Prim's Algorithm
- Disjoint Set Union
- Kruskal's Algorithm
- Detect Cycle Using DSU
- Number of Connected Components
Problem-Solving Patterns 0/99
Two-Pointer
- Two-Pointer Technique
- Two Sum in Sorted Array
- Smallest Subarray
- Unique Elements
- Sentence Palindrome
- Three Sum
- Celebrity Problem
- Closest Pair from Two Arrays
- Container With Most Water
- Common Elements in Three Arrays
- Reverse Words
- Four Sum
- Closest Triplet
- Count Triplets
Sliding Window
- Sliding Window Technique
- Maximum Sum Subarray of Size K
- Maximum XOR of K Size
- Distinct in Every Window
- MEX of Subarrays
- Minimum Swaps to Group All 1s
- First Negative in Every Window
- Chocolate Distribution
- Maximize Ones
- Equal Substring With Cost <= K
- Fruit Into Baskets
- Subarray With Given Sum
- Smallest Subarray With Sum Greater Than X
- Minimum Window Subsequence
- Minimum Window Substring
- Subarrays With K Odds
- Subarrays Less Than K
- Longest Substring With Distinct Characters
- Longest Substring With K Unique Characters
- Count Anagrams
Prefix Sum
- Prefix Sum Basics
- Prefix Sum Array
- 2D Prefix Sum
- Range Queries
- Equilibrium Index
- Product of Array Except Self
- Difference Array
- 2D Difference Array
- Subarray With Zero Sum
- Largest Subarray With Zero Sum
- Largest Subarray With Equal 0s and 1s
- Longest Subarray With Sum K
- Count Subarrays With Sum K
- Count Subarrays With Given XOR
Bit Manipulation
- Bit Manipulation Basics
- Swap Without Third Variable
- Kth Set Bit
- Only Set Bit
- Power of Two
- Sort by Set Bits
- Power of Four
- Binary Palindrome
- Rotate Bits
- Swap Odd and Even Bits
- Count Set Bits
- Count Total Set Bits
- Maximum Consecutive 1s
- Missing Number
- One Odd Occurring
- Two Odd Occurring
- Missing and Repeating
- Unique Numbers II
- Gray Codes
- Hamming Distance
- Sum of Pair XORs
- Sum of Subset XORs
- Subarray XORs
- Subsets
- Subsequences
Backtracking
- Backtracking Basics
- Permutations
- Rat in a Maze
- Word Search
- N-Queen Problem
- Sudoku Solver
- Word Break
- Knight's Tour
- Palindromic Partitions
- M-Coloring
Greedy
- Greedy Algorithm Basics
- Fractional Knapsack
- Assign Cookies
- Smallest Subset With Greater Sum
- Minimum Notes With Given Sum
- Activity Selection
- Huffman Coding
- Jump Game
- Job Sequencing
- Non-Overlapping Intervals
- Gas Station
- Stable Marriage
- Minimize Maximum Height Difference
- No Two Adjacent Same
- Minimize Cash Flow
- Min Time to Finish Jobs With Constraints
Core Algorithms 0/122
Searching
- Searching Basics
- Largest Element
- Second Largest
- Local Min and Max
- Search Insert Position
- Lower Bound
- Upper Bound
- Single Element in Sorted Array
- Missing Natural Number
- Count Occurrences
- Search in 2D Matrix
- Search in Sorted and Rotated Array
- Search in Sorted and Rotated Array II
- K Closest Elements
- Search in Almost Sorted Array
- Peak Element
- Peak Element in 2D
- Range Based Counts
- Kth Missing Positive
- Search in Row-Column Sorted Matrix
- Square Root
- Nth Root
- Check Power
- Book Allocation
- Koko Eating Bananas
- Aggressive Cows
- Median in Row Sorted Matrix
- Kth Smallest in Row and Column Sorted Matrix
- M Bouquets
- Kth in Multiplication Table
- Median of Two Sorted Arrays
- Kth Element of Two Sorted Arrays
Sorting
- Sorting Basics
- Wave Form
- Sort by Length
- Minimum Difference Pair
- Merge Overlapping Intervals
- Form Largest Number
- Meeting Rooms
- Insert and Merge Intervals
- Minimize Moves
- Quick Sort
- Sort Binary Array
- Move Zeroes to End
- Sort Ternary Array
- Merge Sort
- Union of Two Sorted Arrays
- Intersection of Two Sorted Arrays
- Merge Without Extra Space
- Minimum Platforms
- Inversion Count
- Cycle Sort
- Minimum Missing Positive
- Minimum Swaps to Sort
Dynamic Programming
- Dynamic Programming Basics
- Climbing Stairs
- Count Without Consecutive 1s
- Frog Jump
- House Robber
- Maximum Segments
- Coin Change
- Decode Ways
- Word Break
- Unique Paths
- Minimum Cost Path
- Longest Common Subsequence
- Edit Distance
- Distinct Subsequences
- Largest Square Submatrix of 1s
- Partition Equal Subset Sum
- Subset Sum
- Count Subsets With Given Sum
- Target Sum
- 0/1 Knapsack
- Coin Change II
- Rod Cutting
- Unique Paths in a Grid
- Maximum Path Sum in Matrix
- Longest Increasing Path
- Longest Common Substring
- Shortest Common Supersequence
- Interleaving String
- Wildcard Matching
- Longest Palindromic Substring
- Buy/Sell With Cooldown
- Buy/Sell With At Most Two Transactions
- Buy/Sell With K Transactions
- Buy/Sell With Transaction Fee
- Longest Increasing Subsequence
- Number of LIS
- Longest Bitonic Subsequence
- Longest String Chain
- Matrix Chain Multiplication
- Minimum Cost to Cut a Stick
- Palindrome Partitioning
- Boolean Parenthesization
- Partition Array for Maximum Sum
- Egg Dropping
String Matching
- Substring Search
- Rabin-Karp
- KMP Algorithm
- Z Algorithm
- Longest Prefix Suffix
- Manacher's Algorithm
- Longest Palindromic Substring
- Palindrome Substring Queries
- Minimum Repeats for Substring
Number Theory
- nCr
- Euler's Totient
- Sieve of Eratosthenes
- Pascal's Triangle
- Modular Exponentiation
- Segmented Sieve
Range Query
- Segment Tree
- Min-Max Range Queries
- Range LCM Queries
- Range XOR Queries
- Lazy Propagation
- Flipping Sign
- Segment Tree on N-ary Rooted Tree
- Fenwick Tree
- Sum and Update Queries on 3D Matrix
Functions
Learn how functions help organize DSA algorithms into reusable units using parameters, return values, and clear inputs and outputs.
On this page
- 1. Why Functions Are Important in DSA
- 2. Basic Function Structure
- 3. Parameters
- 4. Return Value
- 5. Functions for DSA Algorithms
- 6. Example: Linear Search Function
- Complexity
- 7. Function for Finding Maximum
- 8. Function for Counting Elements
- 9. Functions and Problem Decomposition
- 10. Functions and Recursion
- 11. Functions and Divide and Conquer
- 12. Input and Output of a Function
- 13. Functions and Complexity
- 14. Functions Calling Other Functions
- 15. Functions and Testing
- 16. Common Mistakes
- Forgetting the return value
- Incorrect parameters
- Mixing responsibilities
- Ignoring edge cases
- Search
- Maximum
- Minimum
- Count
- Transformation
- Recursive
Functions in DSA
A function is a reusable block of logic that performs a specific task.
In DSA, functions help break a problem into smaller, manageable parts.
Instead of writing the same logic repeatedly, we can place it inside a function and call it whenever required.
For example:
findMaximum(array)
can represent the algorithm for finding the maximum element.
A function generally has:
Input → Function → Output
1. Why Functions Are Important in DSA
Functions help make algorithms:
- Easier to understand
- Easier to test
- Reusable
- Easier to debug
- Easier to divide into smaller problems
For example, instead of putting all logic into one large algorithm:
main algorithm
find maximum
find minimum
search element
calculate sum
we can separate the logic:
findMaximum()
findMinimum()
search()
calculateSum()
Each function has a clear responsibility.
2. Basic Function Structure
A function can be represented as:
function name(input):
perform operation
return result
For example:
function add(a, b):
return a + b
Calling:
add(5, 3)
returns:
8
The important DSA concept is:
Input → Processing → Result
3. Parameters
Parameters are the inputs provided to a function.
Example:
function findMaximum(arr):
...
Here:
arr
is a parameter.
Another example:
function search(arr, target):
...
The function receives two inputs:
arr
target
Parameters allow the same algorithm to work with different input values.
4. Return Value
A function can return the result of an operation.
Example:
function findMaximum(arr):
max = arr[0]
for each element in arr:
if element > max:
max = element
return max
For:
[4, 9, 2, 15, 7]
the function returns:
15
The return statement sends the result back to the caller.
5. Functions for DSA Algorithms
Functions are commonly used to represent individual algorithms.
For example:
linearSearch(arr, target)
binarySearch(arr, target)
findMaximum(arr)
findMinimum(arr)
reverseArray(arr)
Each function can represent one specific operation.
This makes it easier to understand the overall solution.
6. Example: Linear Search Function
A linear search can be written as a function:
function linearSearch(arr, target):
for i = 0 to n - 1:
if arr[i] == target:
return i
return -1
Example:
arr = [10, 20, 30, 40]
target = 30
The function returns:
2
because 30 is at index 2.
Complexity
Linear search takes:
Time: O(n)
Space: O(1)
The function itself does not change the algorithm's complexity.
7. Function for Finding Maximum
function findMaximum(arr):
max = arr[0]
for i = 1 to n - 1:
if arr[i] > max:
max = arr[i]
return max
For:
[5, 12, 3, 20, 8]
the result is:
20
Complexity:
Time: O(n)
Space: O(1)
8. Function for Counting Elements
A function can also return a calculated value.
function countEven(arr):
count = 0
for each element in arr:
if element % 2 == 0:
count++
return count
For:
[2, 5, 8, 9, 10]
the result is:
3
The function encapsulates the complete logic for the operation.
9. Functions and Problem Decomposition
Functions become particularly useful when a DSA problem contains multiple smaller tasks.
Suppose a problem requires:
- Finding the maximum.
- Finding the minimum.
- Calculating the difference.
Instead of putting everything together, we can use:
max = findMaximum(arr)
min = findMinimum(arr)
difference = max - min
This is called problem decomposition.
A large problem is divided into smaller functions.
10. Functions and Recursion
Functions are especially important for recursive algorithms.
A recursive function calls itself.
Example:
function factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
The function calls itself with a smaller input:
factorial(5)
↓
factorial(4)
↓
factorial(3)
↓
factorial(2)
↓
factorial(1)
↓
factorial(0)
The condition:
n == 0
is the base case that stops the recursion.
Recursive functions are widely used in:
- Trees
- Graphs
- Divide and Conquer
- Backtracking
- Dynamic Programming
11. Functions and Divide and Conquer
Functions are useful for algorithms that divide a problem into smaller problems.
For example, Merge Sort can conceptually be represented as:
mergeSort(array)
↓
divide array
↓
mergeSort(left)
mergeSort(right)
↓
merge results
The function calls itself on smaller portions of the input.
This makes functions an important part of recursive and divide-and-conquer algorithms.
12. Input and Output of a Function
A useful way to understand a DSA function is:
Input
↓
Function
↓
Output
For example:
findMaximum([4, 8, 2, 10])
Input:
[4, 8, 2, 10]
Output:
10
Another example:
linearSearch([5, 8, 12], 8)
Output:
1
Thinking in terms of inputs and outputs helps when designing algorithms.
13. Functions and Complexity
Creating a function does not automatically change the time or space complexity of an algorithm.
For example:
function findMaximum(arr):
for each element:
...
If the function processes n elements once:
Time Complexity = O(n)
If it uses constant additional variables:
Space Complexity = O(1)
The complexity depends on the operations performed by the function.
14. Functions Calling Other Functions
A function can call another function.
For example:
function solve(arr):
max = findMaximum(arr)
min = findMinimum(arr)
return max - min
Here:
solve()
uses:
findMaximum()
findMinimum()
This allows complex algorithms to be built from smaller reusable components.
15. Functions and Testing
Functions make DSA solutions easier to test.
For example:
findMaximum([1, 5, 3])
Expected:
5
Test another input:
findMaximum([-5, -2, -10])
Expected:
-2
And:
findMaximum([7])
Expected:
7
Testing individual functions makes it easier to identify errors in an algorithm.
16. Common Mistakes
Forgetting the return value
If a function is expected to produce an answer, make sure the result is returned.
function findMaximum(arr):
...
return max
Incorrect parameters
Make sure the function receives all information required by the algorithm.
For example:
search(arr, target)
requires both the array and the target.
Mixing responsibilities
A function should ideally have a clear purpose.
Instead of one function doing many unrelated operations, separate the logic when appropriate.
Ignoring edge cases
Functions should be considered for inputs such as:
empty array
single element
duplicate values
negative values
large input
The correct handling depends on the problem requirements.
17. DSA Function Patterns
Search
search(arr, target)
Returns the position or indicates whether the target exists.
Maximum
findMaximum(arr)
Returns the largest element.
Minimum
findMinimum(arr)
Returns the smallest element.
Count
countElements(arr, condition)
Returns the number of elements satisfying a condition.
Transformation
reverseArray(arr)
Processes the input and produces a result.
Recursive
solve(problem)
Calls itself on smaller inputs.
These patterns appear repeatedly throughout DSA.
18. Function as an Algorithmic Unit
A useful way to think about a function in DSA is as an algorithmic unit.
For example:
solve()
|
+-- findMaximum()
|
+-- findMinimum()
|
+-- search()
|
+-- calculateResult()
Each function handles a specific part of the solution.
This makes large problems easier to reason about.
Key Takeaways
- A function is a reusable unit of logic.
- Functions help divide DSA problems into smaller tasks.
- Parameters provide input to a function.
- Return values provide the result.
- Functions can represent individual algorithms.
- Functions are especially important in recursion and divide-and-conquer algorithms.
- Breaking a problem into functions improves readability and testing.
- A function does not automatically change the complexity of an algorithm.
- Always consider edge cases when designing a function.
- Good DSA functions generally have a clear and focused responsibility.
Practice Questions
- Write a function to find the maximum element in an array.
- Write a function to find the minimum element.
- Write a function for linear search.
- Write a function to count even numbers.
- Write a function to calculate the sum of an array.
- Write a function to reverse an array.
- Write a function to check whether an array is sorted.
- Write a recursive function for factorial.
- Write a recursive function to calculate Fibonacci numbers.
- Identify the time and space complexity of a given function.
What's Next?
Functions provide a way to organize algorithms into reusable units.
The next important DSA concept is Arrays, where these functions and iteration techniques are applied to one of the most fundamental data structures.