Press "Enter" to skip to content

Posts tagged as “hashtable”

花花酱 LeetCode 1. Two Sum


Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.


Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Brute force / Hashtable


Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)



花花酱 LeetCode 128. Longest Consecutive Sequence



Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.


Hashtable / Hashset


Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online


Solution 2: C++ / offline


花花酱 LeetCode 208. Implement Trie (Prefix Tree)


Implement a trie with insertsearch, and startsWith methods.

You may assume that all inputs are consist of lowercase letters a-z.


Tree/children array




C++ / Array


C++ / hashmap




Python 1:


Python 2:


花花酱 LeetCode 677. Map Sum Pairs


Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:


Prefix tree

Solution 1

Solution 2:

with std::unique_ptr


花花酱 LeetCode 380. Insert Delete GetRandom O(1)


Design a data structure that supports all following operations in average O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.



Hashtable + array

Time complexity:





Related Problems: