Brute Force - find all the pairs and compare.

For a number in the array, we want to check the existence of the pairing number, so we can use a Set to hold the numbers to improve the search into 𝑂(1) time. This could be done in even one pass.


Given an integer array, find the pair that sum to target number.

Two Sum

If valid, the closest opening parenthesis before the first closing parenthesis must match and it should not alter the status if the most inner pair is removed.
  Stack is perfect for this question - push the openings, and try to pop on meeting closing parenthesis. If pairings are valid, the stack must be empty in the end.
  

Given an string which might contain parentheses & brackets like <code>'()abc{]}123'</code>, check if their pairings are valid.

Valid Parentheses

Since both are sorted, we only need to compare the heads of both lists, and put the smaller one into the final list. We can achieve this by 2 cursors. Remember to use a false head to handle linked list more easily.

QuickCode 75

What are your best approaches regarding time complexity?

1. Two Sum

2. Valid Parentheses

3. Merge Two Sorted Linked Lists

4. Two Sum