CodingWithAmit-07/algorithms

Algorithms in python and C

Algorithms in C and Python

• All programs are categorized in level 1 to 4(1 being easiest)

List of Algorithms

Sorting

• Bubble sort: Implement bubble sort | O(n^2) | Level 2.
• Selection sort: Implement selection sort | O(n^2) | Level 2.
• Insertion sort: Implement insertion sort | O(n^2) | Level 2.
• Heap sort using max heap: Build a max heap and sort array in ascending order | Level 3.
• Heap sort using max heap - python: Build a max heap and sort array in ascending order | Level 3.
• Heap sort using min heap: Build a min heap and sort array in descending order | Level 3.
• Heap sort using min heap - python: Build a min heap and sort array in descending order | Level 3.
• Merge sort: Implement merge sort | O(nlogn) | Level 3.
• Merge sort - python: Implement merge sort in python | O(nlogn) | Level 3.
• Quick sort: Implement quick sort(C) for array of random numbers | O(nlogn) | Level 3.
• Quick sort - python: Implement quick sort(python) for array of random numbers | O(nlogn) | Level 3.
• Counting sort: Implement count sort | O(n + k) | Level 2.
• Counting sort - python: Implement count sort in python | O(n + k) | Level 2.
• Radix sort: Implement radix sort | O(digits * (n + base)) | Level 4.

Trie

• Trie implementation: Implement trie and perform insert, search and delete operations | O(L) | Level 3.
• Trie autocomplete: Implement word autocomplete feature using trie | O(ALPHABET_SIZE * N * L) | Level 3.
• Trie, sorted strings: Print all words in trie, in sorted order | O(ALPHABET_SIZE * N * L) | Level 2.
• Trie, longest prefix matching: Given a string, find a word from trie which matches longest prefix | O(n) | Level 2.
• Pattern matching using suffix tries: Implement suffix tries for pattern matching | O(m) | Level 3.

Graphs

• Graph BFS traversal: Breadth first search(BFS) traversal of directed graph | O(V + E) | Level 3.
• DFS traversal: Creates a directed graph and performs DFS traversal | O(V + E) | Level 3.
• Cycle in graph: Check if there is cycle in a directed graph, uses DFS | O(V + E) | Level 3.
• Topological sort: Topological order of directed acyclic graph(DAG) using DFS | O(V + E) | Level 3.
• Shortest path of DAG: Find shortest in a directed acyclic graph from a source vertex to all reachable vertex | O(V + E) | Level 3.
• Bellman ford: Bellman ford algo to find shortest path in a graph | O(VE) | Level 3.

Uncategorised

