Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

4. Chapter 4 Solutions
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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 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 string character. 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.

bool areParenthesesBalanced(String text) {
  var stack = Stack<String>();
  for (int i = 0; i < text.length; i++) {
    final character = text[i];
    if (character == '(') {
      stack.push(character);
    } else if (character == ')') {
      if (stack.isEmpty) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty;
}
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now