Scribd
Upload
6 views3 pages

Recursion and Problem Solving Techniques

The document discusses two approaches to solving problems: a brute force method and an optimized solution using data structures like hashmaps. The brute force method, while simple, has a time complexity of O(n²), whereas the optimized approach reduces it to O(n). It also emphasizes a problem-solving mindset by breaking down problems into smaller steps and considering incremental optimizations.

Uploaded by

Ashish Deshmukh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views3 pages

Recursion and Problem Solving Techniques

The document discusses two approaches to solving problems: a brute force method and an optimized solution using data structures like hashmaps. The brute force method, while simple, has a time complexity of O(n²), whereas the optimized approach reduces it to O(n). It also emphasizes a problem-solving mindset by breaking down problems into smaller steps and considering incremental optimizations.

Uploaded by

Ashish Deshmukh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Recursion Pre read

1. Brute Force Approach

The brute force method involves checking all possible solutions and selecting the best one.

Although it’s simple, brute force may be inefficient for large datasets.

Example: Finding a pair of numbers in an array whose sum equals a target value.

Pseudocode:

FUNCTION FindPair(arr, target):

SET n TO LENGTH OF arr

FOR i FROM 0 TO n - 1:

FOR j FROM i + 1 TO n - 1:

IF arr[i] + arr[j] EQUALS target THEN

RETURN (arr[i], arr[j])

RETURN None

This brute-force solution has a time complexity of O(n²), which may not be optimal for larger

arrays.

2. Optimizing Code with Data Structures

By using efficient data structures, like hashmaps, we can reduce the time complexity of

lookups and improve performance.

Optimized Solution Using Hashmap:

Pseudocode:
FUNCTION FindPairOptimized(arr, target):

CREATE empty hashmap

FOR EACH num IN arr:

SET complement TO target - num

IF complement IS IN hashmap THEN

RETURN (complement, num)

ADD num TO hashmap

RETURN None

With this approach, the time complexity reduces to O(n) due to the use of hashmap for fast

lookups.

3. Problem Solving Mindset:

Break the problem into smaller steps. Identify inputs, outputs, and subproblems to approach

it incrementally.

Example: Reverse a Linked List

1. Traverse through the list.


2. Track the previous node.
3. Reverse pointers at each node.

4. Think Incrementally

Start with a straightforward solution (like brute force) and then apply incremental

optimizations using:

● Dynamic Programming
● Greedy Algorithms
● Efficient Data Structures

Note: This post serves as pre-reads for the session titled “Problem Solving” in our DSA and

System Design course.

You might also like