Baseball Game - Leetcode

Solving and analyzing space and time complexity of an easy leetcode problem

Table of contents

No heading

No headings in the article.

This problem is very straightforward, we just have to convert the problem statement into code. However, it's a really nice problem to practice our time & space complexity analysis skills.

Link to the problem on leetcode.

I've also discussed time & space complexity following the code solution.

1. Code Solution in Java -

class Solution {
    public int calPoints(String[] ops) {

        List<Integer> scores = new ArrayList<>();

        for(String el: ops) {

            final int lastIndex = scores.size() - 1;
            int result;

            switch(el) {
                case "+":
                    result = scores.get(scores.size() - 1) + scores.get(scores.size() - 2);
                    scores.add(result);
                    break;
                case "D":
                    result = scores.get(lastIndex) * 2;
                    scores.add(result);
                    break;
                case "C":
                    scores.remove(lastIndex);
                    break;
                default:
                    scores.add(Integer.parseInt(el));
                    break;
            }
        }

        int res = 0;
        for(int el: scores) { res += el; }
        return res;
    }

}

2. Time Complexity -

Time Complexity is O(n), where n = size of ops.

O(n) is the result of looping through the ops array exactly once. All other operations inside are constant-time operations.

The remove method for case "C" could be O(n) in time complexity. However, it's just O(1) because we're removing the last element from the list. We don't need to change the list after removing the last item.

3. Space Complexity -

Space Complexity is O(n), where n ~ size of ops.

Since case "C" just invalidates the previous score without adding anything, it reduces the space taken by our List storing all the scores.

Therefore, n is approximately equal to the size of ops but not always the same.

Did you find this article valuable?

Support Jayesh Karli by becoming a sponsor. Any amount is appreciated!