README.md

algorithm-playground

This repository contains:

• Data structure implementations
• Algorithms examples
• Leetcode problem's solutions
• Google Kick Start solutions
• Google Code Jam solutions

Data structure:

• Aho Corasick
• AVL tree
• Binary Indexed Tree
• Binary Min Heap (HeapMap)
• Bit Map
• Heavy Light Decomposition
• Huffman Tree
• Interval Tree
• KD Tree
• Palindromic Tree
• Segment Tree
• Segment Tree Lazy
• Segment Tree Mutable Size
• Segment Tree Sparse
• Sparse Table
• Splay Tree
• Suffix Array
• Suffix Automation
• Suffix Tree

Graph algorithms:

• Johnson's algorithm detection all simple cycles in directed graph
• Kosaraju's algorithm detection strongly connected components

Other algorithms:

• KMP Pattern Search
• Max sum subarray

Competitions:

• Google Kick Start:

  • 2019:

    • Round A:

      • Training [solution]
      • Parcels [solution]
      • Contention [solution](without hidden test set)

    • Round B:

      • Building Palindromes [solution]
      • Energy Stones [solution]
      • Diverse Subarray [solution]

    • Round C:

      • Wiggle Walk [solution]
      • Circuit Board [solution]
      • Catch Some [solution]

    • Round D:

      • X or What? [solution]
      • Latest Guests [solution]
      • Food Stalls [solution]

    • Round E:

      • Cherries Mesh [solution]
      • Code-Eat Switcher [solution]
      • Street Checkers [solution]

    • Round F:

      • Flattening [solution]
      • Teach Me [solution]
      • Spectating Villages [solution]

    • Round G:

      • Book Reading [solution]
      • The Equation [solution]
      • Shifts [solution]

• Google Code Jam

  • 2018:

    • Qualification Round:

      • Saving The Universe Again [solution]
      • Trouble Sort [solution]

  • 2019:

    • Qualification Round:

      • Foregone Solution [solution]
      • You Can Go Your Own Way [solution]
      • Cryptopangrams [solution]
      • Dat Bae [solution]

    • Round A:

      • Pylons [solution]
      • Golf Gophers [solution]
      • Alien Rhyme [solution]

    • Round B:

      • Manhattan Crepe Cart [solution]
      • Draupnir [solution]
      • Fair Fight [solution]

    • Round C:

      • Robot Programming Strategy [solution]
      • Power Arrangers [solution]
      • Bacterial Tactics [solution]

    • Round 2:

      • New Elements: Part 1 [solution]
      • Pottery Lottery [solution]
      • New Elements: Part 2 [solution]
      • Contransmutation [solution]

    • Round 3:

      • Zillionim [solution]
      • Pancake Pyramid [solution]
      • Datacenter Duplex [solution]
      • Napkin Folding [solution] (without hidden test set)

Leetcode problems:

