FACULTY GUIDE

DSA with Python - 1

 DSA WITH PYTHON
TIME AND SPACE COMPLEXITY, LIST, TUPLE, SET, DICTIONARY, STRING

1. WHAT IS DSA?

DSA = Data Structures + Algorithms

Data Structure is a way to store and organize data efficiently.

Algorithm is a step-by-step procedure to solve a problem.

WHY DSA IS IMPORTANT?

• Efficient programs
• Faster execution

2. WHAT IS DATA STRUCTURE?

A Data Structure is a method of storing data in memory so that operations like search, insert,
delete, update can be done efficiently.

Examples:

Real Life Data Structure

Library Array/List

Phone Contacts Dictionary

Unique roll numbers Set

Types of Data Structures:

1. Primitive
o int, float, char, bool
2. Non-Primitive
o Linear: Array, List, Tuple, Stack, Queue
o Non-Linear: Tree, Graph

3. WHAT IS ALGORITHM?
An Algorithm is a finite sequence of well-defined instructions to solve a problem.

Example:

Problem: Find sum of 2 numbers

Algorithm:

© 2025|Simplifying Skills | All rights reserved

 • Take two numbers
• Add them
• Print result

4. TIME COMPLEXITY (TC)

What is Time Complexity?

Time Complexity tells how much time an algorithm takes as input size increases.

It does NOT measure seconds

It measures number of operations

5. SPACE COMPLEXITY (SC)

What is Space Complexity?

Space Complexity tells how much extra memory an algorithm uses.

Includes:

• Input space

• Extra variables

• Data structures created

6. HOW TO CALCULATE TIME & SPACE COMPLEXITY

Steps:

I. Count loops
II. Ignore constants
III. Focus on input size n
IV. Consider extra memory usage

7. ASYMPTOTIC NOTATIONS (VERY IMPORTANT)

1. Big-O (Worst Case)

2. Omega Ω (Best Case)

3. Theta Θ (Average Case)

8. BIG-O NOTATIONS WITH EXAMPLES

O(1) – Constant Time

def get_first(arr):

© 2025|Simplifying Skills | All rights reserved

 return arr[0]

TC: O(1)
SC: O(1)

O(n) – Linear Time

def print_elements(arr):

for i in arr:

print(i)

TC: O(n)
SC: O(1)

O(n²) – Quadratic Time

def pair_sum(arr):

for i in arr:

for j in arr:

print(i, j)

TC: O(n²)
SC: O(1)

O(log n)

def binary_search(arr, key):

low, high = 0, len(arr)-1

while low <= high:

mid = (low + high)//2

TC: O(log n)
SC: O(1)

9. BEST, WORST & AVERAGE CASE

Example: Linear Search

def linear_search(arr, key):

for i in arr:

if i == key:

© 2025|Simplifying Skills | All rights reserved

 return True

Case TC

Best O(1)

Worst O(n)

Average O(n)

10. LIST IN DSA (PYTHON)

What is List?

• Ordered

• Mutable

• Allows duplicates

Types of Lists:

• Homogeneous

• Heterogeneous

• Nested List

LIST PROGRAMS (WITH TC & SC)

1. Find length

lst = [1,2,3]

print(len(lst))

TC: O(1) | SC: O(1)

2. Traverse list

for i in lst:

print(i)

TC: O(n) | SC: O(1)

3. Reverse list

[Link]()

TC: O(n) | SC: O(1)

© 2025|Simplifying Skills | All rights reserved

4. Find max

max(lst)

TC: O(n) | SC: O(1)

5. Append element

[Link](10)

TC: O(1) | SC: O(1)

6. Insert element

[Link](1, 100)

TC: O(n) | SC: O(1)

. Remove element

[Link](2)

TC: O(n) | SC: O(1)

8. Sort list

[Link]()

TC: O(n log n) | SC: O(1)

9. Copy list

new_lst = [Link]()

TC: O(n) | SC: O(n)

10. Count frequency

[Link](2)

TC: O(n) | SC: O(1)

11. TUPLE IN DSA

What is Tuple?

• Ordered

• Immutable

• Faster than list

© 2025|Simplifying Skills | All rights reserved

Types:

• Single element tuple

• Nested tuple

TUPLE PROGRAMS

1. Access element

t = (1,2,3)

print(t[0])

TC: O(1) | SC: O(1)

2. Traverse tuple

for i in t:

print(i)

TC: O(n) | SC: O(1)

3. Tuple length

len(t)

TC: O(1) | SC: O(1)

4. Convert list to tuple

tuple(lst)

TC: O(n) | SC: O(n)

5. Count element

[Link](2)

TC: O(n) | SC: O(1)

6. Index search

[Link](3)

TC: O(n) | SC: O(1)

. Nested tuple access

t = ((1,2),(3,4))

print(t[1][0])

© 2025|Simplifying Skills | All rights reserved

TC: O(1) | SC: O(1)

. Tuple unpacking