• Karatsuba algo: Efficient way to multiply 2 numbers, karatsuba algo | O(n^1.58) | Level 4.
• Level order tree traversal: Level order traversal of a tree | O(n^2) | Level 2.
• Level order tree traversal - python: Level order traversal of a tree | O(n^2) | Level 2.
• Level order tree traversal using queue*: Level order traversal of a tree using queue | O(n) time and space | Level 2.
• Level order tree traversal using queue - python*: Level order traversal of a tree using queue | O(n) time and space | Level 2.
• Edit distance: Find minimum operations required to convert a source string to target string | Level 3.
• Flip your caps: You all will conform | flip your cap(s) puzzle | Level 3.
• Find 1-D peak: Find 1-D peak from an array | Level 2.
• Find 2-D peak: Find 2-D peak from a 2-D array | Level 3.
• Find second largest number: Find second largest number from an array | Level 1.
• Find element with rank k: Find element with rank k(or kth smallest number) between 2 sorted arrays in ascending sorted | O(k) | Level 1.
• Find element with rank k - python: Find element with rank k(or kth smallest number) between 2 sorted arrays in ascending sorted | O(k) | Level 2.
• Find element with rank k - log(n)*: Find element with rank k(or kth smallest number) between 2 sorted arrays in ascending sorted having distinct elements | O(log(k)) | Level 3.
• Search element in rotated sorted array: Search an element from rotated sorted array | Level 3.
• Check strings has unique characters: Check if a string has all unique characters or not | Level 1.
• 2 strings are permutations: Check if 2 strings are permutations of each other or not | Level 2.
• Update input string: Update(in-place) input string to have space replaced with %20 | O(n) | Level 2.
• Is permutation palindrome: Check if any permutation of given string is palindrome or not | Level 2.
• Check 2 strings, one edit away: Check if 2 strings are max one edit away or not | O(n) | Level 2.
• String compression: Compress string, show count for consecutive repeating characters | O(n) | Level 2.
• Rotate square matrix: Rotate square matrix clockwise by 90 degrees | O(n) | Level 3.
• Clear row and column if 0 found: If an element in a matrix is 0, its entire row and column are set to 0 | O(MxN) | Level 3.
• 2 strings are rotations: Check if 2 strings are rotations of each other or not | O(n) | Level 2.
• Longest increainng subsequence - O(n^2): Find length of longest increasing subsequence from an unsorted array | O(n^2) | Level 3.
• Longest increainng subsequence - O(nlogn)*: Find length of longest increasing subsequence from an unsorted array | O(nlogn) | Level 3.
• Binary representation: Print binary representation of an integer | Level 1.
• Insert M into N: Insert bits in M to N at positions between i and j | Level 2.
• Decimal fraction to binary: Convert binary fraction number between 0 and 1 to binary representation | Level 1.
• Flip a bit, get max sequence of 1s: Flip a bit to get maximum sequence of 1s in sequence | O(b) | Level 2.
• Next largest number, same set bits: Given a positive integer, find next largest number having same number of set bits | O(b) | Level 4.
• Previous number, same set bits: Given a positive integer, find previous number having same number of set bits | O(b) | Level 4.
• Bit flips required to convert: Determine the number of bits need to flip to convert integer A to B | Level 2.
• Swap odd and even bits: Program to swap odd and even bits in an integer | Level 2.
• Update screen array, draw line: Update pixels array based on input pixel points to draw a line | Level 3.
• Knapsack problem: Given a knapsack (bag with capacity W), and N items having weights and values, Select items such that value is maximized | O(nxW) | Level 4.
• Knapsack problem - Maximize weight: Given a knapsack, maximize weights that can be carried in given knapsack, No item values given | O(nxW) | Level 4.
• Merge 2 sorted arrays, in place: Merge 2 sorted arrays, in place | O(A + B) | Level 2.
• Groups anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other. | O(MxNxlog(N)) | Level 2.
• Sorted search, no size: Search an element from an infinite sized(size of array not given) sorted array | O(log(p)) | Level 2.
• Search in sparse array: Search a string from sparsely populated array of strings (other places has empty string) | O(log(n)) | Level 2.
• Find all duplicates in array: Find all duplicates in array (range 1 to 32,000) with memory 4k | O(n) | Level 2.
• Search in sorted matrix: Search for an element in a matrix having each row and each column sorted | O(M + N) | Level 2.
• Rank from stream: Find rank of an element from a stream of data | O(logn) | Level 3.
• Peaks and valleys, sorting method: Arrange an unsorted in alternating sequence of peaks and valleys | O(NlogN) | Level 2.
• Peak and valley, O(n) method*: Arrange an unsorted array in alternating sequence of peaks and valleys | O(n) | Level 3.
• Count ways to run n steps: Count the number of ways possible to run stairs having n steps (can take 1, 2 or 3 steps) | O(n) | Level 2.
• Path of robot in grid: Find path traversed by robot to reach from 0, 0 to row - 1, col - 1 | O(rc) | Level 3.
• Min from sorted rotated: Find min element from sorted rotated array | O(log(n)) | Level 3.
• Tree level with max width: Find tree level having max width/nodes | O(n) | Level 2.
• Tree level with max width - python: Find tree level having max width/nodes | O(n) | Level 2.
• Find magic index: Find magic index from an sorted array having distinct elements | O(log(n)) | Level 2.
• Find magic index, duplicates allowed*: Find magic index from an sorted array (having duplicates) | O(log(n)) | Level 3.
• Generate all subsets of a set: Generate all subsets of a given set | O(n2^n) | Level 3.
• Generate all subsets, binary method*: Generate all subsets of a given set, binary representation method | O(n2^n) | Level 2.
• Multiply 2 integers: Multiply 2 positive integers without using multiply operator | O(log(s)) | Level 3.
• Print fibonacci numbers: Print first n fibonacci numbers | O(n) | Level 1.
• Tower of hanoi: Print steps to solve tower of hanoi problem for n disks | O(2^n) | Level 3.
• Compute all permutations - Unique chars*: Compute all permutations of a given string having unique characters | O(n^2 * n!) | Level 4.
• Compute all permutations - Repeated chars: Compute all permutations of a given string having repeated characters | O(n * n!) | Level 4+.
• Pair of valid parens: Print all valid combinations of n pairs of parentheses | O(n * n!) | Level 2.
• Paint fill: Fill surrounding area with new color | O(2^r * 2^c) | Level 2.
• Ways to represent n cents: Find number of ways to represent n cents using quarters, dimens, nickels and pennies | O(n * NUM_OF_DENOMS) | Level 4.
• Place 8 queens on 8x8: Print all ways to arrange 8 queens on a 8x8 chessboard so that none attack any other | O(GRID_SIZE^3) | Level 4.
• Stack boxes to maximize height: Stack boxes to to have maximum height | O(2^n) | Level 4.
• Boolean evaluation ways: Total number of ways to get expected boolean result from a boolean expression | O(n) | Level 3.
• Print prime numbers: Print all prime numbers from 1 to n, sieve of eratosthenes method | O(sqrt(n)log(log(n))) | Level 3.
• Find min range, k sorted arrays: Find min range which will have elements from all k arrays | O(n * k) | Level 3.
• Min positive integer missing: Find minimum positive number from an array having random integers | O(n) | Level 2.
• Min positive integer missing - O(1) space*: Find minimum positive number from an array having random integers | O(n) | Level 3.
• Create sequence of 'a' and 'b': Given 2 numbers A and B, create sequence with at max 2 consecutive 'a' and 'b' | O(A + B) | Level 3.
• Check strings same: Write a function to check if 2 strings are same, ignoring case | Level 1.
• Multiple of 4: Check if a number of 4 or not | Level 1.
• Find 7n/8: Find 7n/8 without using * and / operators | Level 1.
• Clear both elements: Clear both array elements having at least a 0 and 1 | Level 1.
• Binary palindrom: Check if a numbers binary representation is palindrome or not | Level 2.
• Product of elements: Create a array having product of all elements except element at self index | Level 2.
• Next word in dictionary: Given a string, find next dictionary word | Level 2.
• Find log(n): Write one liner program to find log(n) with some base | O(n/b) | Level 1
• Binary search tree: BST insert, traverse, delete operations | Level 2.
• Binary search tree - python: BST insert, traverse, delete operations | Level 2.
• AVL trees: Implement AVL balanced trees - Insert, delete, search | Level 3.
• AVL trees - python: Implement AVL balanced trees - Insert, delete, search | Level 3.
• Year with max population: Given birth and death years, find year with max population | O(Y + P) | Level 3.
• Linked list in python: Implement linked list in python.
• Remove duplicates from linked list: Remove duplicates from a linked list | O(n) time and space | Level 2.
• kth from last in linked list: Find kth element from last of a singly linked list | O(n) | Level 3.
• Delete node from linked list: Given only reference to an arbitary node of a linked list, delete that node | O(1) | Level 2.
• Reverse linked list: Reverse a linked list | O(n) | Level 3.
• Happy number: Check if a given number is happy or not | O(n) | Level 2.
• Partitio linked list: Partition 2 linked lists with respect to a given value | O(n) | Level 2.
• Sum digits of 2 linked list, digits in reverse order: Add 2 numbers stored in linked list in reverse order(12 is 2->1) | O(n) | Level 2.
• Sum digits of 2 linked list, digits in forward order: Add 2 numbers stored in linked list in forward order(12 is 1->2) | O(n) | Level 3.
• Is linked list palindrome: Check if linked list is palindrome or not | O(n) | Level 2.
• Median in 2 sorted arrays: Find median from 2 sorted arrays | O(log(min(m + n))) | Level 4.
• Linked list intersection: Find if two linked list intersect each other | O(m + n) | Level 2.
• Longest palindrome: Find longest palindrome from a given string | O(n^2) | Level 3.
• LCA in binary tree: Find lowest common ancestor in binary tree | O(n) | Level 3.
• LCA in BST: Find lowest common ancestor in binary search tree | O(logn) | Level 2.
• Starting node of loop in linked list: Detect loop in linked list and find starting node of loop | O(n) | Level 4.
• Spiral matrix: Given a number N, create matrix having values from 1 to N^2 in spiral form | O(N^2) | Level 3.
• Print matrix in spiral: Given a matrix, print its elements in clockwise spiral form | O(MxN) | Level 3.
• Look and say sequence: Print look and say sequence for given number of input lines | O(N) | Level 2.
• LCM and HCF: Find GCD(or HCF) and LCM of 2 numbers | Level 1.
• Separate positives and negatives: Move all positive to start and negative to end of array, 2 pointer problem, problem adapted from sort array of 0s and 1s | O(n) | Level 2.
• Track kth largest, stream of numbers: Keep track of kth largest number from a stream of numbers | O(k) | Level 2.
• Track median, stream of numbers: Keep track of median from stream of numbers | O(nlogn) | Level 4.
• Check prime: Check if a given number is prime or not | O(sqrt(n)) | Level 2.
• Find square root: Find square root of a number using babylonian convergence method | Level 4.
• Substring matching, Rabin karp: Implement rabin karp algo for substring matching | O(m + n) | Level 4.
• Substring matching, Rabin karp - python: Implement rabin karp algo for substring matching | O(m + n) | Level 4.
• Pairs having given sum: Given an array and required sum, find pairs in array that sums to required sum | O(n) time and space | Level 2.
• Connections in matrix: Count possible connections in matrix of 0s and 1s | O(MxN) | Level 2.
• Next power of 2: Find next power of 2 for a given number | Level 1.
• Round off float: Round off a float number to nearest integer | Level 1.
• Sum of digits: Find sum of digits of a given integer | Level 1.
• Generic linked list: Generic linked list in C language | Level 3.
• Count frequency of numbers: Count frequency of numbers in array | O(N) time and space | Level 1.
• Count frequency, without space: Count frequency of numbers in array | O(N) time and O(1) space | Level 2.
• Repeating numbers: Find all repeating numbers in a array | O(N) | Level 2.
• Inversion of 3: Find number of combinations which follows: a[i] > a[j] > a[k] with i < j < k in a unsorted array | O(N^2) | Level 2.
• Equilibrium index: Find equilibrium index in a array(Equal sum of left and right sub array) | O(N) | Level 2.
• Majority element from array: Find majority(more than n/2 times) element from an array | Moore's voting algo | O(N) | Level 2.
• Leaders in array: Print all leaders in array(greater than all elements right to that) | O(N) | Level 1.
• Odd occurring numberr: A array has all numbers occurring even numbers of times and 2 occurring odd number of times, find these 2 numbers | O(N) | Level 2.
• Even occurring numbers: Find 2 numbers in array(numbers from 1 to n - 2) occurring even number of times, other all occur odd number of times | O(N) | Level 3.
• Common in 3 sorted arrays: Find common elements in 3 sorted arrays | O(n1 + n2 + n3) | Level 1.
• Sorted subsequence of size 3: Find sorted subsequence of size 3 in an unsorted array | O(N) time and space | Level 3.
• Sorted subsequence of size 3, O(1) space: Find sorted subsequence of size 3 in an unsorted array | O(N) time | Level 4.
• Max average of len K: Find sub array of len K having maximum average | O(N) | Level 2.
• Subarray having given sum: Find a sub array(positive numbers) having sum | O(N) | Level 3.
• Triplets in GP: Given a sorted array, print triplets in GP | O(N^2) | Level 2.
• ASCII to int: Given an ascii string convert it to integer, atoi conversion | O(N) | Level 2.
• Largest sum of subarray: Given an unsorted array(+ve and -ve numbers), find max sum possible of a subarray | Kadane's algo | O(N) | Level 3.
• Largest sum of rotated subarray: Find max sum of rotated subarray | O(N) | Level 3.
• Triplet having given sum: Find triplets in a sorted array which sums to a given sum | O(N^2) | Level 2.
• Triplet having smaller sum: Find triplets in a sorted array which sums less than given sum | O(N^2) | Level 2.
• Distinct pairs: Find number of distinct pairs in unsorted array | O(N) | Level 4.
• Is array subset: Given 2 sorted arrays, check if arr2 is subset of arr1 | O(N) | Level 1.
• Count 0s in sorted array: Given a sorted array of 1s and 0s, find number of 0s in that array | O(logn) | Level 2.
• Merge required to make palindrome: Number of merge operations required to make an unsorted array palindrome | O(N) | Level 2.
• Jolly jumper sequence: Check if an unsorted array is jolly jumper sequence | O(N) | Level 2.
• Min number not possible: Find the min num not possible as any subset of sorted array | O(N) | Level 4.
• Subarray with equal 0 and 1: Find max subarray having equal 0s and 1s | O(N^2) | Level 2.
• Max diff btwn elements: Find max diff btwn 2 elements in array such that larger appears later | O(N) | Level 2.
• Maximize index diff: Find max(j - i) such that A[j] > A[i] | O(N) | Level 3.
• Max subarray len, arrange contiguous: Max subarray len whose elements can be arranged in contiguous sequence | O(N^2) | Level 2.
• String anagram having given md5 hash: Given an input string, md5 hashes and long list of words, find anagram of given string which has given hash | Level 3.
• JSON parser: Partial JSON parser, Ecko question | Level 2.
• Max product of subarray, size k: Find max product of a subarray, size k | O(N) | Level 2.
• Max and min product of subset: Find max and min product of subset in array | O(N) | Level 2.
• Max subarray product, 2 traversal: Find max subarray product, 2 traversals used | O(N) | Level 3.
• Max subarray product, single traversal*: Find max subarray product, single traversal | O(N) | Level 3.
• Triplet with max product: Find triplet in array with max product | O(N) | Level 2.
• Max product - index diff and min: Find max value of abs(i - j) * MIN(a[i], a[j]) from unsorted array | O(N) | Level 2.
• Max product of increasing triplet: Find max product of increasing triplet from unsorted array | O(N^2) | Level 3.
• Max min, value index pair: Find max value of (a[i] - i) - (a[j] - j) from an unsorted array | O(N) | Level 2.
• Min unique array sum: Increment array elements until all elements become unique and find sum of all unique elements | O(N) | Level 2.
• Max K such that K elements >= K: Find max k such that array has k elements greater than equal to k | O(N) | Level 2.
• Min subarray len, sum > X: Min subarray len having sum greater than X | O(N) | Level 2.
• Max sum with no elements adjacent: Find max sum with no 2 elements adjacent | O(N) | Level 3.
• Longest bitonic subsequence: Find longest bitonic subsequence in a array | O(N) | Level 3.
• Rotations to maximize sum(i * a[i]): Find number of right rotations required to maximize sum(i * a[i]) | O(N) | Level 2.
• RGB merging, get min count: Array has RGBs, merge different element and get min elements left O(N) | Level 2.
• Count strictly increasing subarrays: Count the number of strictly increasing subarrays possible | O(N) | Level 2.
• Count subarrays with even sum: Given an unsorted array, count the number of subarrays with even sum | O(N) | Level 3.
• Smallest number missing: Given a sorted array - size n, elements 0 to n - 1. Find smallest number missing | O(logn) | Level 2.
• Max sum path, 2 sorted arrays: Given 2 sorted arrays, find max sum path | O(M + N) | Level 3.
• Min distance between 2 elements - O(N^2): Find min distance 2 elements in unsorted array | O(N^2) | Level 2.
• Min distance between 2 elements - O(N): Find min distance 2 elements in unsorted array | O(N) | Level 3.
• Stock buy sell to maximize profit: Given stock prices, find days to buy and sell so that profit can be maximized | O(N) | Level 3.
• Merge 2 sorted arrays as contiguous sorted: Given 2 sorted arrays, merge them as contiguous sorted arrays | O(M * N) | Level 4.
• Steps to get given array: Find the number of steps required to get given array from all 0s array | O(K * N) | Level 2.
• Index of 0 flipped to get max 1 seq: Find the index of 0 to be changed to 1 to get max 1s sequence | O(N) | Level 3.
• Max sum after k negations: Find max sum of array elements after k negations | O(K * N) | Level 2.
• Max 0s after flipping subarray - O(N^2): Find max 0s in binary array after flipping a subarray | O(N^2) | Level 2.
• Max 0s after flipping subarray - O(N): Find max 0s in binary array after flipping a subarray | O(N) | Level 3.
• LRU cache impelementation: Put and Get operations implemented in LRU cache | Level 3.
• Find floor and ceil in array - O(N): Find floor and ceil of X from sorted array | O(N) | Level 1.
• Find floor and ceil in array: Find floor and ceil of X from sorted array | O(logn) | Level 2.
• Find floor and ceil in array - python: Find floor and ceil of X from sorted array | O(logn) | Level 2.
• Convert integer to comma format: Given an integer, convert it to string with comma notation - Indian and US | O(N) | Level 2.
• Reverse sentence: Given a sentence, reverse it's individual words | O(N) | Level 2.
• Is BST valid: Check if a tree is valid BST or not | O(N) | Level 3.
• Is symmetric tree: Check if a given tree is symmetric/self mirror image or not | O(N) | Level 2.
• Find mirror image: Find mirror image of a given binary tree | O(N) | Level 2.
• Left and right views of tree: Print left and right views of binary tree | O(N) | Level 2.
• Left/right rotate array: Rotate array left or right by given number of times | O(N) | Level 3.
• Knight's shortest path: Find shortest path from source to destination for a knight on NxN board | BFS | O(N^2) | Level 3.
• Tree inorder iterative: Tree inorder traversal without recursion, iterative approach using stack | O(N) | Level 2.
• Tree preorder iterative: Tree preorder traversal without recursion, iterative approach using stack | O(N) | Level 2.
• Vertical level order tree traversal: Perform vertical level order tree traversal | O(n) | Level 2.
• Top view of binary tree: Print elements seen from top view of a binary tree | O(N) | Level 2.
• Bottom view of binary tree: Print elements seen from bottom view of a binary tree | O(N) | Level 2.
• Tree nodes level by level: Print binary tree nodes level by level in separate lines | O(N) | Level 2.
• Nodes with distance K in binary tree: Print all nodes which are K distance away from given node in binary tree | O(N) | Level 4.
• Tree spiral level order: Print tree nodes in spiral level order | O(N) | Level 3.
• Find diameter(width) of tree: Find diameter(or max width) of a tree | O(N) | Level 2.
• Nodes with K distance from leaf: Nodes with k distance from leaf in tree | O(N) | Level 3.
• Sort array of 0s, 1s and 2s: Sort array having 0s, 1s and 2s | O(N) | Level 2.
• Kth largest number, Heap method: Find Kth largest number from an unsorted array | O(k + (n-k)logk) | Level 2.
• Kth smallest number, QuickSort method: Find Kth smallest number from an unsorted array | O(N) | Level 3.
• Longest common subsequence: Find LCS in given 2 strings | O(M * N) | Level 3.
• Subset having equal sum: Given an array, check if it can be partitioned in 2 subsets having equal sum | O(N * SUM) | Level 3.
• Kth smallest from BST: Find Kth smallest number from a BST | O(K) | Level 3.
• Next greater element: Print NGEs for all elements in given array | O(N) | Level 3.
• Binary tree to doubly linked list: Convert a binary tree to doubly linked list | O(N) | Level 3.
• Cut rod to have max profit: Find max profit obtainable by cutting up the rod and selling the pieces | O(N^2) | Level 3.
• Max product, rope cutting: Find max product obtained by cutting rope of different sizes | O(N^2) | Level 3.
• Custom split string: Split string with substrings enclosed in quotes as single | O(N) | Level 2.