A folder to track my DSA progress.
Complexity of Python Operations
https://wiki.python.org/moin/TimeComplexity
import sys input = sys.stdin.readline
def inp(): return(int(input())) def inlt(): return(list(map(int,input().split()))) def insr(): s = input() return(list(s[:len(s) - 1])) def invr(): return(map(int,input().split()))
It comprises of 4 functions :-
-
inp — For taking integer inputs.
-
inlt — For taking List inputs.
-
insr — For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
-
invr — For taking space seperated integer variable inputs.
The input = sys.stdin.readline is actually for Faster Inputs, because line reading through System STDIN (Standard Input) is faster in Python.
https://neetcode.io/courses/lessons/python-for-coding-interviews
If input array is sorted then
- Binary search
- Two pointers
If asked for all permutations/subsets then
- Backtracking
If given a tree then
- DFS
- BFS
If given a graph then
- DFS
- BFS
If given a linked list then
- Two pointers
If recursion is banned then
- Stack
If must solve in-place then
- Swap corresponding values
- Store one or more different values in the same pointer
If asked for maximum/minimum subarray/subset/options then
- Dynamic programming
If asked for top/least K items then
- Heap
- QuickSelect
If asked for common strings then
- Map
- Trie
Else
- Map/Set for O(1) time & O(n) space
- Sort input for O(nlogn) time and O(1) space
// Written by Rahul :)