a,b,c = t

TC: O(n) | SC: O(1)

9. Membership check

2 in t

TC: O(n) | SC: O(1)

10. Concatenation

t1 + t2

TC: O(n) | SC: O(n)

12. SET IN DSA

What is Set?

• Unordered

• Unique elements

• Uses Hashing

Types:

• Set

• Frozen Set

SET PROGRAMS

1. Add element

[Link](5)

TC: O(1) | SC: O(1)

2. Remove element

[Link](2)

TC: O(1) | SC: O(1)

3. Union

s1 | s2

© 2025|Simplifying Skills | All rights reserved

TC: O(n) | SC: O(n)

4. Intersection

s1 & s2

TC: O(n) | SC: O(n)

5. Difference

s1 - s2

TC: O(n) | SC: O(n)

6. Membership check

5 in s

TC: O(1) | SC: O(1)

7. Length

len(s)

TC: O(1) | SC: O(1)

8. Clear set

[Link]()

TC: O(1) | SC: O(1)

9. Convert list to set

set(lst)

TC: O(n) | SC: O(n)

10. Iterate set

for i in s:

print(i)

TC: O(n) | SC: O(1)

13. DICTIONARY IN DSA

Why Dictionary?

• Fast lookup

• Key-Value pair

© 2025|Simplifying Skills | All rights reserved

 • Uses Hash Table

DICTIONARY PROGRAMS

1. Create dict

d = {"a":1, "b":2}

TC: O(1) | SC: O(n)

2. Access value

d["a"]

TC: O(1) | SC: O(1)

3. Add key

d["c"] = 3

TC: O(1) | SC: O(1)

4. Delete key

del d["a"]

TC: O(1) | SC: O(1)

5. Traverse

for k,v in [Link]():

print(k,v)

TC: O(n) | SC: O(1)

6. Keys

[Link]()

TC: O(1) | SC: O(1)

© 2025|Simplifying Skills | All rights reserved

7. Values

[Link]()

TC: O(1) | SC: O(1)

8. Check key

"a" in d

TC: O(1) | SC: O(1)

9. Copy dict

d2 = [Link]()

TC: O(n) | SC: O(n)

10. Nested dictionary

d = {"x":{"y":10}}

TC: O(1) | SC: O(n)

14. STRING IN DSA (PYTHON)

• Strings are immutable

• Stored as array of characters

s = "Python"

Operations:

• Traversal → O(n)

• Slicing → O(n)

• Concatenation → O(n)

15. ARRAY IN DSA (PYTHON)

Python uses List as Dynamic Array

Example:

arr = [10,20,30,40]

© 2025|Simplifying Skills | All rights reserved

Operations:

Operation TC
Access O(1)
Insert O(n)
Delete O(n)
Search O(n)

© 2025|Simplifying Skills | All rights reserved

🔹 1. LIST

1. Rotate list to the right by k positions

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

2. Minimum swaps required to sort list

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

3. Remove consecutive duplicates

Input: lst = [1,1,2,2,2,3,1,1]

4. Find all pairs with given sum

Input: lst = [2,4,3,5,7,8,9], target = 7

5. Longest increasing contiguous sublist

Input: lst = [1,2,2,3,4,1,2,3,4,5]

6. Alternate positive and negative numbers

Input: lst = [1,-2,3,-4,-1,4]

7. Find majority element (> n/2)

Input: lst = [2,2,1,2,3,2,2]

8. Flatten nested list of any depth

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

9. Intersection of two lists (no set)

Input: lst1 = [1,2,3,4], lst2 = [3,4,5,6]

10. Split list into chunks of size k

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

11. Kth largest element without sorting

Input: lst = [7,10,4,3,20,15], k = 3

12. Move all zeroes to end (order preserved)

Input: lst = [0,1,0,3,12]

13. Divide list into two parts with equal sum

Input: lst = [1,5,11,5]

14. Generate all subarrays

Input: lst = [1,2,3]

15. Maximum product subarray

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

© 2025|Simplifying Skills | All rights reserved

🔹 2. STRING

1. Check if strings are isomorphic

Input: s1 = "egg", s2 = "add"

2. First non-repeating character

Input: s = "swiss"

3. Longest palindromic substring

Input: s = "babad"

4. Valid shuffle of two strings

Input: s1 = "abc", s2 = "def", s3 = "adbcef"

5. Find all anagrams of pattern

Input: s = "cbaebabacd", pattern = "abc"

6. Reverse words without split()

Input: s = "Python is powerful"

7. String compression
Input: s = "aaabbcccc"

8. Minimum window substring

Input: s = "ADOBECODEBANC", t = "ABC"

9. Pattern matching (bijective)

Input: pattern = "abba", s = "dog cat cat dog"

10. Implement atoi (string → int)

Input: s = "-12345"

11. Longest substring without repeating chars

Input: s = "abcabcbb"

12. Substrings with equal vowels & consonants

Input: s = "aba"

