/programming-problems

Data structures and algorithms refresher.

Primary LanguageC

Data Structures and Algorithms Problems

An algorithm problem contains 3 parts: input, output and solution/algorithm. The input can be an array, string, matrix, tree, linked list, graph, etc. The algorithm solution can be dynamic programming, binary search, BFS, DFS, or topological sort. The solution can also be a data structure, such as a stack, queue/dequeue, hash set, tree set, hash map, tree (heap, binary search tree, trie, segment tree, binary index tree), disjoint set, etc. In this file, problems are tagged by input data structures or algorithms.

Array/String

Simple Pointers

  1. Remove Duplicates from Sorted Array I
  2. Remove Duplicates from Sorted Array II
  3. Candy
  4. Trapping Rain Water
  5. Product of Array Except Self
  6. Minimum Size Subarray Sum
  7. Summary Ranges
  8. Missing Ranges
  9. Merge Intervals
  10. Insert Interval
  11. Partition Labels
  12. Find and Replace in String
  13. My Calendar II
  14. One Edit Distance
  15. Merge Sorted Array
  16. Is Subsequence
  17. Backspace String Compare
  18. Repeated String Match
  19. Container with Most Water
  20. Reverse Vowels of a String
  21. Valid Palindrome
  22. Shortest Word Distance I
  23. Shortest Word Distance II
  24. Shortest Word Distance III
  25. Intersection of Two Arrays I
  26. Intersection of Two Arrays II
  27. Two Sum II
  28. Two Sum III
  29. Three Sum
  30. Four Sum
  31. Three Sum Closest
  32. Wiggle Sort
  33. Wiggle Subsequence
  34. Longest Common Prefix
  35. Next Permutation
  36. Sentence Screen Fitting
  37. Remove Element
  38. Move Zeroes
  39. Two Sum I

Binary Search

  1. Search Insert Position
  2. Median of Two Sorted Arrays
  3. Find Minimum in Rotated Sorted Array I
  4. Find Minimum in Rotated Sorted Array II
  5. Find First and Last Position of Element in Sorted Array
  6. Guess Number Higher or Lower
  7. First Bad Version
  8. Search in Rotated Array I
  9. Search in Rotated Array II
  10. Longest Increasing Subsequence
  11. Count of Smaller Numbers After Self
  12. Russian Doll Envelopes
  13. H-Index I
  14. H-Index II

Hash Map

  1. Valid Anagram
  2. Group Shifted Strings
  3. Palindrome Pairs
  4. Line Reflection
  5. Isomorphic Strings

Sum Subarray Related Problems

  1. Two Sum
  2. Maximum Size Subarray Sum Equals k
  3. Subarray Sum Equals k

Hash Map Tracking

  1. Longest Substring Without Repeating Characters
  2. Longest Substring that contains k Unique Characters
  3. Substring with Concatenation of All Words
  4. Minimum Window Substring
  5. Longest Substring with At Least k Repeating Characters
  6. Permutation in String

Hash Set

  1. Longest Consecutive Sequence

Caching

  1. Majority Element I
  2. Majority Element II
  3. Increasing Triplet Subsequence
  4. Find the Second Largest Element in an Array

BFS

  1. Word Ladder I
  2. Word Ladder II

Heap

  1. Top k Frequent Elements
  2. Meeting Rooms I
  3. Meeting Rooms II
  4. Range Addition
  5. Merge k Sorted Arrays
  6. Merge k Sorted Lists
  7. Rearrange String k Distance Apart
  8. Minimum Cost to Hire k Workers

Tree Set

  1. Contains Duplicate I
  2. Contains Duplicate II
  3. Contains Duplicate III
  4. Max Sum of Rectangle No Larger than k
  5. Max Sum of Subarray Close to k
  6. k Empty Slots

Stream (dequeue/caching/heap/treeset)

  1. Sliding Window Maximum
  2. Moving Average from Data Stream
  3. Find Median from Data Stream
  4. Data Stream as Disjoint Intervals
  5. Linked List Random Node
  6. Shuffle an Array

Sorting

  1. Mergesort
  2. Quicksort
  3. kth Largest Element in an Array
  4. Sort Colors (Counting Sort)
  5. Maximum Gap (Bucket Sort)
  6. Group Anagrams (Bucket Sort)

Tracking Index Using an Array

  1. Ugly Number I
  2. Ugly Number II
  3. Super Ugly Number
  4. Find k Pairs with Smallest Sums from Two Arrays

Rotate

  1. Rotate Array
  2. Reverse Words in a String

Finding a Number

  1. Missing Number
  2. Find the Duplicate Number
  3. First Missing Positive

