Category: Tutorial

In the ever present LeetCode grind that our industry puts us through I decided to solve the “Valid Parentheses” problem in LeetCode today. For a LeetCode problem it’s surprisingly practical and provides insight into how our IDEs know when we are missing a bracket within our code. Like other LeetCode problems it’s relatively straightforward once you pick the right data structure.

Before we dive in if you are the type that prefers videos over reading do check out this walk through on my Youtube channel.

The Problem

We are given a string containing the following characters: ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, and ‘]’.  We need to write a function that determines if the input string is valid. The problem defines ‘valid’ as:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets have to be closed in the right order.
3. Every close bracket has a corresponding bracket of the same type.

Let’s work through some examples:

Example 1:

Input s  = “[()]”

Output: true

This makes sense since the string starts with “[“ and is closed by “]”. Also the inner “()” closes itself since the opening and closing brackets are next to each other.

Example 2:

Input s  = “([)]”

Output: false

This makes sense since the string starts with “(“ and is closed by “]”. Although both “[“ and “(“ characters have a matching pair in the string the ordering is wrong and they don’t close each other out properly.

Solution

The core challenge with this problem is keeping track of the ordering of the open brackets as they come in and checking that they get closed later down the line. If we had to brute force this we could repeatedly scan the string, remove matching pairs and work our way through the string. Normally I would like to write a brute force solution, but in this scenario the optimal solution is actually simpler and easier to understand. There is actually an ideal data structure for this. A stack! The idea is that we push any open brackets we see onto the stack and when we see a closed bracket we pop the stack to see if the corresponding bracket is there. If it is there then we know the string is valid. If not then we know it’s invalid. If we go through the entire string and we still have stuff left in our stack then we know the string isn’t valid as well.

So what does the pseudocode for this look like?

1. Initialize an empty stack to keep track of ordering of brackets 
2. For each character in the input string:
   1. If it’s an open brace then push it onto the stack
   2. If it’s a closed brace
      1. If the stack is empty or if we pop the stack and it’s not the corresponding bracket then we return false.
3. If the stack is empty the string is valid, otherwise it’s invalid

Now let’s code it out.

public boolean isValid(String s) {
   Stack<Character> stack = new Stack<>();
   for(int i = 0; i < s.length(); i++) {
       char current = s.charAt(i);
       switch (current) {
           case '(':
           case '{':
           case '[':
               stack.push(current);
               break;
           case ')':
               if (stack.empty() || stack.pop() != '(') return false;
               break;
           case '}':
               if (stack.empty() || stack.pop() != '{') return false;
               break;
           case ']':
               if (stack.empty() || stack.pop() != '[') return false;
               break;
           default:
		           // do this in case LeetCode ever throws us a bad input
               throw new IllegalArgumentException();
       }
   }


   return stack.isEmpty();
}

public boolean isValid(String s) {
   Stack<Character> stack = new Stack<>();
   for(int i = 0; i < s.length(); i++) {
       char current = s.charAt(i);
       switch (current) {
           case '(':
           case '{':
           case '[':
               stack.push(current);
               break;
           case ')':
               if (stack.empty() || stack.pop() != '(') return false;
               break;
           case '}':
               if (stack.empty() || stack.pop() != '{') return false;
               break;
           case ']':
               if (stack.empty() || stack.pop() != '[') return false;
               break;
           default:
		           // do this in case LeetCode ever throws us a bad input
               throw new IllegalArgumentException();
       }
   }


   return stack.isEmpty();
}

If you are a seasoned LeetCoder you may prefer to write this solution using a map. That works too and the code is a bit cleaner. However in my experience I have found that switch statements to be more explicit and readable for a small character set. However for those who do prefer maps here is what that solution looks like:

public boolean isValid(String s) {
   Map<Character, Character> map = new HashMap<>();
   map.put(')', '(');
   map.put('}', '{');
   map.put(']', '[');

   Stack<Character> stack = new Stack<>();

   for (char c : s.toCharArray()) {
       if (!map.containsKey(c)) {
           stack.push(c);
       } else (map.containsKey(c)) {
           if (stack.isEmpty() || map.get(c) != stack.pop()) {
               return false;
           }
       }
   }
   return stack.isEmpty();
}

public boolean isValid(String s) {
   Map<Character, Character> map = new HashMap<>();
   map.put(')', '(');
   map.put('}', '{');
   map.put(']', '[');

   Stack<Character> stack = new Stack<>();

   for (char c : s.toCharArray()) {
       if (!map.containsKey(c)) {
           stack.push(c);
       } else (map.containsKey(c)) {
           if (stack.isEmpty() || map.get(c) != stack.pop()) {
               return false;
           }
       }
   }
   return stack.isEmpty();
}

Since we have to traverse the entire string at least once to know if it’s valid or not this solution has a time complexity of O(n). Also in the worst case scenario of all the characters being open brackets and stored on our stack then the space complexity of this solution is also O(n). This time complexity and space complexity holds true for both the switch statement and the map approach.

Key Takeaways

Although this problem is relatively straightforward I think it still teaches the critical skill of choosing the right data structure for the problem. Solving this problem without some stack-like data structure would be incredibly painful. Also, unlike most LeetCode problems it does actually have a use in the real world. Anyone who solves this can appreciate how their IDE’s bracket checking works. So I hope that the next time you see your IDE telling you that a bracket is missing you remember this problem.

Today we’ll be tackling the quintessential problem everyone starts with on LeetCode: Two Sum. It’s approachable but teaches a genuinely useful lesson: how to  pick the right data structure for a problem.

The Problem

The problem from LeetCode looks like this:

Given an array of integer nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums [3, 2, 4] and target = 6

Output: [1,2]

Explanation: because nums[1] + nums[2] == 6 so we return [1, 2]

Example 2:

Input: nums [3,3] and target = 6

Output: [0,1]

Explanation: because nums[0] + nums[1] == 6 so we return [0,1]

From the examples provided we can learn two new things about the problem. Firstly the numbers in the input are unsorted and that although we cannot use the same number twice a number can appear multiple times in the input.

Brute Force

I like to try to solve problems using a naive brute-force approach first. It often gives insight into how to give the optimal solution for the problem later. So what does a brute force algorithm for this look like? Well we can try computing the sum of every pair of numbers and seeing if they equal our target number. We can pseudocode an algorithm like below.

1. For each number in the input
   1. Go through every other number in the input
      1. Add the current number and the other number up
      2. If their sum equals target then return their indexes
      3. Otherwise go to the next pair of numbers

public int[] twoSum(int[] nums, int target) {
   // go through each number in the input nums
   for(int i = 0; i < nums.length; i++) {
       // go through each other number in the input
       for(int j = i + 1; j < nums.length; j++) {
           // if the sum of each number is equal to target then return the indexes
           if(nums[i] + nums[j] == target) {
               return new int[]{i, j};
           }
           // Otherwise go to the next pair of numbers
       }
   }

   // we should never reach this but if we do then we got a bad input
   throw new IllegalArgumentException();

}

public int[] twoSum(int[] nums, int target) {
   // go through each number in the input nums
   for(int i = 0; i < nums.length; i++) {
       // go through each other number in the input
       for(int j = i + 1; j < nums.length; j++) {
           // if the sum of each number is equal to target then return the indexes
           if(nums[i] + nums[j] == target) {
               return new int[]{i, j};
           }
           // Otherwise go to the next pair of numbers
       }
   }

   // we should never reach this but if we do then we got a bad input
   throw new IllegalArgumentException();

}

With that coded up let’s take a look at the time and space complexity of our work. In terms of space we don’t allocate any new memory so the solution is  O(1) in space. When it comes to time complexity we are O(n²). The rationale for the time complexity is that the worst case scenario for this algorithm is that the solution is the last two numbers in the input array. In that situation we would have to loop through the entire array for each preceding number until we reach the last two.

Key Insight for Optimization

The key to coming up with an optimal solution actually comes from looking at the brute-force approach. If we analyze it we notice that we lose a lot of time checking each individual pair in the inner for loop. If we could do that more efficiently then the algorithm would become dramatically faster. 

Turns out there is actually a data structure that could help with this! We could introduce a hashmap to look up numbers and indices efficiently. Using that we can avoid the extra for-loop and check immediately if we have a number that adds up to target or not. How do we know what key to look up? Well for any number and a target number we know that we need to find something equal to target - current number to have a solution. So we can look up that target - current value in our HashMap quickly.

Optimal Solution

So what does the optimal solution look like? The algorithm would look something like this. 

1. We create a map that stores values to their indexes
2. We go through each number in the input array
   1. We calculate the number we need to add our current number to get the target number
   2. We check if our map has that number we need
      1. If yes then return the indexes and we are done!
      2. Otherwise add the current number and index to our map and move on

So lets try coding that out.

public int[] twoSum(int[] nums, int target) {
   // We create a map that stores values to their indexes
   Map<Integer, Integer> valToIndex = new HashMap<>();


   // We go through each number in the input array
   for (int i = 0; i < nums.length; i++) {
       // We calculate the number we need to add our current number to get the target number
       int goal = target - nums[i];
        //We check if our map has that number we need
       if (valToIndex.containsKey(goal)) {
           // If yes then return the indexes and we are done!
           return new int[]{i, valToIndex.get(goal)};
       }


       // Otherwise add the current number and index to our map and move on
       valToIndex.put(nums[i], i);
   }


   // we should never reach this but if we do then we got a bad input
   throw new IllegalArgumentException();
}

public int[] twoSum(int[] nums, int target) {
   // We create a map that stores values to their indexes
   Map<Integer, Integer> valToIndex = new HashMap<>();


   // We go through each number in the input array
   for (int i = 0; i < nums.length; i++) {
       // We calculate the number we need to add our current number to get the target number
       int goal = target - nums[i];
        //We check if our map has that number we need
       if (valToIndex.containsKey(goal)) {
           // If yes then return the indexes and we are done!
           return new int[]{i, valToIndex.get(goal)};
       }


       // Otherwise add the current number and index to our map and move on
       valToIndex.put(nums[i], i);
   }


   // we should never reach this but if we do then we got a bad input
   throw new IllegalArgumentException();
}

With this new approach we have actually improved our time complexity to O(n). This is because the look ups in the hashmap are O(1) and we only have to loop through all the numbers in the input array once in the worst case scenario that the two numbers we need are at the end of the input array. However this speed improvement did not come for free. Out space complexity actually got worse and became O(n). This is because we need to allocate a Map that could potentially store our entire input array!

Key Takeaway

I think the most valuable lesson the Two Sum problem teaches is that if you are repeatedly searching the same list of things over and over we can make that more efficient by using a HashMap lookup pattern. This technique can be used in other LeetCode problems like Four Sum and Three Sum. So hopefully this article prepares you for the next challenges ahead!

Also if you want more of a walk through check out this Youtube Video of me solving the problem.