vishwajeet-hogale/Leetcode

Learning all important data structures present in STL C++

All problems being solved here are done using python, c++ or c

• Open the Problems Directory
• Check the this readme and refer to the code which is either written in python or c++ or c

Questions

1. Split the array into two partions such that the sum of both partitons is the same. Constraint : You can swap one element from one partition to another.

2. On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.

   You can move according to these rules:

   In 1 second, you can either: move vertically by one unit, move horizontally by one unit, or move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second). You have to visit the points in the same order as they appear in the array. You are allowed to pass through points that appear later in the order, but these do not count as visits.

3. Iterative knapsack problem solution.

4. Hamiltonian cycle

5. Find middle elemnt in a linked list]

6. Anagram Solution : two strings with words. Go through each word and check if anagrams can be formed. If not then minimum modification that is needed to make it into an anagram

7. License plate formatting : https://leetcode.com/problems/license-key-formatting/

8. Longest Absolute File Path : https://leetcode.com/problems/longest-absolute-file-path/

9. Next Permutation : https://leetcode.com/problems/next-permutation/

10. Memoized fibonacci

11. Count the number of paths in the grid from one location to another.

12. Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

13. Combination sum : https://leetcode.com/problems/combination-sum/

14. Maximum Subarray : https://leetcode.com/problems/maximum-subarray/

15. canSum : Function to check if a target sum be calculated given an array of numbers. Dp problem

16. climbing stairs : combination of 1's and 2's to reach nth step

17. is subsequence : Is s a subsequence of t

18. Sell and buy stocks wit htransaction fee : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

19. Integer Break : https://leetcode.com/problems/integer-break/

20. Maxdepth of a tree

21. symmetric tree

22. Balanced Binary Tree

23. FLatten Binary Tree to linked list

24. Third Maximum number in an array

25. Kth largest number in an array

26. Find Duplicate Number (Only one number is repeated in the list/array)

27. Minimum Operations to Make the Array Increasing : https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/

28. Invert Binary Tree

29. Monotone array

30. Number of Susequences

31. Count The number of Teams : https://leetcode.com/problems/count-number-of-teams/ (Backtracked)

32. Count The number of Teams : https://leetcode.com/problems/count-number-of-teams/ (Iterative)

33. Validate a binary Tree https://leetcode.com/problems/validate-binary-search-tree/

34. Range Sum of a Binary Tree

35. Two sum : Hashmap Solution https://leetcode.com/problems/two-sum/

36. Good Nodes : https://leetcode.com/problems/count-good-nodes-in-binary-tree/

37. Adding two lists

38. Checking if a linked list is a palindrome

39. Ones and zeroes https://leetcode.com/problems/ones-and-zeroes/

40. Longest paranthesis substring

41. Toeplitz Matrix : A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

42. Spiral Matrix : https://leetcode.com/problems/spiral-matrix/

43. First Unique Character : https://leetcode.com/problems/first-unique-character-in-a-string/

44. Sort by frequency : https://leetcode.com/problems/sort-characters-by-frequency/

45. Sort increasing order : https://leetcode.com/problems/sort-array-by-increasing-frequency/

46. Genearte Parenthesis : https://leetcode.com/problems/generate-parentheses/

47. Longest Substring Match : https://leetcode.com/problems/longest-substring-without-repeating-characters/

48. Add two linked lists : https://leetcode.com/problems/add-two-numbers-ii/

49. Trim BST : https://leetcode.com/problems/trim-a-binary-search-tree/

50. Remove instances of an element : https://leetcode.com/problems/remove-element/

51. Relative Sorting : https://leetcode.com/problems/relative-sort-array/

52. K Closest Points to Origin : https://leetcode.com/problems/k-closest-points-to-origin/

53. Top K frequent items : priority_queue https://leetcode.com/problems/top-k-frequent-elements/

54. All elements in two binary tree : https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

55. Rotate String : https://leetcode.com/problems/rotate-string/

56. Majority Element II : https://leetcode.com/problems/majority-element-ii/

57. Count Vowel Strings : https://leetcode.com/problems/count-sorted-vowel-strings/