Using Index to Add Elements to a List

  1. Queue Reconstruction by Height

Iterate Within a Fixed Boundry

  1. Binary Watch
  2. Next Closest Time

Matrix

Sorted Matrix

  1. Search a 2D Matrix I
  2. Search a 2D Matrix II
  3. kth Smallest Element in a Sorted Matrix

Queue

  1. Design Snake Game

Union Find (Disjoint Set)

  1. Number of Islands II
  2. Number of Connected Components in an Undirected Graph
  3. Most Stones Removed with Same Row or Column

DFS

  1. Longest Increasing Path in Matrix
  2. Word Search I
  3. Word Search II
  4. Number of Islands (DFS/BFS)
  5. Find a Path in a Matrix
  6. Sodoku Solver
  7. Valid Sodoku
  8. Walls and Gates (DFS/BFS)

BFS

  1. Surrounded Regions

Others

  1. Set Matrix Zeroes
  2. Spiral Matrix I
  3. Spiral Matrix II
  4. Rotate Image
  5. Range Sum Query 2D - Immutable
  6. Shortest Distance from All Buildings
  7. Best Meeting Point
  8. Game of Life
  9. Tic Tac Toe

Matrix Multiplication

  1. Sparse Matrix Multiplication

Linked List

  1. Add Two Numbers
  2. Reorder List
  3. Linked List Cycle
  4. Copy List with Random Pointer
  5. Merge Two Sorted Lists
  6. Odd Even Linked List
  7. Remove Duplicates from Sorted List I
  8. Remove Duplicates from Sorted List II
  9. Partition List
  10. Intersection of Two Linked Lists
  11. Remove Linked List Elements
  12. Swap Nodes in Pairs
  13. Reverse Linked List I
  14. Reverse Linked List II
  15. Reverse Double Linked List
  16. Print Linked List in Reversed Order
  17. Remove Nth Node From End of List (Fast-Slow Pointers)
  18. Palindrome Linked List
  19. Delete Node in a Linked List
  20. Reverse Nodes in k-Group
  21. Sort List
  22. Plus One Linked List

Tree

Traversal

  1. Binary Tree Traversal
    • Preorder
    • Inorder
    • Postorder
    • Level Order I
    • Level Order II
    • Vertical Order

DFS/BFS

  1. Invert Binary Tree
  2. kth Smallest Element in a BST
  3. Binary Tree Longest Consecutive Sequence
  4. Validate Binary Search Tree
  5. Flatten Binary Tree to Linked List
  6. Path Sum I (DFS or BFS)
  7. Path Sum II (DFS)
  8. Construct Binary Tree from Inorder and Postorder Traversal
  9. Construct Binary Tree from Preorder and Inorder Traversal
  10. Convert Sorted Array to Binary Search Tree
  11. Convert Sorted List to Binary Search Tree
  12. Minimum Depth of Binary Tree
  13. Binary Tree Maximum Path Sum *
  14. Balanced Binary Tree
  15. Symmetric Tree
  16. Binary Search Tree Iterator
  17. Binary Tree Right Side View
  18. Lowest Common Ancestor of a Binary Search Tree
  19. Lowest Common Ancestor of a Binary Tree
  20. Most Frequent Subtree Sum
  21. Verify Preorder Serialization of a Binary Tree
  22. Populating Next Right Pointers in Each Node I
  23. Populating Next Right Pointers in Each Node II
  24. Unique Binary Search Trees I (DP)
  25. Unique Binary Search Trees II (DFS)
  26. Sum Root to Leaf Numbers (DFS)
  27. Count Complete Tree Nodes
  28. Closest Binary Search Tree Value
  29. Binary Tree Paths
  30. Maximum Depth of Binary Tree
  31. Recover Binary Search Tree
  32. Same Tree
  33. Serialize and Deserialize Binary Tree
  34. Inorder Successor in BST I
  35. Inorder Successor in BST II
  36. Find Leaves of Binary Tree
  37. Largest BST Subtree
  38. Convert BST to Sorted Doubly Linked List

Trie

  1. Implement Trie (Prefix Tree)
  2. Add and Search Word - Data structure design (DFS)

Segment Tree and Binary Index Tree

  1. Range Sum Query - Mutable
  2. The Skyline Problem

Stack

Stack and Queue Data Structure Implementation

  1. Implement Stack using Queues
  2. Implement Queue using Stacks
  3. Implement a Stack Using an Array
  4. Implement a Queue using an Array

Stack

  1. Evaluate Reverse Polish Notation (Stack)
  2. Valid Parentheses
  3. Longest Valid Parentheses
  4. Min Stack
  5. Max Chunks To Make Sorted

