Let's make this one less mysterious. For 641. Design Circular Deque, the solution in this repository is mainly a data structure design solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are insertFront, insertLast, deleteFront, deleteLast, getFront.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 48 ms, faster than 25.07% of C++ online submissions for Design Circular Deque.
02//Memory Usage: 13.9 MB, less than 100.00% of C++ online submissions for Design Circular Deque.
03class MyCircularDeque {
04public:
05 vector<int> q;
06 int head, curSize;
07 bool isStart;
08
09 /** Initialize your data structure here. Set the size of the deque to be k. */
10 MyCircularDeque(int k) {
11 q = vector<int>(k, -1);
12 head = 0;
13 curSize = 0;
14 isStart = true;
15 }
16
17 /** Adds an item at the front of Deque. Return true if the operation is successful. */
18 bool insertFront(int value) {
19 if(isFull()) return false;
20 if(isEmpty()){
21 head = 0;
22 }else{
23 head = (head-1+q.size()) % q.size();
24 }
25 q[head] = value;
26 curSize++;
27 // for(int i = 0; i < q.size(); i++){
28 // cout << q[i] << " ";
29 // }
30 // cout << endl;
31 return true;
32 }
33
34 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
35 bool insertLast(int value) {
36 if(isFull()) return false;
37 q[(head+curSize) % q.size()] = value;
38 curSize++;
39 // for(int i = 0; i < q.size(); i++){
40 // cout << q[i] << " ";
41 // }
42 // cout << endl;
43 return true;
44 }
45
46 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
47 bool deleteFront() {
48 if(isEmpty()) return false;
49 q[head] = -1;
50 head = (head+1) % q.size();
51 curSize--;
52 // for(int i = 0; i < q.size(); i++){
53 // cout << q[i] << " ";
54 // }
55 // cout << endl;
56 return true;
57 }
58
59 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
60 bool deleteLast() {
61 if(isEmpty()) return false;
62 q[(head+curSize-1) % q.size()] = -1;
63 curSize--;
64 // for(int i = 0; i < q.size(); i++){
65 // cout << q[i] << " ";
66 // }
67 // cout << endl;
68 return true;
69 }
70
71 /** Get the front item from the deque. */
72 int getFront() {
73 return q[head];
74 }
75
76 /** Get the last item from the deque. */
77 int getRear() {
78 return q[(head+curSize-1) % q.size()];
79 }
80
81 /** Checks whether the circular deque is empty or not. */
82 bool isEmpty() {
83 return curSize == 0;
84 }
85
86 /** Checks whether the circular deque is full or not. */
87 bool isFull() {
88 return curSize == q.size();
89 }
90};
91
92/**
93 * Your MyCircularDeque object will be instantiated and called as such:
94 * MyCircularDeque* obj = new MyCircularDeque(k);
95 * bool param_1 = obj->insertFront(value);
96 * bool param_2 = obj->insertLast(value);
97 * bool param_3 = obj->deleteFront();
98 * bool param_4 = obj->deleteLast();
99 * int param_5 = obj->getFront();
100 * int param_6 = obj->getRear();
101 * bool param_7 = obj->isEmpty();
102 * bool param_8 = obj->isFull();
103 */
104
105//no edge case
106//https://leetcode.com/problems/design-circular-deque/discuss/155209/c%2B%2B-99-ring-buffer-no-edge-cases.-fb-interviewer-really-loves-it.-easy-to-impl-in-4mins.-cheers!
107//Runtime: 48 ms, faster than 25.07% of C++ online submissions for Design Circular Deque.
108//Memory Usage: 14.1 MB, less than 100.00% of C++ online submissions for Design Circular Deque.
109class MyCircularDeque {
110public:
111 vector<int> q;
112 int head, tail, curSize;
113
114 /** Initialize your data structure here. Set the size of the deque to be k. */
115 MyCircularDeque(int k) {
116 q = vector<int>(k, -1);
117 head = k-1; //exclusive
118 tail = 0; //exclusive
119 curSize = 0;
120 }
121
122 /** Adds an item at the front of Deque. Return true if the operation is successful. */
123 bool insertFront(int value) {
124 if(isFull()) return false;
125 q[head] = value;
126 head = (head-1+q.size()) % q.size();
127 curSize++;
128 return true;
129 }
130
131 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
132 bool insertLast(int value) {
133 if(isFull()) return false;
134 q[tail] = value;
135 tail = (tail+1) % q.size();
136 curSize++;
137 return true;
138 }
139
140 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
141 bool deleteFront() {
142 if(isEmpty()) return false;
143 head = (head+1) % q.size();
144 q[head] = -1;
145 curSize--;
146 return true;
147 }
148
149 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
150 bool deleteLast() {
151 if(isEmpty()) return false;
152 tail = (tail-1+q.size()) % q.size();
153 q[tail] = -1;
154 curSize--;
155 return true;
156 }
157
158 /** Get the front item from the deque. */
159 int getFront() {
160 return q[(head+1) % q.size()];
161 }
162
163 /** Get the last item from the deque. */
164 int getRear() {
165 return q[(tail-1+q.size()) % q.size()];
166 }
167
168 /** Checks whether the circular deque is empty or not. */
169 bool isEmpty() {
170 return curSize == 0;
171 }
172
173 /** Checks whether the circular deque is full or not. */
174 bool isFull() {
175 return curSize == q.size();
176 }
177};
178
179/**
180 * Your MyCircularDeque object will be instantiated and called as such:
181 * MyCircularDeque* obj = new MyCircularDeque(k);
182 * bool param_1 = obj->insertFront(value);
183 * bool param_2 = obj->insertLast(value);
184 * bool param_3 = obj->deleteFront();
185 * bool param_4 = obj->deleteLast();
186 * int param_5 = obj->getFront();
187 * int param_6 = obj->getRear();
188 * bool param_7 = obj->isEmpty();
189 * bool param_8 = obj->isFull();
190 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.