58. Remove K digits

59. Minimum cost path : https://leetcode.com/problems/minimum-path-sum/

60. Permutations : https://leetcode.com/problems/permutations/

61. Paths from source to destination : https://leetcode.com/problems/all-paths-from-source-to-target/

62. Group Anagrams : https://leetcode.com/problems/group-anagrams/

63. Intersection in linked list : https://leetcode.com/problems/intersection-of-two-linked-lists/

64. Construct binary tree using preorder and inorder lists : https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

65. Hamming distance : <>

66. Find Peak Element : https://leetcode.com/problems/find-peak-element/

67. Mountain array : https://leetcode.com/problems/peak-index-in-a-mountain-array/

68. Delete a node without using head : https://leetcode.com/problems/delete-node-in-a-linked-list/

69. Number of 1 bits : https://leetcode.com/problems/number-of-1-bits/

70. Minimum cost to reach the top : https://leetcode.com/problems/min-cost-climbing-stairs/

71. Sum of all left Leaves : https://leetcode.com/problems/sum-of-left-leaves/

72. Reverse Substrings Between Each Pair of Parentheses : https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/

73. Distribute Candies : https://leetcode.com/problems/distribute-candies/

74. N Queens problem : https://leetcode.com/problems/n-queens/

75. word break : https://leetcode.com/problems/word-break/

76. Kth Smallest Element in a BST : https://leetcode.com/problems/kth-smallest-element-in-a-bst/

77. Minimum Absolute difference in bst : <>

78. Split a balanced string : https://leetcode.com/problems/split-a-string-in-balanced-strings/

79. Find common characters in words : https://leetcode.com/problems/find-common-characters/

80. Square of a sorted array : https://leetcode.com/problems/squares-of-a-sorted-array/

81. Heigh Checker : https://leetcode.com/problems/height-checker/

82. Search Insert Position : https://leetcode.com/problems/search-insert-position/

83. Number of provinces : https://leetcode.com/problems/number-of-provinces/

84. Pangram : https://leetcode.com/problems/check-if-the-sentence-is-pangram/

85. Palindrome Number : https://leetcode.com/problems/palindrome-number/

86. Add two strings : <>

87. Minimum Number of Days to Eat N Oranges : https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/

88. Binary Watch : https://leetcode.com/problems/binary-watch/

89. Prison Cells after N days : https://leetcode.com/problems/prison-cells-after-n-days/

90. Student Attendance Record I : https://leetcode.com/problems/student-attendance-record-i/

91. Power of Two : https://leetcode.com/problems/power-of-two/

92. Open Lock : https://leetcode.com/problems/open-the-lock/

93. Max area island : https://leetcode.com/problems/max-area-of-island/

94. Two sum BST : https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

95. GC of two strings : https://leetcode.com/problems/greatest-common-divisor-of-strings/

96. Reverse Vowels : https://leetcode.com/problems/reverse-vowels-of-a-string/

97. Maximum value at each level in a Binary tree : https://leetcode.com/problems/find-largest-value-in-each-tree-row/

98. Longest Consecutive Sequence : https://leetcode.com/problems/longest-consecutive-sequence/

99. 3Sum : https://leetcode.com/problems/3sum/

100. Minimum cost climbinf stairs

101. Unique Paths II : https://leetcode.com/problems/unique-paths-ii/

102. House Robber : https://leetcode.com/problems/house-robber/

103. Minimum Number of Vertices to Reach All Nodes : https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/

104. Divisor Game : https://leetcode.com/problems/divisor-game/

105. Left view of tree

106. Rod cutting : maximize product

107. Sum of left view

108. Convert BS to sorted Linked List

109. Find the City With the Smallest Number of Neighbors at a Threshold Distance : https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

110. Count Numbers with Unique Digits : https://leetcode.com/problems/count-numbers-with-unique-digits/

111. Palindrome pairs

112. Minimum Number Units oN a Truck

113. Min jums to reach n-1 position :

114. Flip an image : https://leetcode.com/problems/flipping-an-image/

115. Leaf similar trees : https://leetcode.com/problems/leaf-similar-trees/

