Hashing Problems in Data Structure

 
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 have basic understanding of how std::unordered_set/HashSet and std::unordered_map/HashMap works in C++/Java before moving to below Hashing Problems.

 

  • Find pair with given sum in the array
     
  • Shuffle a given array of elements (Fisher–Yates shuffle)
     
  • Find majority element in an array (Boyer–Moore majority vote algorithm)
     
  • Check if subarray with 0 sum is exists or not
     
  • Find sub-array with 0 sum
     
  • Find maximum length sub-array having given sum
     
  • Find maximum length sub-array having equal number of 0’s and 1’s
     
  • Find a duplicate element in a limited range array
     
  • Find largest sub-array formed by consecutive integers
     
  • Find subarray having given sum in given array of integers
     
  • Find Triplet with given sum in an array
     
  • 4 sum problem | Quadruplets with given sum
     
  • Custom Sort | Sort elements by their frequency and Index
     
  • Custom Sort | Sort elements of the array by order of elements defined by the second array
     
  • Find probability that a person is alive after taking N steps on the island
     
  • Check if repeated subsequence is present in the string or not
     
  • Determine if two strings are anagram or not
     
  • Isomorphic Strings
     
  • Find all combinations by replacing given digits with characters of the corresponding list
     
  • Find all words from given list that follows same order of characters as given pattern
     
  • Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm)
     
  • Remove duplicates from a linked list
     
  • Level Order Traversal of Binary Tree
     
  • Spiral Order Traversal of Binary Tree
     
  • Reverse Level Order Traversal of Binary Tree
     
  • Print all nodes of a given binary tree in specific order
     
  • Print Left View of a Binary Tree
     
  • Print Right View of a Binary Tree
     
  • Print Bottom View of Binary Tree
     
  • Print Top View of Binary Tree
     
  • Find ancestors of given node in a Binary Tree
     
  • Find Vertical Sum in a given Binary Tree
     
  • Print nodes in vertical order of a given Binary Tree (Vertical Traversal)
     
  • Find the diagonal sum of given binary tree
     
  • Print Diagonal Traversal of Binary Tree
     
  • Memory efficient Trie Implementation using Map | Insert, Search and Delete
     
  • Find Duplicate rows in a binary matrix
     
  • Find numbers represented as sum of two cubes for two different pairs
     
  • Remove duplicates from a linked list
     
  • 4 sum problem | Quadruplets with given sum
     
  • Find pairs with given difference k in the array
     
  • Find odd occurring element in an array in single traversal
     
  • Find two odd occurring element in an array without using any extra space
     
  • Print leaf to root path for every leaf node in a binary tree
     
  • Find maximum width of given binary tree
     
  • Build Binary Tree from given Parent array
     
  • Find a pair with given sum in a BST
     
  • Efficiently Sort an Array with many Duplicated Values
     
  • Replace each element of the array by its corresponding rank in the array
     
  • Find all common elements present in every row of given matrix
     
  • Group elements of an array based on their first occurrence
     
  • Find inorder successor for given key in a BST
     
  • Find all Symmetric Pairs in an Array of Pairs
     
  • Construct the longest palindrome by shuffling or deleting characters from a string
     
  • Find count of distinct elements in every sub-array of size k
     
  • Find Minimum Index of Repeating Element in an Array
     
  • Find Index of Maximum Occurring Element with Equal Probability
     
  • Check if an Array is Formed by Consecutive Integers
     
  • Find two non-overlapping pairs having same sum in an array
     
  • Construct a Binary Tree from Ancestor Matrix
     
  • Find common elements present in all rows of a matrix
     
  • Determine if a pattern matches with a string or not
     
  • Count the distinct absolute values in the sorted array
     
  • Find subarrays with given sum in an array
     
  • Find the surpasser count for each element of an array
     
  • Calculate frequency of all elements present in an array of specified range in linear time and using constant space
     

    •  
     

    Thank you for being with us. 🙂

     


    Leave a Reply

    avatar
      Subscribe  
    newest oldest most voted
    Notify of
    Ankit
    Guest
    Ankit

    nice collection. I love solving problem with the help of hashing..

    Vote Up2Vote Down  Reply
    1 year ago