Top 75 Hashing Problems

Hash tables are extremely useful data structure as lookups take expected O(1) time on average, i.e. the amount of work that a hash table does to perform a lookup is at most some constant. Several data structure and algorithms problems can be very efficiently solved using hashing which otherwise have high time complexity.

In this post, we will list out few problems that can be solved in elegant fashion using hashing, with significant economy of time and space. We recommend to get yourself familiar with the following data structures before procceding to hashing problems.

• std::set, std::map, std::unordered_set, std::unordered_map in C++
• HashMap, HashSet, TreeMap in Java
• Dictionary, Set in Python

1. Find pair with given sum in an array
2. Check if subarray with 0 sum is exists or not
3. Print all sub-arrays with 0 sum
4. Find longest subsequence formed by consecutive integers
5. Find duplicates within given range k in an array
6. Count distinct absolute values in a sorted array
7. Find subarray having given sum in given array of integers
8. Find largest sub-array formed by consecutive integers
9. Find duplicate element in a limited range array
10. Find maximum length sub-array having equal number of 0’s and 1's
11. Find maximum length sub-array having given sum
12. Find majority element in an array (Boyer–Moore majority vote algorithm)
13. Custom Sort | Sort array based on another array
14. Custom Sort | Sort elements by their frequency and Index
15. Efficiently Sort an Array with many Duplicated Values
16. Calculate frequency of all elements present in an array of specified range in linear time and using constant space
17. Replace each element of an array by its corresponding rank
18. Group elements of an array based on their first occurrence
19. Find all Symmetric Pairs in an Array of Pairs
20. Construct the longest palindrome by shuffling or deleting characters from a string
21. Find count of distinct elements in every sub-array of size k
22. Print all sub-arrays of an array having distinct elements
23. Find Minimum Index of Repeating Element in an Array
24. Find Index of Maximum Occurring Element with Equal Probability
25. Check if an Array is Formed by Consecutive Integers
26. Find two non-overlapping pairs having same sum in an array
27. Find subarrays with given sum in an array
28. 3-Partition Problem
29. Find two odd occurring elements in an array without using any extra space
30. Find pairs with given difference k in an array
31. Find odd occurring element in an array in single traversal
32. Determine if two integers are equal without using comparison and arithmetic operators
33. 4 sum problem | Quadruplets with given sum
34. Find Triplet with given sum in an array
35. Find the surpasser count for each element of an array
36. Construct a binary tree from inorder and level order sequence
37. Construct a binary tree from inorder and postorder traversals
38. Construct a binary tree from inorder and preorder traversal
39. Clone a binary tree with random pointers
40. Efficiently print all nodes between two given levels in a binary tree
41. Find preorder traversal of a binary tree from its inorder and postorder sequence
42. Print Right View of a Binary Tree
43. Find postorder traversal of a binary tree from its inorder and preorder sequence
44. Iteratively print leaf to root path for every leaf node in a binary tree
45. Find a pair with given sum in a BST
46. Find maximum width of given binary tree
47. Build Binary Tree from given Parent array
48. Find the Diagonal Sum of given Binary Tree
49. Print Diagonal Traversal of Binary Tree
50. Perform vertical traversal of a binary tree
51. Find Vertical Sum in a given Binary Tree
52. Find ancestors of given node in a Binary Tree
53. Print Top View of Binary Tree
54. Print Bottom View of Binary Tree
55. Print Left View of Binary Tree
56. Print all nodes of a perfect binary tree in specific order
57. Reverse Level Order Traversal of Binary Tree
58. Spiral Order Traversal of Binary Tree
59. Level Order Traversal of Binary Tree
60. Construct a Binary Tree from Ancestor Matrix
61. Find Probability that a Person is Alive after Taking N steps on an Island
62. Link nodes present in each level of a binary tree in the form of a linked list
63. Convert a binary tree into a doubly linked list in spiral order
64. Remove duplicates from a linked list in single traversal
65. Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm)
66. Clone a Linked List with Random Pointers
67. Find all common elements present in every row of given matrix
68. Generate list of possible words from a character matrix
69. Find common elements present in all rows of a matrix
70. Find Duplicate Rows in a Binary Matrix
71. Find all words from given list that follows same order of characters as given pattern
72. Find all possible combinations by replacing given digits with characters of the corresponding list
73. Isomorphic Strings
74. Determine if two strings are anagram or not
75. Check if repeated subsequence is present in the string or not

Thank you for reading.