116. Remove outer parantheses : https://leetcode.com/problems/remove-outermost-parentheses/

117. Combination sum-ii : https://leetcode.com/problems/combination-sum-ii/

118. Find bottom tree left leaf : https://leetcode.com/problems/find-bottom-left-tree-value/

119. Filter Restaurants by Vegan-Friendly, Price and Distance : https://leetcode.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance/

120. House robber II : https://leetcode.com/problems/house-robber-ii/

121. Combination Sum 3 : https://leetcode.com/problems/combination-sum-iii/

122. Remove Covered Intervals : https://leetcode.com/problems/remove-covered-intervals/

123. Longest Word in Dictionary through Deleting : https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/

124. Path with maximum gold : https://leetcode.com/problems/path-with-maximum-gold/

125. Word Search : https://leetcode.com/problems/word-search/

126. Minimum Insertion Steps to Make a String Palindrome : https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

127. Odd Even List : https://leetcode.com/problems/odd-even-linked-list/

128. Boats to save people : https://leetcode.com/problems/boats-to-save-people/

Answers File name according to numbers

1. equalarr.cpp (c++ STL approach)
2. min-path-2d-plane.cpp
3. knapsack.cpp (c++ STL approach)
4. hamiltonian.cpp (c++ STL approach)
5. midelelist.c
6. anagram.c
7. LicenseFormat.py
8. LongestAbsoluteFilePath.py
9. nextpermutation.cpp (c++ STL approach)
10. fibdp.cpp
11. countpathfromtoplefttobottomright.cpp (No memoization)
12. searchindexpostion.cpp
13. combinationsum.cpp
14. maximumsubarray.cpp (DP approach c++)
15. Dynamic_Programming/Memoization/canSum.cpp (Dp memoization)
16. Dynamic_Programming/Memoization/climbingstairs.cpp (Dp memoization)
17. issubsequence.cpp (Brute Force approach)
18. sellstockwithtransaction.py (Iterative)
19. IntegerBreak.cpp : Backtracking solution
20. Tree/maxdepth.cpp : Recursive
21. Tree/symmetrictree.cpp : Recursive
22. Tree/balancedbintree.cpp : Recursive
23. Tree/flattentree.cpp : Recursive
24. Array/thirdMax.cpp
25. Array/kthlargestarray.cpp
26. Array/FindDuplicateNumber.cpp
27. Array/MinimumOperationsToMakeIncArray.cpp
28. Tree/invertTree.cpp
29. Array/MonotoneArray.cpp : Iterative
30. Array/numberofsubsequences.cpp
31. Backtracking/CountTheNumberOfTeams.cpp
32. Array/CountTheNumberOfTeams.cpp
33. Tree/validateBinaryTree.cpp
34. Tree/RangeSumBST.cpp (inorder approach)
35. Array/twosum.cpp
36. Tree/goodnodes.cpp
37. LinkedList/addingtwolists.cpp
38. LinkedList/palindromelist.cpp
39. Recursion/oneszeroes.cpp
40. Array/longestparanthesismatch.cpp (Brute force approach)
41. Array/Toeplitzmat.cpp
42. Array/spiralmatrix.cpp
43. Array/firstuniquecharacter.cpp
44. String/sortbyfreq.cpp
45. Array/sortincfrq.cpp
46. Backtracking/generateParenthesis.cpp
47. String/longestsubstring.cpp
48. LinkedList/add-linked-list-ii.cpp
49. Tree/trimBST.cpp
50. Array/removeInstance.cpp
51. Array/relativeSorting.cpp
52. Array/kclosestpintstoorigin.cpp
53. Array/Topkfreqitems.cpp
54. Tree/allelementsin2binarytree.cpp
55. String/rotateString.cpp
56. Array/majorityElements.cpp
57. Backtracking/countVowelStrings.cpp
58. Backtracking/removeKDigits.cpp
59. Dynamic_Programming/minpathcost.cpp
60. Backtracking/all_permutations.cpp
61. Backtracking/pathsfromsourcetodestination.cpp
62. String/groupAnagrams.cpp
63. LinkedList/intersectionLinkedList.cpp
64. Tree/constructBinaryTreePI.cpp
65. Binary/hammingDistance.cpp
66. Array/findPeakElement.cpp
67. Array/MountainArray.cpp
68. LinkedList/deleteNodeWithoutHead.cpp
69. Binary/numberOf1Bits.cpp
70. Array/minCostToReachTop.cpp
71. Tree/sumOfLeftLeaves.cpp
72. String/reverseSubstringsBetweenEachParentheses.cpp
73. Array/aliceCandies.py
74. Backtracking/NQueens.cpp
75. DynamicProgramming/Memoization/wordBreak.cpp
76. Tree/kthSmallestElementBST.cpp
77. Tree/minAbsDiffBST.cpp
78. String/balacedString.cpp
79. String/findCommonCharacters.cpp
80. Array/squareSortedArray.cpp
81. Array/heightChecker.cpp
82. Array/searchInsertPosition.cpp
83. Backtracking/provinces.cpp
84. String/pangram.cpp
85. palindromeNumber.cpp
86. String/addTwoStrings.cpp
87. Recursion/fruits.cpp
88. Backtracking/binaryWatch.cpp
89. Array/prisonCellsAfterNdays.cpp
90. String/StudentAttendanceRecord.cpp
91. Recursion/powerOfTwo.cpp
92. Leetcode_challenges/Day4/openLock.cpp
93. Leetcode_challenges/Day4/maxAreaIsland.cpp
94. Tree/twoSumBST.cpp
95. String/gcdOfStrings.cpp
96. String/reverseVowels.cpp
97. Tree/maxValInLevel.cpp
98. Leetcode_challenges/Day6/longestconsecutivesequence.cpp
99. Array/3sum.cpp
100. Leetcode_challenges/Day7/minCostClimbingStairs.cpp
101. Backtracking/uniquePathsII.cpp
102. Array/houserobber.cpp
103. Graph/minNumberOfNodesNeededTOVisitAllNodes.cpp
104. divisorGame.cpp
105. Tree/leftViewOfTree.cpp
106. Dynamic_Programming/maxProductRodCutting.cpp
107. Tree/sumOfLeftView.cpp
108. Tree/bstTOSortedLinkedList.cpp
109. Graph/smallestNuberOfNeighBoursAtThresholdDistance.cpp
110. Backtracking/countUniqueDigitNumbers.cpp
111. Leetcode_challenge/Day13/palindromePairs.cpp
112. Leetcode_challenge/Day13/minNumberOfUnitsTruck.cpp
113. Greedy/minJumps2.cpp
114. Array/flipImage.py
115. Tree/leafSimilar.cpp
116. String/removeOuterParentheses.cpp
117. Backtracking/combinationSumii.cpp
118. Tree/findBottomTreeLeftLeaf.cpp
119. Array/filterRestaurant.cpp
120. Dynamic_Programming/houseRobber-ii.cpp
121. Backtracking/combinationSum3.cpp
122. Array/removeCoveredIntervals.cpp
123. String/longestWordDictionaryThroughDeletion.cpp
124. Graph/goldRunner.cpp
125. Graph/wordSearch.cpp
126. String/minInsertionsToMakePalindrome.cpp
127. LinkedList/oddEvenList.cpp
128. Greedy/boatsToSavePeople.cpp

GFG

• Backtracking

  • https://www.geeksforgeeks.org/backtracking-algorithms/

• Dynamic Programming

  • If you identify that a problem can be solved using DP
  • Try to create a backtrack function that calculates the correct answer.
  • Try to avoid the redundant arguments, minimize the range of possible values of function arguments
  • Try to optimize the time complexity of one function call
  • Memoize the values and don't calculate the same things twice.
  • Key points to remember of Dp :
    • Optimal substructure : Optimal solution to a problem involves optimal solutions to sub-problems.
    • Overlapping Sub-problems : Subproblems once computed can be stored in a table for further use. This saves the time needed to compute the same sub-problems again and again.
  • Exponential runtime can be converted/brought down to polynomial runtime.