4 Chapter 4 Solutions

Solution to Challenge 1

One of the prime use cases for stacks is to facilitate backtracking. If you push a sequence of values into the stack, sequentially popping the stack will give you the values in reverse order.

void printInReverse<E>(List<E> list) {
  var stack = Stack<E>();

  for (E value in list) {
    stack.push(value);
  }

  while (stack.isNotEmpty) {
    print(stack.pop());
  }
}

If you try it with ['d', 'r', 'a', 'w', 'e', 'r'] you’ll get a reward. :]

The time complexity of pushing all of the list elements into the stack is O(n). The time complexity of popping the stack to print the values is also O(n). Overall, the time complexity of this algorithm is O(n).

Since you’re allocating a container (the stack) inside the function, you also incur an O(n) space complexity cost.

Note

The way you should reverse a list in production code is to call the reversed method that List provides. This method is O(1) in time and space. This is because as an iterable it’s lazy and only creates a reversed view into the original collection. If you traverse the items and print out all of the elements, it predictably makes the operation O(n) in time while remaining O(1) in space.

Solution to Challenge 2

To check if there are balanced parentheses in the string, you need to go through each character of the string. When you encounter an opening parenthesis, you’ll push that onto a stack. Conversely, if you encounter a closing parenthesis, you should pop the stack.

Here’s what the code looks like:

bool checkParentheses(String text) {
  var stack = Stack<int>();

  final open = '('.codeUnitAt(0);
  final close = ')'.codeUnitAt(0);

  for (int codeUnit in text.codeUnits) {
    if (codeUnit == open) {
      stack.push(codeUnit);
    } else if (codeUnit == close) {
      if (stack.isEmpty) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty;
}

The time complexity of this algorithm is O(n), where n is the number of code units in the string. This algorithm also incurs an O(n) space complexity cost due to the usage of the Stack data structure.