• ``````class Solution {
public int calPoints(String[] ops) {
int sum = 0;
for (String op : ops) {
if (op.equals("C")) {
sum -= list.removeLast();
}
else if (op.equals("D")) {
sum += list.peekLast();
}
else if (op.equals("+")) {
sum += list.peekLast();
}
else {
sum += list.peekLast();
}
}
return sum;
}
}
``````

• Awesome! Could you explain why using `LinkedList` instead of `ArrayList`(Advantages)? Thanks!

• @BryanBo.Cao yea pretty sure the add function on `LinkedList` is O(n) compared to an `ArrayList`'s O(1)

• I did it with stack.

``````class Solution {
public int calPoints(String[] ops) {
if(ops == null || ops.length == 0) return 0;
Stack<Integer> st = new Stack<Integer>();
int len = ops.length;
int total = 0,
new_pts = 0,
temp = 0;
for(int i=0;i<len;++i){
switch(ops[i]){
case "+":
if(st.size() > 1){
temp = st.pop();
new_pts = temp + st.peek();
st.push(temp);
st.push(new_pts);
total += new_pts;
}
break;
case "C":
if(!st.isEmpty()) total -= st.pop();
break;
case "D":
if(!st.isEmpty()){
total += st.peek() << 1;
st.push(st.peek()<<1);
}
break;
default:
temp = Integer.parseInt(ops[i]);
st.push(temp);
total += temp;
}

}

}
}
``````

• @BryanBo.Cao yea pretty sure the add function on `LinkedList` is O(n) compared to an `ArrayList`'s O(1)

Thanks! But if the add function on `LinkedList` is O(n) greater than `ArrayList`'s O(1) then why do we use `LinkedList`?
nʕ-͏̶̶̶̯͡-ʔn

• @BryanBo.Cao that's the point. we dont want to use `LinkedList`

• @BryanBo.Cao yea pretty sure the add function on `LinkedList` is O(n) compared to an `ArrayList`'s O(1)

LinkedList's is O(1). Why wouldn't it be?

And ArrayList's isn't O(1) but only amortized O(1).

• This post is deleted!

• ``````    public int calPoints(String[] ops) {
if(ops == null) return 0;
Stack<Integer> s = new Stack<Integer>();
int sum = 0;
for(int i=0; i<ops.length; i++)
{
if(ops[i].equals("C"))
{
if(s.isEmpty())
return -1;
int x = s.pop();
sum -= x;
}
else if(ops[i].equals("D"))
{
int x = s.peek();
x = x * 2;
s.push(x);
sum += x;
}
else if(ops[i].equals("+"))
{
if(s.size() < 2)
return -1;
int t1 = s.pop();
int t2 = s.pop();
s.push(t2);
s.push(t1);
s.push(t1 + t2);
sum += t1 + t2;
}
else
{
int x = Integer.parseInt(ops[i]);
s.push(x);
sum += x;
}
}

return sum;
}
}``````

• @Vivek
I did it with stack too, and here is my solution:

``````public int calPoints(String[] ops) {
int sum = 0;
Stack<Integer> stack = new Stack<>();
for (String s : ops) {
if (s.equals("C")) sum -= stack.pop();
else if (s.equals("D")) {
stack.push(stack.peek() * 2);
sum += stack.peek();
}
else if (s.equals("+")) {
int last = stack.pop();
int add = last + stack.peek();
stack.push(last);
sum += stack.peek();
}
else {
stack.push(Integer.parseInt(s));
sum += stack.peek();
}
}
return sum;
}
``````

• @dilyar Yes, with stack it becomes pretty intuitive.

• ``````import java.util.ArrayList;
import java.util.regex.Pattern;
class Solution {
public int calPoints(String[] ops) {
int sum = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
Pattern pattern = Pattern.compile("^[-]?[\\d]*\$");
for (int i = 0; i < ops.length; i++) {
if (pattern.matcher(ops[i]).matches()) {
} else if(ops[i] == "C"){
list.remove(list.size() - 1);
}
else if(ops[i] == "D"){
}
else if (ops[i] == "+") {
}
}

for (int j = 0; j < list.size(); j++) {
sum += list.get(j);
}
return sum;
}
}
``````

I don't know why I get the right values in my Eclipse, however when I run it on the LeetCode, it got the inconsistent value.

• I use stack

``````class Solution {
public int calPoints(String[] ops) {
Stack<Integer> stack = new Stack<>();
int sum = 0;
for (String s: ops) {
if (s.equals("D")) {
stack.push(stack.peek() * 2);
sum += stack.peek();
} else if (s.equals("C")) {
sum -= stack.pop();
} else if (s.equals("+")) {
int sec = stack.peek();
stack.pop();
int fir = stack.peek();
int cur = fir + sec;
stack.push(sec);
stack.push(cur);
sum += cur;
} else {
stack.push(Integer.parseInt(s));
sum += stack.peek();
}
}
return sum;
}
}
``````

• If the ops[0]="C" then the application will throw java.util.NoSuchElementException.
So we may need add the special logic to handle this situation.

`````` public int calPoints(String[] ops) {
int sum = 0;
for (String op : ops) {
if (op.equals("C")) {
if(null!=list.peekLast()){
sum -= list.removeLast();
}
}
else if (op.equals("D")) {
if(list.peekLast()!=null){
sum += list.peekLast();
}
}
else if (op.equals("+")) {
if(list.peekLast()!=null && list.size()>=2){
sum += list.peekLast();
}
}
else {
sum += list.peekLast();
}
}
return sum;
}
``````

This may work better.

• This post is deleted!

• `list.get(list.size() - 2));`

This call right here is exactly why LinkedList is one of the worst choices of data structures to store the points. Since it is a LinkedList, calling .get() is O(N) and you are calling .size() within that get which is also O(N).

Consider at least storing (and updating appropriately) the size of your LinkedList as a variable :-)

What part of

``````public int size() {
return size;
}
``````

makes you say O(N)?

And that `get` call is O(1) as well. As you can see elsewhere in the code if you just bother to look. And as you should expect after reading the first two paragraphs of the documentation.

• @ManuelP For + you can remove the last element from LinkedList (O(1)) and then add it back after calculating sum. LinkedList/Deque is a great data structure to solve this problem cleanly.

• @zeebo Hmm, but why would you do that? That's two unnecessary modifications. Is that supposed to be somehow better than what shawngao does? And please show the code, would be good to have for comparison.

@shawngao Why do you use `peekLast` instead of `getLast`? As far as I can tell, the difference is that `peekLast` returns `null` if the list is empty, but it's not like you can actually handle a `null` value, so I find this rather misleading.

• @ManuelP I think the get(list.size() - 2) is O(n) operation, but removing 1 element from Deque is O(1) operation. This is my code:

class Solution {
public int calPoints(String[] ops) {
int sum = 0;
for (String s : ops) {
if (s.equals("C") && !points.isEmpty()) {
sum -= points.removeLast();
} else if (s.equals("D") && !points.isEmpty()) {
int val = points.peekLast() * 2;
sum += val;
} else if (s.equals("+") && points.size() >= 2) {
int last = points.removeLast();
int plus = last + points.peekLast();
sum += plus;
} else {
int val = Integer.parseInt(s);
sum += val;
}
}
return sum;
}
}

• @ManuelP I think the get(list.size() - 2) is O(n) operation

As I already said, it's O(1).