13. Rearrange string to palindrome

Input: s = "aabb"

14. Remove duplicate characters

Input: s = "programming"

15. All permutations of string

Input: s = "abc"

© 2025|Simplifying Skills | All rights reserved

🔹 3. ARRAY

1. Maximum sum subarray (Kadane)

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

2. Merge two sorted arrays in-place

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

3. Missing and repeating number

Input: arr = [4,3,6,2,1,1]

4. Find leaders
Input: arr = [16,17,4,3,5,2]

5. Equilibrium index
Input: arr = [-7,1,5,2,-4,3,0]

6. First repeating element

Input: arr = [10,5,3,4,3,5,6]

7. Largest subarray with zero sum

Input: arr = [15,-2,2,-8,1,7,10,23]

8. Sort 0s,1s,2s
Input: arr = [0,1,2,1,0,2,1]

9. Minimum jumps to reach end

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

10. Next greater element

Input: arr = [4,5,2,25]

11. Count inversions

Input: arr = [8,4,2,1]

12. Maximum circular subarray sum

Input: arr = [8,-4,3,-5,4]

13. Check rotated sorted array

Input: arr = [3,4,5,1,2]

14. Triplets with sum zero

Input: arr = [-1,0,1,2,-1,-4]

15. Rearrange arr[i] = i

Input: arr = [-1,-1,6,1,9,3,2,-1,4,-1]

© 2025|Simplifying Skills | All rights reserved

🔹 4. TUPLE

1. Sum values of same keys

Input: [(1,2),(3,4),(1,5)]

2. Tuple with maximum product

Input: [(1,2),(3,4),(2,5)]

3. Remove duplicate tuples

Input: [(1,2),(3,4),(1,2),(5,6)]

4. Sort by second element

Input: [(1,3),(4,1),(2,2)]

5. Flatten nested tuple

Input: (1,(2,(3,4)),5)

6. Count tuples with same first element

Input: [(1,2),(1,3),(2,4)]

7. Replace last value

Input: [(1,2),(3,4)], new_val = 99

8. Common elements between tuples

Input: (1,2,3), (2,3,4)

9. Tuple digits to number

Input: (1,2,3,4)

10. Palindrome tuple

Input: (1,2,3,2,1)

11. Tuples with distinct elements

Input: [(1,2),(2,2),(3,4)]

12. Tuples with sum > k

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

13. Rotate tuple

Input: (1,2,3,4,5), n = 2

14. Tuple to string

Input: ('p','y','t','h','o','n')

15. Frequency in tuple

Input: (1,2,2,3,3,3)

© 2025|Simplifying Skills | All rights reserved

🔹 5. DICTIONARY

1. Sort by values
Input: {'a':3,'b':1,'c':2}

2. Merge without overwriting

Input: d1={'a':1,'b':2}, d2={'b':3,'c':4}

3. Key with maximum value

Input: {'x':10,'y':25,'z':5}

4. Reverse dictionary
Input: {'a':1,'b':2,'c':3}

5. Common keys
Input: {'a':1,'b':2}, {'b':3,'c':4}

6. Group by frequency
Input: lst = [1,1,2,3,3,3]

7. List to frequency dict

Input: [10,20,10,30,20,10]

8. Anagram dictionaries
Input: {'a':2,'b':1}, {'b':1,'a':2}

9. Two lists to dict

Input: keys=[1,2,3], values=['a','b','c']

10. Top k frequent

Input: lst=[1,1,1,2,2,3], k=2

11. Remove None values

Input: {'a':1,'b':None,'c':3}

12. Flatten nested dictionary

Input: {'a':{'b':1,'c':2}}

13. Sort by key length

Input: {'one':1,'three':3,'two':2}

14. Dict to tuple list

Input: {'a':1,'b':2}

15. Character count

Input: "interview"

© 2025|Simplifying Skills | All rights reserved

🔹 6. SET

1. Union without built-in

Input: {1,2,3}, {3,4,5}

2. Common in three sets

Input: {1,2,3}, {2,3,4}, {3,4,5}

3. Remove duplicates from list

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

4. Check disjoint sets

Input: {1,2}, {3,4}

5. Symmetric difference manually

Input: {1,2,3}, {3,4,5}

6. Subset check
Input: {1,2}, {1,2,3,4}

7. Unique pairs with sum k

Input: [1,5,7,-1,5], k=6

8. Remove common elements

Input: {1,2,3}, {2,3,4}

9. Find duplicates in list

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

10. Set to sorted list

Input: {5,3,1,4,2}

11. Count distinct elements

Input: [1,2,2,3,4,4,5]

12. All unique elements check

Input: [1,2,3,4]

13. Missing numbers

Input: [1,2,4,6], n=6

14. Set equality without ==

Input: {1,2,3}, {3,2,1}

15. Custom set operations using list

Input: list1=[1,2,3], list2=[3,4,5]

© 2025|Simplifying Skills | All rights reserved