Data-Structures-and-Algorithms

This repository contains all the DSA problems that I have solved.

• DP: https://leetcode.com/discuss/study-guide/1000929/Solved-all-dynamic-programming-(dp)-problems-in-7-months.

  1. Knapsack(divide into two groups): https://leetcode.com/problems/last-stone-weight-ii/description/

  2. Matrix Chain Multiplication: i. https://leetcode.com/problems/burst-balloons/ ii. https://leetcode.com/problems/minimum-cost-to-merge-stones/ iii. https://www.interviewbit.com/problems/evaluate-expression-to-true/ iv. https://leetcode.com/problems/super-egg-drop/ (IMP)

  3. Kadane's Algo:

     • Maximum difference of 0's and 1's in a binary string
     • Maximum Sum Circular array
     • Smallest sum contiguous subarray
     • Largest sum increasing contiguous subarray
     • Maximum Product Subarray
     • Largest sum contiguous subarray with only non-negative elements.
     • Largest sum contiguous subarray with unique elements.
     • Maximum Alternating Sum Subarray
     • **Maximum Sum Rectangle In A 2D Matrix(IMP)

  4. LCS:

     • Longest Common Subsequence and Print LCS: https://leetcode.com/problems/longest-common-subsequence/
     • Shortest Common Supersequence and Print SCS: https://leetcode.com/problems/shortest-common-supersequence/
     • Longest Repeating subsequence: https://www.geeksforgeeks.org/longest-repeating-subsequence/
     • Length of largest subsequence of which is a substring in b: https://practice.geeksforgeeks.org/problems/find-length-of-longest-subsequence4905/1/#
     • No. of matching subsequences: https://leetcode.com/problems/number-of-matching-subsequences/
     • Find no. of times a string occurs as a subsequence: https://practice.geeksforgeeks.org/problems/find-number-of-times-a-string-occurs-as-a-subsequence3020/1/#
     • Longest Palindromic subsequence: https://leetcode.com/problems/longest-palindromic-subsequence/
     • Longest Palindromic substring: https://leetcode.com/problems/longest-palindromic-substring/
     • Count of palindromic substrings: https://leetcode.com/problems/palindromic-substrings/
     • Minimum no. of insertions to make string palindrom: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
     • Min no. of deletions and insertions to transform string:https://practice.geeksforgeeks.org/problems/minimum-number-of-deletions-and-insertions0209/1/

  5. String DP:

     • Regular Expression matching: https://leetcode.com/problems/regular-expression-matching/
     • Longest Valid Parenthesis: https://leetcode.com/problems/longest-valid-parentheses/

  6. DP GRID:

     • Within k moves: https://leetcode.com/problems/out-of-boundary-paths/, https://leetcode.com/problems/knight-probability-in-chessboard/

• Graph: https://leetcode.com/discuss/general-discussion/655708/Graph-For-Beginners-Problems-or-Pattern-or-Sample-Solutions

  1. https://practice.geeksforgeeks.org/problems/minimum-swaps/1#
  2. 0-1 BFS: https://leetcode.com/discuss/general-discussion/1234074/0-1-bfs
  3. Weighted BFS(Heap): https://leetcode.com/problems/find-all-people-with-secret/
  4. Centroid of a Tree(toposort): https://leetcode.com/problems/minimum-height-trees/
  5. Increasing paths in a grid: https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/ (there is no cycle in the graph if the path is increasing)
  6. BFS: https://leetcode.com/problems/jump-game-ii,

• Linked List: https://practice.geeksforgeeks.org/problems/length-of-longest-palindrome-in-linked-list/1/

• Increment/Decrement to make array elements distinct: 1.https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/ 2.https://leetcode.com/problems/minimum-increment-to-make-array-unique/

• DP states + BFS: https://leetcode.com/problems/shortest-path-visiting-all-nodes/

• Divide and Conquer:

  1. Merge with Divide and Conquer: https://leetcode.com/problems/merge-k-sorted-lists/
  2. Merge keep count of smaller elements: https://leetcode.com/problems/count-of-smaller-numbers-after-self/

• Minimum Swaps to make balanced string: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/ (remove already balanced string) - Greedy

• Monoqueue:

  1. https://leetcode.com/problems/jump-game-vi/
  2. https://leetcode.com/problems/sliding-window-maximum/

• Morris Traversal(Inorder and preorder traversal in amortized O(N) TC and O(1) SC): https://www.youtube.com/watch?v=80Zug6D1_r4 (Based on binary tree threading) 1.https://leetcode.com/problems/recover-binary-search-tree/

• Next Smaller or Greater: https://leetcode.com/problems/largest-rectangle-in-histogram/

• String(Greedy): https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/

• Search in 2D sorted-matrix: https://leetcode.com/problems/search-a-2d-matrix-ii/, (Diff Version) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

• Missing Number:https://www.interviewbit.com/blog/find-the-missing-number/ , https://www.interviewbit.com/problems/repeat-and-missing-number-array/ , https://www.interviewbit.com/problems/first-missing-integer/

CP

1. https://codeforces.com/contest/1690/problem/E
2. https://codeforces.com/contest/1689/problem/C
3. https://codeforces.com/contest/1697/problem/C
4. https://codeforces.com/contest/1695/problem/C

System Design

1.Design Parking Lot: https://medium.com/double-pointer/system-design-interview-parking-lot-system-ff2c58167651