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 and std::unordered_map works 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
     



  •  
     

    Thank you for being with us. 🙂

     




    Leave a Reply

    Notify of
    avatar
    Sort by:   newest | oldest | most voted
    Ankit
    Guest
    Ankit

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

    wpDiscuz