Stack Largest Rectangle

  1. Largest Rectangle in Histogram
  2. Maximal Rectangle

Stack Nested Object

  1. Mini Parser
  2. Flatten Nested List Iterator
  3. Nested List Weight Sum
  4. Nested List Weight Sum II (HashMap)
  5. Longest Absolute File Path
  6. Decode String
  7. Evaluate Math Expression

DFS

  1. Partition to K Equal Sum Subsets
  2. Permutations I
  3. Permutations II
  4. Permutation Sequence
  5. Number of Squareful Arrays
  6. Generate Parentheses
  7. Combination Sum (DFS) I
  8. Combination Sum (DFS) II
  9. Combination Sum (DFS) III
  10. Combination Sum (DFS) IV
  11. Wildcard Matching
  12. Regular Expression Matching
  13. Expressive Words
  14. Get Target Using Number List And Arithmetic Operations
  15. Flip Game I
  16. Flip Game II
  17. Word Pattern I
  18. Word Pattern II
  19. Scramble String
  20. Remove Invalid Parentheses
  21. Shortest Palindrome
  22. Lexicographical Numbers
  23. Combinations (DFS)
  24. Letter Combinations of a Phone Number (DFS)
  25. Restore IP Addresses
  26. Factor Combinations (DFS)
  27. Subsets I
  28. Subsets II

Dynamic Programming

  1. Coin Change
  2. Palindrome Partitioning I
  3. Palindrome Partitioning II
  4. House Robber I
  5. House Robber II
  6. House Robber III
  7. Jump Game I
  8. Jump Game II
  9. Best Time to Buy and Sell Stock I
  10. Best Time to Buy and Sell Stock II
  11. Best Time to Buy and Sell Stock III
  12. Best Time to Buy and Sell Stock IV
  13. Dungeon Game
  14. Decode Ways
  15. Perfect Squares
  16. Word Break I
  17. Word Break II
  18. Minimum Window Subsequence
  19. Maximal Square
  20. Minimum Path Sum
  21. Unique Paths I
  22. Unique Paths II
  23. Paint House I
  24. Paint House II
  25. Maximum Subarray
  26. Maximum Product Subarray

Dynamic Programming 2D

  1. Edit Distance
  2. Distinct Subsequences Total
  3. Longest Palindromic Substring
  4. Longest Common Subsequence
  5. Longest Common Substring

Data Structure Design

  1. LRU Cache
  2. Insert Delete GetRandom O(1)
  3. Insert Delete GetRandom O(1) - Duplicates allowed
  4. Insert Delete GetMostFrequent O(1)
  5. Design Phone Directory
  6. Design Twitter

Bit Manipulation

  1. Single Number I
  2. Single Number II
  3. Maximum Binary Gap
  4. Number of 1 Bits
  5. Reverse Bits
  6. Repeated DNA Sequences
  7. Bitwise AND of Numbers Range
  8. Sum of Two Integers
  9. Counting Bits
  10. Maximum Product of Word Lengths
  11. Gray Code
  12. UTF-8 Validation

Graph

Topological Sort

  1. Course Schedule I
  2. Course Schedule II
  3. Minimum Height Trees

DFS/BFS

  1. Graph Valid Tree
  2. Clone Graph
  3. Reconstruct Itinerary

Math/Numbers

Power

  1. Pow(x,n)
  2. Power of Two
  3. Power of Three
  4. Power of Four
  5. Super Pow

Modulo

  1. Reverse Integer
  2. Palindrome Number
  3. Nth Digit
  4. Fraction to Recurring Decimal
  5. Excel Sheet Column Number
  6. Excel Sheet Column Title
  7. Factorial Trailing Zeroes
  8. Happy Number
  9. Count Primes
  10. Plus One
  11. Divide Two Integers
  12. Multiply Strings
  13. Max Points on a Line
  14. Integer Break
  15. Add Digits
  16. Largest Divisible Subset
  17. Count Numbers with Unique Digits
  18. Rotated Digits
  19. Remove k Digits

Other

  1. Largest Number
  2. Triangle
  3. String to Integer
  4. Implement strStr()
  5. ZigZag Conversion
  6. Add Binary
  7. Length of Last Word
  8. Bulls and Cows
  9. Simplify Path
  10. Compare Version Numbers
  11. Pascal's Triangle I
  12. Pascal's Triangle II
  13. Count and Say
  14. Basic Calculator I
  15. Basic Calculator II
  16. Rectangle Area
  17. Find Peak Element
  18. Integer to English Words
  19. Text Justification
  20. Gas Station
  21. Self Crossing
  22. Patching Array
  23. Nim Game
  24. Bulb Switcher
  25. Pain Fence
  26. Nested List Weight Sum