TODO

Repository for solving the right questions and not grinding over redundant one

TOPICS:

ALGORITHMS

1. DYNAMIC PROGRAMMING
   
2. BACKTRACKING
   
3. DIVIDE AND CONQUERE
   
4. GREEDY
   
5. GRAPH ALGORITHM
   
6. BRANCH AND BOUND
   
7. PATTERN MATCHING
   
8. RANDOMISED ALGORITHM
   
9. SORTING & SEARCHING

DATASTRUCTURE

1. TREES
2. LINKED LIST
3. STACK

Dynamic Programming Pattern

• Recursion

  • Bell Numbers
  • Tilling Problem
  • Friends Pairing Problem
  • Tiling With Dominoes
  • Painting Fence Algorithm
  • Tile Stacking Problem
  • Highway Billboard Problem
  • choose maximum weight given weight value ratio
  • maximum sum subsequence least k distant elements
  • maximum number of trailing zeros
  • hosoyas triangle
  • wildcard pattern matching
  • non crossing lines connect points circle
  • Balanced expressions such that given positions have opening brackets
  • word wrap problem
  • Maximize arr[j] – arr[i] + arr[l] – arr[k]

• 0/1 Knapsack

  • maximum sum array length less equal m --Doubt
  • maximum dot product two arrays insertion 0s --Doubt
  • Check if all people can vote on two machines

• unbounded knapsack

  • Rod Cutting

• subset sum

  • subset sum divisible m
  • largest divisible subset -Leetcode --Doubt
  • Target Sum --Leetcode
  • count of subsets with sum equal to x
  • perfect-sum-problem
  • Partition problem
  • Partition of Subset Min difference

• coin change

  • Dice Throw | DP-30
  • count of different ways
  • probability reaching point

• Longest common subsequence

  • Longest Repeated Subsequence
  • LCS for Three Strings
  • Shortest Common Supersequence
  • Count Distinct Subsequences --Doubt
  • Minimum Insertions To Form A Palindrome
  • minimum cost make two strings identical

• Longest increasing subsequence

  • Maximum Sum Bitonic Subsequence
  • Maximum Product Increasing Subsequenc
  • Count Subsequences Product Less K --Doubt
  • Maximum Length Chain Of Pairs
  • Longest Alternating Subsequence -Doubt
  • Box Stacking Problem
  • Weighted Job Scheduling
  • Building Bridges
  • minimum insertions sort array
  • min number del make sorted sequence
  • maximum sum bitonic subarray

• Longest Common Substring

• Longest palindromic subsequence

  • Count Palindromic Subsequence Given String
  • Longest Palindrome Substring
  • Count Palindrome Substring
  • number of palindromic subsequences of length k --Doubt
  • Minimum Number Deletions Make String Palindrome

• Edit distance

• Kadane’s algorithm

  • maximum subarray sum using prefix sum
  • maximum sum subarray removing one element
  • K maximum sums non-overlapping contiguous subarrays
  • Maximum product subarray
  • minimum sum submatrix given 2d array
  • Maximum Subarray Sum Excluding Certain Elements
  • K maximum sums of overlapping contiguous sub-arrays

• Matrix chain multiplication

  • Egg Dropping Puzzle
  • Boolean Parenthesization
  • Palindrome Partitioning
  • Minimum Cost Polygon Triangulation
  • optimal binary search tree
  • minimum maximum values expression

• DP on grids

  • Gold Mine Problem
  • minimum sum path
  • max decimal value path in a binary matrix
  • max sqsubmatrix with equal ele
  • maximum points collected by two persons allowed to meet once --Doubt
  • minimum sum path 3d array
  • minimum positive points to reach destination
  • minimum jumps to reach last building
  • longest path in a matrix
  • check possible path 2d matrix
  • longest increasing path matrix
  • prefix sum 2d array
  • maximize binary matrix filpping submatrix
  • number of palindromic paths in a matrix
  • Largest rectangular sub-matrix whose sum is 0
  • Largest rectangular sub-matrix having sum divisible by k
  • Largest area rectangular sub-matrix with equal number of 1’s and 0’s
  • Collect maximum points in a grid using two traversals
  • Maximum points from top left of matrix to bottom right and return back
  • Check whether row or column swaps produce maximum size binary sub-matrix with all 1s

• DP on trees

  • Count Balanced Binary Trees of Height h
  • Vertex Cover Problem
  • Largest Independent Set
  • subtree min color diff 2coloured tree
  • minimum cost to reach destination
  • multistage graph shortest path
  • Shortest path with exactly k edges in a directed and weighted graph
  • Traversal of tree with k jumps allowed between nodes of same height

• DP on bits

  • number ordered pairs ai aj 0
  • bridge torch problem
  • Find all combinations of k-bit numbers with n bits set

Place one has the fun times of linking here, but I can also link back here.

DIVIDE AND CONQUERE

• Binary Search
  • The painter’s partition problem
  • Allocate minimum number of pages
• Closest Pair of Points
• strassens matrix multiplication
• Skyline Problem
• Longest Common Prefix
• Largest Rectangular Area
• Iterative Tower of Hanoi
• Merge K sorted array
• Divide and Conquer DP

BINARY TREES

HASHTABLE

• 2 SUM
• 3 SUM
• 4 SUM
• Contiguous Array
• contiguous_integers
• count-subarrays-equal-number
• largest_subarray
• LIS
• longest_consecutive_subsequence
• Longest_subarray_ sum_divisible _k
• Maximum_length_subsequence
• max_subarray_k_elements
• pair_sum_divisible_k
• pairs whose sum is divisible by k