Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed


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

Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.


Hashtable + array





Related Problems:

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)


Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.


[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) – Add a integer number from the data stream to the data structure.
  • double findMedian() – Return the median of all elements so far.

For example:



  1. Min/Max heap
  2. Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)



Solution 2:


Related Problems

花花酱 Leetcode 140. Word Break II


Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


Time complexity: O(2^n)

Space complexity: O(2^n)




Related Problems