daily algorithms practice https://github.com/leetcode-notes/daily-algorithms-practice

daily.md

8/29/20 (Sliding Window)

• https://leetcode.com/problems/sliding-window-median/
• https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
• Extra
  • https://leetcode.com/problems/split-array-with-same-average/

8/27/20 (Binary Search)

• https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
• https://leetcode.com/problems/koko-eating-bananas/
• https://leetcode.com/problems/divide-chocolate/

8/24/20 (DP)

• https://leetcode.com/problems/number-of-submatrices-that-sum-to-target
• https://leetcode.com/problems/count-submatrices-with-all-ones
• Extra
  • https://leetcode.com/problems/corporate-flight-bookings/

8/22/20 (DP)

• https://leetcode.com/problems/burst-balloons
• https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/
• https://leetcode.com/problems/frog-jump

8/20/20 (backtracking)

• https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares
• https://leetcode.com/problems/unique-paths-iii
• https://leetcode.com/problems/confusing-number-ii/

8/16/20 https://leetcode.com/problems/unique-paths-iii Use recursive search to count the valid paths. A path is valid if all of the non-obstacle cells have been visited exactly once. We check if remain == 1, since remain is the count of non-obstacle cells and a valid path should only have 1 cell left unvisited (the target cell).

https://leetcode.com/problems/confusing-number-ii/ Use backtracking to try all possible numbers. Whenever a number is not equal to its rotation, increment the total count. Then try to add other valid rotation digits to the current number and determine if the result is a confusing number.

6/21/20

• https://leetcode.com/problems/valid-parenthesis-string/
• https://leetcode.com/problems/friends-of-appropriate-ages/
• https://leetcode.com/problems/number-of-closed-islands/
• https://leetcode.com/problems/rotting-oranges/
• https://leetcode.com/problems/allocate-mailboxes/
• https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
• https://leetcode.com/problems/01-matrix/
• https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/
• https://leetcode.com/problems/minesweeper/
• https://leetcode.com/problems/count-complete-tree-nodes/
• https://leetcode.com/problems/the-k-strongest-values-in-an-array/
• https://leetcode.com/problems/decode-string/
• https://leetcode.com/problems/pacific-atlantic-water-flow/
• https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
• https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
• https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/

6/20/20

• https://leetcode.com/problems/deepest-leaves-sum/, just used level order bfs
• https://leetcode.com/problems/count-good-nodes-in-binary-tree/, dfs tree traversal, increment a counter whenever a node is found to be "good"
• https://leetcode.com/problems/delete-leaves-with-a-given-value, a little trickier, need to recursively replace nodes if they become leaves after the initial deletion process. Just need to be thoughtful about all the cases.
• https://leetcode.com/contest/weekly-contest-194/problems/making-file-names-unique/ contest q2
• https://leetcode.com/contest/weekly-contest-194/problems/xor-operation-in-an-array/ contest q1
• https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/ a variation of 2sum
• https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/ too easy
• https://leetcode.com/problems/best-sightseeing-pair/ got tripped up, but really just an implement the idea presented kind of problem
• https://leetcode.com/problems/binary-tree-level-order-traversal/ straightforward bfs, classic
• https://leetcode.com/problems/running-sum-of-1d-array/ too easy
• https://leetcode.com/problems/find-bottom-left-tree-value/ just bfs

6/17/20

• https://leetcode.com/problems/integer-to-roman/ very long and dirty code, just implement the algorithm that is presented

6/16/20

• https://leetcode.com/problems/permutations/ nice classic recursive backtracking problem

6/15/20

• https://leetcode.com/problems/island-perimeter/, used a straightforward edge counting approach

• https://leetcode.com/problems/top-k-frequent-words/ Used two hash tables one for words -> freq, another freq -> [words]. Then fetch the top k values starting from maximum possible frequency. Can also use a heap.

• https://leetcode.com/problems/repeated-dna-sequences/ Direct application of hash table

6/14/20

• https://leetcode.com/problems/maximum-number-of-balloons/ Pretty straightforward, need to determine which character is the limiting factor in creating the string "balloon". That will determine how many "balloon"(s) we can make.

• https://leetcode.com/problems/brick-wall/ Interesting problem, essentially count how many gaps and use that to calculate minimum number of bricks a vertical line will hit.

6/8/20 https://leetcode.com/problems/shuffle-the-array/ https://leetcode.com/problems/find-lucky-integer-in-an-array/ 5/30/20

5/23/20

5/16/20

• https://leetcode.com/problems/lucky-numbers-in-a-matrix/ Easy question, but quite a bit of code. First extract the min and max of each row and column respectively, store them using the index as key in a hashmap (i.e. row_min = {row:value}, col_max = {col:value}). Then traverse the entire matrix and for each element check if it is both the row_min and col_max, add it to the results list if it is.

• https://leetcode.com/problems/time-needed-to-inform-all-employees/

Three problems from weekly contest 189

• https://leetcode.com/problems/number-of-students-doing-homework-at-a-given-time/ Very easy!

• https://leetcode.com/problems/rearrange-words-in-a-sentence/ Use a hashmap to store {length:[words]}, then iterate through the possible word lengths to re-assemble the sentence. Great opportunity to use defaultdict(list) to save some code.

• https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/ Could not think of an efficient solution, but brute force passed. Check that each list is (or is not) a subset of all other lists...

5/15/20

• https://leetcode.com/problems/count-largest-group/ Easy question, straightforward use of hashmap for storing frequency counts.
• https://leetcode.com/problems/reformat-the-string/ Count number of digits and strings, check that abs(numberOfDigits - numberOfStrings) <= 1. If it is, then continue to construct the reformatted string. But need to decide whether to start with strings or digits based on which one has more elements.
• https://leetcode.com/problems/count-number-of-teams/

5/14/20

• https://leetcode.com/problems/destination-city/, Given a list of pairs representing start and end, find the "final destination" which is the destination without any paths leaving from it. Algorithm: store the start and end cities in a hash map, increase the count if the city is a "start" and don't change the count if it is end "end". After processing the entire list, find the city in the hashmap that has count of 0.

• https://leetcode.com/problems/check-if-all-1s-are-at-least-length-k-places-away/ Algorithm: Count the number of zeroes between every 1 in the array. At each 1 check if the number of zeroes is < k, if so return False. Corner case, don't perform check for 1 if at index 0.

• https://leetcode.com/problems/check-if-a-string-can-break-another-string/, sort both strings, and check if one break the other. Used to "flag" boolean variables to check if s1 breaks s2 or s2 breaks s1.

The explanation for each problem is very brief, basically enough information for me to quickly remember what the key points to the algorithm are. A detailed interview style explanation would involve walking the code through a few examples (aka "running it by hand") and pointing out corner cases, explaining the time and space complexity, and even talking about possible alternative approaches.