Jayesh Karli
Jayesh Karli's Blog

Follow

Jayesh Karli's Blog

Follow
Baseball Game - Leetcode

Photo by Eduardo Balderas on Unsplash

Baseball Game - Leetcode

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

Jayesh Karli's photo
Jayesh Karli
·Apr 10, 2022·

2 min read

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!

See recent sponsors Learn more about Hashnode Sponsors
 
Share this