Press "Enter" to skip to content

Posts tagged as “data structure”

花花酱 LeetCode 1845. Seat Reservation Manager

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

  • SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
  • int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
  • void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

Example 1:

Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output

[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

Constraints:

  • 1 <= n <= 105
  • 1 <= seatNumber <= n
  • For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
  • For each call to unreserve, it is guaranteed that seatNumber will be reserved.
  • At most 105 calls in total will be made to reserve and unreserve.

Solution: TreeSet

Time complexity: O(nlogn)
Space complexity: O(n)

C++

花花酱 LeetCode 1825. Finding MK Average

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

  1. If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
  2. Remove the smallest k elements and the largest k elements from the container.
  3. Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

  • MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
  • void addElement(int num) Inserts a new element num into the stream.
  • int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]

Explanation MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // current elements are [3] obj.addElement(1); // current elements are [3,1] obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist. obj.addElement(10); // current elements are [3,1,10] obj.calculateMKAverage(); // The last 3 elements are [3,1,10]. // After removing smallest and largest 1 element the container will be [3]. // The average of [3] equals 3/1 = 3, return 3 obj.addElement(5); // current elements are [3,1,10,5] obj.addElement(5); // current elements are [3,1,10,5,5] obj.addElement(5); // current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); // The last 3 elements are [5,5,5]. // After removing smallest and largest 1 element the container will be [5]. // The average of [5] equals 5/1 = 5, return 5

Constraints:

  • 3 <= m <= 105
  • 1 <= k*2 < m
  • 1 <= num <= 105
  • At most 105 calls will be made to addElement and calculateMKAverage.

Solution 1: Multiset * 3

Use three multiset to track the left part (smallest k elements), right part (largest k elements) and mid (middle part of m – 2*k elements).

Time complexity: addElememt: O(logn), average: O(1)
Space complexity: O(n)

C++

花花酱 LeetCode 1670. Design Front Middle Back Queue

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

  • FrontMiddleBack() Initializes the queue.
  • void pushFront(int val) Adds val to the front of the queue.
  • void pushMiddle(int val) Adds val to the middle of the queue.
  • void pushBack(int val) Adds val to the back of the queue.
  • int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
  • int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
  • int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:

  • Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
  • Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].

Example 1:

Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]
Explanation:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // return 1 -> [4, 3, 2]
q.popMiddle();    // return 3 -> [4, 2]
q.popMiddle();    // return 4 -> [2]
q.popBack();      // return 2 -> []
q.popFront();     // return -1 -> [] (The queue is empty)

Constraints:

  • 1 <= val <= 109
  • At most 1000 calls will be made to pushFrontpushMiddlepushBackpopFrontpopMiddle, and popBack.

Solution: List + Middle Iterator

Time complexity: O(1) per op
Space complexity: O(n) in total

C++

花花酱 LeetCode 1656. Design an Ordered Stream

There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.

Implement the OrderedStream class:

  • OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
  • String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
    • If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
    • Otherwise, return an empty list.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Solution: Straight Forward

Time complexity: O(n) in total
Space complexity: O(n)

C++

Python3

花花酱 LeetCode 1206. Design Skiplist

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to adderase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:


Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

  • bool search(int target) : Return whether the target exists in the Skiplist or not.
  • void add(int num): Insert a value into the SkipList. 
  • bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Constraints:

  • 0 <= num, target <= 20000
  • At most 50000 calls will be made to searchadd, and erase.

Solution:

C++

Python3