• 1 Two Sum [solution]
• 2 Add Two Numbers [solution]
• 3 Longest Substring Without Repeating Characters [solution]
• 4 Median of Two Sorted Arrays [solution]
• 5 Longest Palindromic Substring [solution]
• 10 Regular Expression Matching [solution]
• 11 Container With Most Water [solution]
• 14 Longest Common Prefix [solution]
• 15 3Sum [solution]
• 17 Letter Combinations of a Phone Number [solution]
• 19 Remove Nth Node From End of List [solution]
• 20 Valid Parentheses [solution]
• 21 Merge Two Sorted Lists [solution]
• 22 Generate Parentheses [solution]
• 23 Merge K Sorted Lists [solution]
• 25 Reverse Nodes in K-Group [solution]
• 31 Next Permutation [solution]
• 32 Longest Valid Parentheses [solution]
• 33 Search in Rotated Sorted Array [solution]
• 34 Find First and Last Position of Element in Sorted Array [solution]
• 35 Search Insert Position [solution]
• 37 Sudoku Solver [solution]
• 39 Combination Sum [solution]
• 41 First Missing Positive [solution]
• 42 Trapping Rain Water [solution]
• 44 Wildcard Matching [solution]
• 45 Jump Game II [solution]
• 46 Permutations [solution]
• 48 Rotate Image [solution]
• 49 Group Anagrams [solution]
• 53 Maximum Subarray [solution]
• 55 Jump Game [solution]
• 56 Merge Intervals [solution]
• 57 Insert Interval [solution]
• 62 Unique Paths [solution]
• 64 Minimum Path Sum [solution]
• 70 Climbing Stairs [solution]
• 72 Edit Distance [solution]
• 75 Sort Colors [solution]
• 76 Minimum Window Substring [solution]
• 78 Subsets [solution]
• 79 Word Search [solution]
• 81 Search in Rotated Sorted Array II [solution]
• 84 Largest Rectangle in Histogram [solution]
• 85 Maximal Rectangle [solution]
• 91 Decode Ways [solution]
• 94 Binary Tree Inorder Traversal [solution]
• 96 Unique Binary Search Trees [solution]
• 97 Interleaving String [solution]
• 98 Validate Binary Search Tree [solution]
• 99 Recover Binary Search Tree [solution]
• 101 Symmetric Tree [solution]
• 102 Binary Tree Level Order Traversal [solution]
• 103 Binary Tree Zigzag Level Order Traversal [solution]
• 104 Maximum Depth Of Binary Tree [solution]
• 105 Construct Binary Tree from Preorder and Inorder Traversal [solution]
• 107 Binary Tree Level Order Traversal II [solution]
• 108 Convert Sorted Array to Binary Search Tree [solution]
• 110 Balanced Binary Tree [solution]
• 111 Minimum Depth of Binary Tree [solution]
• 112 Path Sum [solution]
• 114 Flatten Binary Tree to Linked List [solution]
• 117 Populating Next Right Pointers in Each Node II [solution]
• 121 Best Time To Buy And Sell Stock [solution]
• 123 Best Time To Buy And Sell Stock Iii [solution]
• 124 Binary Tree Maximum Path Sum [solution]
• 126 Word Ladder Ii [solution]
• 128 Longest Consecutive Sequence [solution]
• 130 Surrounded Regions [solution]
• 131 Palindrome Partitioning [solution]
• 132 Palindrome Partitioning II [solution]
• 133 Clone Graph [solution]
• 134 Gas Station [solution]
• 135 Candy [solution]
• 136 Single Number [solution]
• 138 Copy List with Random Pointer [solution]
• 139 Word Break [solution]
• 140 Word Break II [solution]
• 141 Linked List Cycle [solution]
• 142 Linked List Cycle II [solution]
• 144 Binary Tree Preorder Traversal [solution]
• 145 Binary Tree Postorder Traversal [solution]
• 146 LRU Cache [solution]
• 148 Sort List [solution]
• 152 Maximum Product Subarray [solution]
• 154 Find Minimum in Rotated Sorted Array II [solution]
• 155 Min Stack [solution]
• 160 Intersection of Two Linked Lists [solution]
• 164 Maximum Gap [solution]
• 167 Two Sum Input Array is Sorted [solution]
• 169 Majority Element [solution]
• 171 Excel Sheet Column Number [solution]
• 173 Binary Search Tree Iterator [solution]
• 174 Dungeon Game [solution]
• 188 Best Time to Buy and Sell Stock IV [solution]
• 189 Rotate Array [solution]
• 198 House Robber [solution]
• 199 Binary Tree Right Side View [solution]
• 200 Number of Islands [solution]
• 206 Reverse Linked List [solution]
• 207 Course Schedule [solution]
• 208 Implement Trie (Prefix Tree) [solution]
• 210 Course Schedule II [solution]
• 212 Word Search II [solution]
• 214 Shortest Palindrome [solution]
• 215 Kth Largest Element in an Array [solution]
• 216 Combination Sum III [solution]
• 218 The Skyline Problem [solution]
• 220 Contains Duplicate III [solution]
• 221 Maximal Square [solution]
• 222 Count Complete Tree Nodes [solution]
• 224 Basic Calculator [solution]
• 226 Invert Binary Tree [solution]
• 227 Basic Calculator II [solution]
• 230 Kth Smallest Element in a BST [solution]
• 232 Implement Queue Using Stacks [solution]
• 234 Palindrome Linked List [solution]
• 235 Lowest Common Ancestor of a Binary Search Tree [solution]
• 236 Lowest Common Ancestor of a Binary Tree [solution]
• 238 Product Of Array Except Self [solution]
• 239 Sliding Window Maximum [solution]
• 240 Search a 2D Matrix II [solution]
• 241 Different Ways to Add Parentheses [solution]
• 242 Valid Anagram [solution]
• 257 Binary Tree Paths [solution]
• 258 Add Digits [solution]
• 260 Single Number III [solution]
• 268 Missing Number [solution]
• 279 Perfect Squares [solution]
• 282 Expression Add Operators [solution]
• 283 Move Zeroes [solution]
• 287 Find the Duplicate Number [solution]
• 295 Find Median From Data Stream [solution]
• 297 SerializeAndDeserializeBinaryTree [solution]
• 300 Longest Increasing Subsequence [solution]
• 301 Remove Invalid Parentheses [solution]
• 303 Range Sum Query Immutable [solution]
• 304 Range Sum Query 2D - Immutable [solution]
• 307 Range Sum Query Mutable [solution]
• 309 Best Time to Buy and Sell Stock with Cooldown [solution]
• 310 Minimum Height Trees [solution]
• 312 Burst Balloons [solution]
• 315 Count of Smaller Numbers After Self [solution]
• 316 Remove Duplicate Letters [solution]
• 322 Coin Change [solution]
• 321 Create Maximum Number [solution]
• 327 Count Of Range Sum [solution]
• 328 Odd Even Linked List [solution]
• 329 Longest Increasing Path in a Matrix [solution]
• 330 Patching Array [solution]
• 332 Reconstruct Itinerary [solution]
• 336 Palindrome Pairs [solution]
• 337 House Robber Iii [solution]
• 338 Counting Bits [solution]
• 341 Flatten Nested List Iterator [solution]
• 343 Integer Break [solution]
• 344 Reverse String [solution]
• 347 Top K Frequent Elements [solution]
• 349 Intersection of Two Arrays [solution]
• 350 Intersection of Two Arrays II [solution]
• 352 Data Stream as Disjoint Intervals [solution]
• 354 Russian Doll Envelopes [solution]
• 355 Design Twitter [solution]
• 357 Count Numbers with Unique Digits [solution]
• 363 Max Sum of Rectangle no Larger Than K [solution]
• 378 Kth Smallest Element in a Sorted Matrix [solution]
• 381 Insert Delete Get Random Duplicates Allowed [solution]
• 382 Linked List Random Node [solution]
• 392 Is Subsequence [solution]
• 394 Decode String [solution]
• 399 Evaluate Division [solution]
• 402 Remove K Digits [solution]
• 406 Queue Reconstruction By Height [solution]
• 409 Longest Palindrome [solution]
• 410 Split Array Largest Sum [solution]
• 413 Arithmetic Slices [solution]
• 414 Third Maximum Number [solution]
• 416 Partition Equal Subset Sum [solution]
• 421 Maximum Xor Of Two Numbers In An Array [solution]
• 429 N-ary Tree Level Order Traversal [solution]
• 432 All O'One Data Structure [solution]
• 437 Path Sum III [solution]
• 438 Find All Anagrams in a String [solution]
• 442 Find all Duplicates in an Array [solution]
• 445 Add Two Numbers II [solution]
• 448 Find All Numbers Disappeared in an Array [solution]
• 451 Sort Characters By Frequency [solution]
• 452 Minimum Number of Arrows to Burst Balloons [solution]
• 454 4Sum II [solution]
• 455 Assign Cookies [solution]
• 456 132 Pattern [solution]
• 460 LFU Cache [solution]
• 461 Hamming Distance [solution]
• 464 Can I Win [solution]
• 470 Implement Rand10 Using Rand7 [solution]
• 472 Concatenated Words [solution]
• 473 Matchsticks to Square [solution]
• 476 Number Complement [solution]
• 477 Total Hamming Distance [solution]
• 486 Predict The Winner [solution]
• 493 Reverse Pairs [solution]
• 494 Target Sum [solution]
• 495 Teemo Attacking [solution]
• 501 Find Mode in Binary Search Tree [solution]
• 502 IPO [solution]
• 503 Next Greater Element II [solution]
• 508 Most Frequent Subtree Sum [solution]
• 513 Find Bottom Left Tree Value [solution]
• 515 Find Largest Value in Each Tree Row [solution]
• 517 Super Washing Machines [solution]
• 519 Random Flip Matrix [solution]
• 524 Longest Word in Dictionary Through Deleting [solution]
• 526 Beautiful Arrangement [solution]
• 528 Random Pick with Weight [solution]
• 530 Minimum Absolute Difference in BST [solution]
• 535 Encode And Decode Tiny URL [solution]
• 538 Convert BST to Greater Tree [solution]
• 542 01 Matrix [solution]
• 543 Diameter of Binary Tree [solution]
• 546 Remove Boxes [solution]
• 547 Friend Circles [solution]
• 554 Brick Wall [solution]
• 559 Maximum Depth Of N Tree [solution]
• 560 Subarray Sum Equals K [solution]
• 561 Array Partition I [solution]
• 576 Out of Boundary Paths [solution]
• 581 Shortest Unsorted Continuous Subarray [solution]
• 594 Longest Harmonious Subsequence [solution]
• 617 Merge Two Binary Trees [solution]
• 621 Task Scheduler [solution]
• 622 Design Circular Queue [solution]
• 630 Course Schedule Iii [solution]
• 632 Smallest Range [solution]
• 639 Decode Ways II [solution]
• 641 Design Circular Deque [solution]
• 646 Maximum Length Of Pair Chain [solution]
• 647 Palindromic Substrings [solution]
• 648 Replace Words [solution]
• 650 Keys Key board [solution]
• 654 Maximum Binary Tree [solution]
• 657 Robot Return To Origin [solution]
• 665 Non-decreasing Array [solution]
• 668 Kth Smallest Number in Multiplication Table [solution]
• 670 Maximum Swap [solution]
• 674 Longest Continuous Increasing Subsequence [solution]
• 675 Cut Off Trees For Golf Event [solution]
• 676 Implement Magic Dictionary [solution]
• 677 Map Sum Pairs [solution]
• 678 Valid Parenthesis String [solution]
• 684 Redundant Connection [solution]
• 685 Redundant Connection II [solution]
• 687 Longest Univalue Path [solution]
• 689 Maximum Sum Of 3 Non Overlapping Subarrays [solution]
• 690 Employee Importance [solution]
• 692 Top K Frequent Words [solution]
• 693 Binary Number with Alternating Bits [solution]
• 695 Max Area of Island [solution]
• 698 Partition to K Equal Sum Subsets [solution]
• 699 Falling Squares [solution]
• 703 Kth Largest Element in a Stream [solution]
• 705 Design HashSet [solution]
• 706 Design HashMap [solution]
• 707 Design Linked List [solution]
• 709 To Lower Case [solution]
• 710 Random Pick With Blacklist [solution]
• 712 Minimum Ascii Delete Sum For Two Strings [solution]
• 714 Best Time To Buy And Sell Stock With Transaction Fee [solution]
• 715 Range Module [solution]
• 719 Find K Th Smallest Pair Distance [solution]
• 721 Accounts Merge [solution]
• 725 Split Linked List in Parts [solution]
• 726 Number of Atoms [solution]
• 728 Self Dividing Numbers [solution]
• 731 My Calendar Ii [solution]
• 732 My Calendar III [solution]
• 739 Daily Temperatures [solution]
• 741 Cherry Pickup [solution]
• 745 Prefix and Suffix Search [solution]
• 746 Min Cost Climbing Stairs [solution]
• 752 Open The Lock [solution]
• 761 Special Binary String [solution]
• 763 Partition Labels [solution]
• 765 Couples Holding Hands [solution]
• 767 Reorganize String [solution]
• 771 Jewels And Stones [solution]
• 773 Sliding Puzzle [solution]
• 778 Swim In Rising Water [solution]
• 779 K-th Symbol in Grammar [solution]
• 780 Reaching Points [solution]
• 783 Minimum Distance Between BST Nodes [solution]
• 784 Letter Case Permutation [solution]
• 785 Is Graph Bipartite [solution]
• 786 K Th Smallest Prime Fraction [solution]
• 787 Cheapest Flights Within K Stops [solution]
• 791 Custom Sort String [solution]
• 793 Preimage Size of Factorial Zeroes Function [solution]
• 802 Find Eventual Safe States [solution]
• 803 Bricks Falling When Hit [solution]
• 805 Split Array With Same Average [solution]
• 814 Binary Tree Pruning [solution]
• 818 Race Car [solution]
• 828 Unique Letter String [solution]
• 832 Flipping an Image [solution]
• 834 Sum Of Distances In Tree [solution]
• 839 Similar String Groups [solution]
• 841 Keys and Rooms [solution]
• 844 Backspace String Compare [solution]
• 846 Hand of Straights [solution]
• 847 Shortest Path Visiting All Nodes [solution]
• 850 Rectangle Area II [solution]
• 854 KSimilar Strings [solution]
• 856 Score Of Parentheses [solution]
• 860 Lemonade Change [solution]
• 861 Score After Flipping Matrix [solution]
• 862 Shortest Subarray With Sum At Least K [solution]
• 863 All Nodes Distance K in Binary Tree [solution]
• 864 Shortest Path To Get All Keys [solution]
• 867 Transpose Matrix [solution]
• 869 Reordered Power Of 2 [solution]
• 871 Minimum Number of Refueling Stops [solution]
• 872 Leaf Similar Trees [solution]
• 876 Middle of the Linked List [solution]
• 878 Nth Magical Number [solution]
• 880 Decoded String at Index [solution]
• 884 Uncommon Words From Two Sentences [solution]
• 887 Super Egg Drop [solution]
• 890 Find and Replace Pattern [solution]
• 891 Sum Of Subsequence Widths [solution]
• 894 All Possible Full Binary Trees [solution]
• 895 Maximum Frequency Stack [solution]
• 901 Online Stock Span [solution]
• 903 Valid Permutations For Di Sequence [solution]
• 907 Sum of Subarray Minimums [solution]
• 908 Smallest Range I [solution]
• 910 Smallest Range Ii [solution]
• 921 Minimum Add to Make Parentheses Valid [solution]
• 925 Long Pressed Name [solution]
• 927 Three Equal Parts [solution]
• 931 Minimum Falling Path Sum [solution]
• 945 Minimum Increment to Make Array Unique [solution]
• 946 Validate Stack Sequences [solution]
• 952 Largest Component Size by Common Factor [solution]
• 955 Delete Columns to Make Sorted II [solution]
• 968 Binary Tree Cameras [solution]
• 975 Odd Even Jump [solution]
• 981 Time Based Key-Value Store [solution]
• 983 Minimum Cost For Tickets [solution]
• 990 Satisfiability of Equality Equations [solution]
• 997 Find the Town Judge [solution]
• 1005 Maximize Sum Of Array After K Negations [solution]
• 1011 Capacity To Ship Packages Within D Days [solution]
• 1019 Next Greater Node In Linked List [solution]
• 1027 Longest Arithmetic Sequence [solution]
• 1029 Two City Scheduling [solution]
• 1036 Escape a Large Maze [solution]
• 1047 Remove All Adjacent Duplicates In String [solution]
• 1114 Print in Order [solution]
• 1115 Print FooBar Alternately [solution]
• 1116 Print Zero Even Odd [solution]
• 1117 Building H2O [solution]
• 1124 Longest Well-Performing Interval [solution]
• 1125 Smallest Sufficient Team [solution]
• 1221 Split a String in Balanced Strings [solution]