Posts tagged as “data structure”

花花酱 LeetCode 1381. Design a Stack With Increment Operation

By zxi on March 15, 2020

Design a stack which supports the following operations.

Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
int pop() Pops and returns the top of stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Solution: Simulation

Time complexity:
init: O(1)
pop: O(1)
push: O(1)
inc: O(k)

C++

// Author: Huahua

class CustomStack {

public:

CustomStack(int maxSize): max_size_(maxSize) {}

void push(int x) {

if (data_.size() == max_size_) return;

data_.push_back(x);

}

int pop() {

if (data_.empty()) return -1;

int val = data_.back();

data_.pop_back();

return val;

}

void increment(int k, int val) {

for (int i = 0; i < min(static_cast<size_t>(k),

data_.size()); ++i)

data_[i] += val;

}

private:

int max_size_;

vector<int> data_;

};

/**

* Your CustomStack object will be instantiated and called as such:

* CustomStack* obj = new CustomStack(maxSize);

* obj->push(x);

* int param_2 = obj->pop();

* obj->increment(k,val);

花花酱 LeetCode 1172. Dinner Plate Stacks

By zxi on August 24, 2019

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output:

[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most 200000 calls will be made to push, pop, and popAtStack.

Solution: Array of stacks + TreeSet

Store all the stacks in an array, and store the indices of all free stacks in a tree set.
1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.
2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).
3. popAtIndex(): pop element from given index
3.1 add it to free set if it was full
3.2 remove it from free set if it becomes empty
3.2.1 remove it from stack array if it is the last stack

Time complexity:
Push: O(logn)
Pop: O(logn)
PopAtIndex: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

class DinnerPlates {

public:

DinnerPlates(int capacity): cap_(capacity) {}

void push(int val) {

int index = aval_.empty() ? stacks_.size() : *begin(aval_);

if (index == stacks_.size()) stacks_.emplace_back();

stack<int>& s = stacks_[index];

s.push(val);

if (s.size() == cap_)

aval_.erase(index);

else if (s.size() == 1) // only insert for the first element

aval_.insert(index);

}

int pop() { return popAtStack(stacks_.size() - 1); }

int popAtStack(int index) {

if (index < 0 || index >= stacks_.size() || stacks_[index].empty()) return -1;

stack<int>& s = stacks_[index];

int val = s.top(); s.pop();

if (s.size() == cap_ - 1) aval_.insert(index);

// Amortized O(1)

auto it = prev(end(aval_));

while (stacks_.size() && stacks_.back().empty()) {

stacks_.pop_back();

aval_.erase(it--);

}

return val;

}

private:

int cap_;

set<int> aval_;

vector<stack<int>> stacks_;

};

花花酱 LeetCode 622. Design Circular Queue

By zxi on July 12, 2018

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.

Solution: Simulate with an array

We need a fixed length array, and the head location as well as the size of the current queue.

We can use q[head] to access the front, and q[(head + size – 1) % k] to access the rear.

Time complexity: O(1) for all the operations.
Space complexity: O(k)

C++

// Author: Huahua

class MyCircularQueue {

public:

MyCircularQueue(int k): q_(k) {}

bool enQueue(int value) {

if (isFull()) return false;

q_[(head_ + size_) % q_.size()] = value;

++size_;

return true;

}

bool deQueue() {

if (isEmpty()) return false;

head_ = (head_ + 1) % q_.size();

--size_;

return true;

}

int Front() { return isEmpty() ? -1 : q_[head_]; }

int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }

bool isEmpty() { return size_ == 0; }

bool isFull() { return size_ == q_.size(); }

private:

vector<int> q_;

int head_ = 0;

int size_ = 0;

};

Java

class MyCircularQueue {

private int[] q;

private int head;

private int size;

public MyCircularQueue(int k) {

this.q = new int[k];

this.head = 0;

this.size = 0;

}

public boolean enQueue(int value) {

if (this.isFull()) return false;

this.q[(this.head + this.size) % this.q.length] = value;

++this.size;

return true;

}

public boolean deQueue() {

if (this.isEmpty()) return false;

this.head = (this.head + 1) % this.q.length;

--this.size;

return true;

}

public int Front() {

return this.isEmpty() ? -1 : this.q[this.head];

}

public int Rear() {

return this.isEmpty() ? -1 : this.q[(this.head + this.size - 1) % this.q.length];

}

public boolean isEmpty() { return this.size == 0; }

public boolean isFull() { return this.size == this.q.length; }

}

Python3

class MyCircularQueue:

def __init__(self, k: int):

self.q = [0] * k

self.k = k

self.head = self.size = 0

def enQueue(self, value: int) -> bool:

if self.isFull(): return False

self.q[(self.head + self.size) % self.k] = value

self.size += 1

return True

def deQueue(self) -> bool:

if self.isEmpty(): return False

self.head = (self.head + 1) % self.k

self.size -= 1

return True

def Front(self) -> int:

return -1 if self.isEmpty() else self.q[self.head]

def Rear(self) -> int:

return -1 if self.isEmpty() else self.q[(self.head + self.size - 1) % self.k]

def isEmpty(self) -> bool:

return self.size == 0

def isFull(self) -> bool:

return self.size == self.k

花花酱 LeetCode 432. All O`one Data Structure

By zxi on April 6, 2018

Problem

题目大意：设计一种数据结构，支持inc/dec/getmaxkey/getminkey操作，必须都在O(1)时间内完成。

https://leetcode.com/problems/all-oone-data-structure/description/

Implement a data structure supporting the following operations:

Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

Solution

Time complexity: O(1)

Space complexity: O(n), n = # of unique keys

// Author: Huahua

// Running time: 32 ms

class AllOne {

public:

/** Initialize your data structure here. */

AllOne() {}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */

void inc(string key) {

auto it = m_.find(key);

if (it == m_.end()) {

if (l_.empty() || l_.front().value != 1)

l_.push_front({1, {key}});

else

l_.front().keys.insert(key);

m_[key] = l_.begin();

return;

}

auto lit = it->second;

auto nit = next(lit);

if (nit == l_.end() || nit->value != lit->value + 1)

nit = l_.insert(nit, {lit->value + 1, {}});

nit->keys.insert(key);

m_[key] = nit;

remove(lit, key);

}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */

void dec(string key) {

auto it = m_.find(key);

if (it == m_.end()) return;

auto lit = it->second;

if (lit->value > 1) {

auto pit = prev(lit);

if (lit == l_.begin() || pit->value != lit->value - 1)

pit = l_.insert(lit, {lit->value - 1, {}});

pit->keys.insert(key);

m_[key] = pit;

} else {

// value == 1, remove from the data structure

m_.erase(key);

}

remove(lit, key);

}

/** Returns one of the keys with maximal value. */

string getMaxKey() {

return l_.empty() ? "" : *l_.back().keys.cbegin();

}

/** Returns one of the keys with Minimal value. */

string getMinKey() {

return l_.empty() ? "" : *l_.front().keys.cbegin();

}

private:

struct Node {

int value;

unordered_set<string> keys;

};

list<Node> l_;

unordered_map<string, list<Node>::iterator> m_;

// Remove from old node.

void remove(list<Node>::iterator it, const string& key) {

it->keys.erase(key);

if (it->keys.empty())

l_.erase(it);

}

};

Posts tagged as “data structure”

花花酱 LeetCode 1381. Design a Stack With Increment Operation

Solution: Simulation

C++

花花酱 LeetCode 1172. Dinner Plate Stacks

Solution: Array of stacks + TreeSet

C++

花花酱 LeetCode 622. Design Circular Queue

Solution: Simulate with an array

C++

Java

Python3

花花酱 LeetCode 432. All O`one Data Structure

Problem

Solution

Related Problems