Baseball Game - Leetcode

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.

Baseball Game - Leetcode

Comments

More from this blog

Atomic Habits

Mongo DB Basics

MongoDB Data-Types

Persevering Through Trials and Tribulations as a Developer: Dev Retro 2022

Shiny Object Syndrome in Tech

Command Palette

Comments

More from this blog