Press "Enter" to skip to content

Posts tagged as “hashtable”

花花酱 LeetCode 1. Two Sum

Problem:

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.

Example:

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

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

Idea:

Brute force / Hashtable

Solution1:

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

 

Problem:

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.



Idea:

Hashtable / Hashset

 

Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online

 

Solution 2: C++ / offline

 

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

Problem:

Implement a trie with insertsearch, and startsWith methods.

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

Idea:




Tree/children array

 

 

Solution:

C++ / Array

 

C++ / hashmap

 

Java

 

Python 1:

 

Python 2:

 

花花酱 LeetCode 677. Map Sum Pairs

https://leetcode.com/problems/map-sum-pairs/description/

Problem:

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:

Idea:

Prefix tree



Solution 1

Solution 2:

with std::unique_ptr

 

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

Problem:

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.

 

Idea:

Hashtable + array

Time complexity:

O(1)

 

Solution:

 

Related Problems: