Coding Block's Algorithm++ course

Important algorithms topic wise:

Arrays

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	generating subarrays	@subarrays	Two indices to generating all pairs	13th Dec
2	subarray sum	@Kadane's Algo	Take the cummulative sum. If sum is negative change it to 0	13th Dec
3	String Palindrome	@Palindrome	Two indices. One from start,other from end. Loop till i<j	14th Dec
4	Consecutive dupl chars in a string	@conschars	Two consecutive indices from the start	14th Dec
5	2d matrix spiral print	@spiralPrint	4 indices in 4 corners of the matrix	14th Dec
6	2d matrix wave print	@waveprint	If column odd traverse from bottom to top, if column is even traverse from top to botton	14th Dec
7	Rotate 2d matrix anticlockwise	@rotateArray	Reverse rows/columns then transpose	14th Dec
8	Staircase search	@staircase	start top right, if curr>k j-=1 else i+=1	14th Dec
9	Sorting string based on token	@sortingStrings	tokenization,custom comparators,pairs	15th Dec

Sorting and Searching

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Bubble Sort	@bubleSort	placing the largest element in the last place of the unsorted array in subsequent iterations	17th Dec
2	Selection Sort	@selectionSort	place the smallest element in the first index of the unsorted array in subsequents iterations	17th Dec
3	Insertion Sort	@insertionSort	sorting left side of the array	17th Dec
4	Counting Sort	@countingsort	storing a cummulative freq array.	17th Dec
5	Wave Sort	@wavesort	making each even index as local minima	17th Dec
6	Binary Search	@binarysearch	comparing the key with middle element and accordingly changing the mid-point	17th Dec
7	lower/upper bound of an element	@1st/last occurence	increasing/reducing the start/end for first/last occ respectively	17th Dec
8	Sqrt of a no. with x precision	@sqrt	for int part apply binary search on 0 to n, for decimal inc iteratively and check sqaure of ans	18th Dec
9	Searching rotated sorted arr	@srs	searching in 3 parts of array(visualize the graph of arr)	18th Dec
10	Book Allocation Prob	@allocation	binary search on range of total pages	18th Dec
11	Partioning	@partioning	two indices from start and replacing arr[i++] and arr[j++] if i++ is less	20th Dec

Bit Masking

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Generating all subsequences of a string	@subsequences	generating all pow(2,n-1) masks and applying & b/w string and mask	19th Dec
2	Index of lucky number	@lucky no	permutation and combination	19th Dec

Number Theory

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Prime no. or not	@isprime	Prime Seive	20th Dec
2	SubArrayDivisiblebyN	@subdivbyN	cal modulo prefix sum, and calculate combination	20th Dec

Recursion and Backtracking

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Power of N	@powOfN	reducing b in each rec call, base is b==0	20th Dec
2	Ascending/Descending till N	@PrintingN	concept of call stack	20th Dec
3	StringToInt	@stringToInt	char[i]-'0' + funccall with i+1, until i>=n ]	20th Dec
4	IntToSpelling	2048	generating a map of int and recursion with (n/10) until n==0	20th Dec
5	BinarySearchRec	binarySearch	rec with change of (low,high) until low>=high	20th Dec
6	Bubble Sort Rec	bubbleSort	call rec till j+1 and swapping if j==n-1 then n-=1 until n==1	20th Dec
7	Merge Sort Rec	MergeSort	constantly merging the array until start>=end, calling merge function to combine two arrays	20th Dec
8	Quick Sort Rec	quicksort	recursively partition around the last element until start>=end	20th Dec
9	Generating Subsequences	generatingsubseq	! Review from video !	21st Dec
10	KeyPad Substrings	keypadSubstr	iterating through 3 values(e.g 2-"abc") and calling recursion func for i+1(inp arr) and j+1(out arr)	21st Dec
11	Rat in a maze	rateInmaze	for every i,j check if "X" is present return false or if reached m,n then return true else call for func for down(i+1,j) and right(i,j+1) and mark it as 1. Mark 0 after both func are called	22nd Dec
12	N-Queen	N-queen	call recursively for row+1. construct 3 bit arrays:column,diag 1 and diag2. for every call loop from c=0 to n and check if that index is occupied in the array.	22nd Dec
13	Suduko Solver	suduko	for all empty cells try to fill no. from 1 to 9 and build a function canplace(), which checks if the no. can be placed or not. call recursively for j+1 until row end and then i+1	22nd Dec

Linked List

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Insertion	insertion	pointers	28th Dec
2	Searching	searching	recursion;iteratively	28th Dec
3	Middle element of LL	middle	slow ptr and fast ptr	28th Dec
4	Reverse	reverse	two adjacent ptrs	28th Dec
5	Deletion	deletion	two adjacent ptrs	28th Dec
6	Finding kth element from last	findingKth	traverse the fast ptr till k from head keeping the slow ptr at head. Then move both ptrs until fast reaches tail	28th Dec
7	Merging Sorted LL	mergeLL	create new ll; recursion	29th Dec
8	MergeSort using LL	mergesort	combination of finding mid point and merging two sorted LL	29th Dec
9	Detecting cycle in LL	detectCycle	slow and fast ptrs; fast moves two steps and slow move one; if slow==fast then cycle is present; if we want find the start of the cycle, move the slow to head and move both ptrs one step, the point where the meet is the start==fast is the start of cycle	29th Dec

Stacks and Queues

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Stack using vectors	stacksImpl	creating a class stack and using vector stl	29th Dec
2	Stack STL	stackSTL	STL	29th Dec
3	Queue using array	queue	front and rear pointer with isfull() and isEmpty() methods	29th Dec
4	Queue STL	queueSTL	STL	29th Dec
5	Stack Reversal using aux stack	reversal	use an addition stack. Run a loop till n; In each iteration store the top in temp and transfer rest n-i elements to aux stack; Push the temp to bottom of current stack; Transfer the n-i elements from aux stack to curr stack	30th Dec
6	Stack reversal using recustion	stackRecur	Implement two functions: reversal and place_at_bottom; reversal constantly calls itself and builds a reverse call stack, then call place_at_bottom with elements of this call stack; Place_at_bottom pushes the element at the bottom, else calls itself to build a call stack to put the element at bottom and then pushes the rest elements into the stack	30th Dec
7	Balanced Paranthesis	isBalanced	push if '(' and pop if ')' ; if the stack is empty at the end then it has a balanced parenthesis	30th Dec
8	Stock Span	stockspan	Creating a stack of indices having strictly decreasing values. ans[i] = i - indice_at_of_stack	30th Dec
9	Largest area under histogram	LargestArea	creating an leftarray having indices of smallest hist in the left side and similar for rightside. area under each hist will be (r-l-1)xCurr_len	5th Jan '21

Trees

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	BuildingBST	implementation	pointers and recursion	4th Jan
2	Height of Tree	height	recursively call left subtree and right subtree; after reaching the bottom of tree return max(left,right) +1	4th Jan
3	Level Order Traversal	levelorder	recursively call func for left and right subtree while decrementing value of k; if k==1 print the data	4th Jan
4	BFS Traversal	bfs	using queue; initializing the queue with root iteratively popping them and pushing their children into the queue until queue is empty	4th Jan
5	Count and Sum of nodes	countAndsum	recursively calling the same func for left and right subtrees	4th Jan
6	Diameter of a Tree	diameter	recursion. diameter can lie in 3 parts, height of the subtree, entirely in the left subtree or entirely in the right sub tree	4th Jan
7	ReplaceNodebySum	replaceBysum	recursion. storing the value of root in a variable and replacing it with sum of children	4th Jan
8	Is BT Balanced	isBalanced	create a pair of height and isBalanced. recursively call the func for left and right subtree. If (abs(hright-hleft))<=1 and left and right subtree then current subtree is balanced and height = max(left,right)+1	5th Jan
9	BST from Sorted Array	BSTfromArray	recursion. root->left = func(arr,start,mid-1) root->right = func(mid+1,end). until start>end.	5th Jan
10	Insertion in BST	insertion	recursion	5th Jan
11	Searching in BST	searching	recursion	5th Jan
12	Deletion in BST	deletion	3 cases; 1. no children, then simply delete. 2. one child, then store the child in temp, delete the root and return temp; 2 children, then return inorder successor	5th Jan
13	isBSTBalanced	isBSTBalanced	checking if the root is greater than max of left subtree and less than min of right sub tree and calling the same func for left and right subtrees	5th Jan
14	BSTtoLL	bstToll	Recursion. Create a class LL with node* head and node* tail. There will 4 major cases. root has: 1)no child: ll.head=ll.tail=root;2)only left child:call the recursive func with left child. ll.head=leftll.head and ll.tail=root;3)only right child: ll.head=root and ll.tail=rightll.tail; root has both the children: call function for both the children. ll.head = leftll.head, ll.tail=rightll.tail. In all the cases connect the root accordingly.	5th Jan

Heap

A heap is a complete tree.

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Insertion and Deletion	insertAndDelete	Implement through a queue. children of a node are always at 2i and 2i+1; heapify: replace the first element with last and then heapify the first element	6th Jan
2	Heap STL	heap	using queue and funtional(for min heap) header files	6th Jan
3	Merging K sorted arrays	mergeKarrays	create a heap and insert all the first elements of each array; remove the top element of the array and push a element from the same array from which the top element was removed. if array has no elements then push infinite	6th Jan
4	Median in a stream of integers	medianInstream	maintain two heaps, leftheap-a max heap and rightheap-a min heap. if there are any elements in the right queue and right.top() is smaller than current element then add into right queue else add in left queue. The difference b/w sizes of these should not be greater than 1, in such a case transfer the top element. when queried either print the avg, if size equal else print the top of the largest heap	6th Jan

Graphs

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Implementing a graph	view	Array of Linked Lists	9th Jan
2	Distance of all nodes from source	view	breadth wise traversal using queue. storing distances in a map. dist(child)=dist(parent from source)+1	9th Jan
3	Snakes and Ladders	view	making nodes and shortest path	10th Jan
4	DFS Traversal	view	recursion and map to keep a track of visited nodes	10th Jan
5	BFS Traversal	view	queue and map to keep a track of visited nodes	12th Jan
6	cycleDetection using BFS	view	map for visited and parent node. while bfs traversal if currNode is visited and parent of node!= currNode then there is a loop	12th Jan
7	cycleDetection using DFS	view	recursion, map of nodes in stack and map of visited nodes	24th Jan
8	Dijsktra Algorithm	view	----	24th Jan