Posts from the “Algorithm” Category

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.

Discussion:

In C++, containers supporting insert with O(1) are vector, list, unordered_map, and unordered_set.

Containers remove by value with O(1) are unordered_map, unordered_set.

Container supporting random access is vector.

So, we can use vector AND unordered_set or unordered_map for the three functions. Then unordered_set or unordered_map? We have to use vector to store the values for the sake of random access with O(1). And a hash container (unordered_set, or unordered_map) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so unordered_map wins: reference the same value in the vector by the value’s position.

insert and random access can easily being done with O(1) for vector and unordered_map. But for remove, it affects the unordered_map‘s reference in the vector. The instinct is removing the value from the vector by getting its position from unordered_map. But this will decrease the positions of all descending elements in the vector, which affects the references of the unordered_map. The time complexity could be up to linear O(n) if we do position update in the unordered_map, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the vector, and updating the last element’s value in the unordered_map with the new position.  exactly O(1) on average.

O(log(m + n)) and O(m + n) Solutions of Median of Two Sorted Arrays

This is a LeetCode problem:

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

It is not hard to come out a solution with O(m + n) or O(log(m + n)), but it’s really tricky to deal with boundary conditions.

A O(log(m + n)) solution should use something like binary search. I referenced an answer in the discussion board, and wrote my O(log(m + n)) solution. The idea is to make the median index as the k of the k-lowest search problem. For even length, the two median indices are (m + n + 1) >> 1 and (m + n + 2) >> 1; for odd length, (m + n + 1) >> 1 and (m + n + 2) >> 1 yield the same results! That’s really clever. With the median index, we find the k-lowest value in a recursion function. Here is the code:

Capture

For the brute force solution, with O(m + n) complexity, we keep sorting the two arrays by comparing the current values until we reach the median index:

Capture