Leetcode 18. 4Sum

Problem Description:

https://leetcode.com/problems/4sum/

Analysis:

This is another N-Sum problem. We may start by thinking “is the HashMap approach in 2Sum valid here”? The answer is yes if we use two loops to convert this problem into 2sum and use the hashmap approach solving it. Be aware that we need to sort the array to avoid duplication. In fact, this is no time complexity benefit in this case. The sorting takes O(N*log(N)), and the two loops take O(N^2 * N), so the entire time complexity takes O(N^3 + N * log(N)) which is O(N^3).

This is the hash map solution.

Read More

Leetcode 16. 3Sum Closest

Problem Description:

https://leetcode.com/problems/3sum-closest/

Analysis:

I came up with a greedy approach at the first place: each time, find the closest to the target, and then subtract this value from the target value and remove it from the array, and then recursively compute. However, this approach did not work for all cases. For example, it will fail in the following case:

The reason of the failure of greedy approach is because there can be negative numbers. Selecting a large number at any step is possible because there may be a negative number which can be paired with this large number to get a closer sum to the target. For example,  [-100,1,100] target = 0 , a greedy approach will force us to select  1 at the first step, but actually this is not true.

The second though was to solve it as 3Sum or 2Sum using HashMap (this solution was described here), however, it is obvious that without a concrete target value (because their sum does not have to be equal to the target), it is impossible to use the HashMap solution, because HashMap can only tell if there is a value or not but we are going to compare their differences with the target.

Read More

Leetcode 9. Palindrome Number

Problem Description:

https://leetcode.com/problems/palindrome-number/

Analysis:

If this was a string, there are many ways to check if it is palindromic: we can use two pointers from start and end, we can also reverse the string and compare them. However, for an integer, if we convert it into a string and then check if it is palindromic, it will require more than constant space. If we can get the reverse integer using constant space and compare the new integer with the original one, that would be great. Recall that in this post: Reverse Integer, we have already had a linear solution with constant space to get a reverse of an integer. What we need to do is to just copy this solution and make a simple comparison. An exception is that if the integer is negative, it will never be a palindrome because of the negative sign.

Read More

Leetcode 7. Reverse Integer

Problem Description:

https://leetcode.com/problems/reverse-integer/

Analysis:

It is a relatively simple problem, but it is also a hard problem.

It is simple because it seems that there are many ways to solve it: we can build a string and then convert it to number; we can convert the original string character array and then convert into an array of digits and calculate the result, convert into a character array and do in-place swaps, etc. Among all these methods, we don’t know which one should we started with, and what are the traps within each of these.

We still want to solve this problem in a beautiful way, so if we aim to solve it in a linear solution with constant space, we can tell that we may need to use a “digit by digit” solution.

Read More

Leetcode 6. ZigZag Conversion

Problem Description:

https://leetcode.com/problems/zigzag-conversion/

Analysis:

I won’t spend much time on this because there are not many generic approaches to take away.

You may wonder: is there any relationship between the index in the 2-d array and the index in the string? Then you may spend a lot of time to figure out the relationship and finally got nothing.

The right thing we need to do is: just write a program doing exactly like what you would do on a piece of paper. Then we can improve on the working version. The approach applies especially to the kind of problems like a game, maze, a word puzzle, etc., something seems to be not algorithm-heavy.

Read More

Leetcode 5. Longest Palindromic Substring

Problem Description:

https://leetcode.com/problems/longest-palindromic-substring/

Analysis:

The problem asks for

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

REMINDER: read until the end, otherwise you will get it wrong.

The “longest”. As we have mentioned in previous posts, looking for “longest” substring usually relates to Dynamic Programming or Sliding Window algorithm. Let’s see which one fits the best here.

If we use Dynamic Programming approach, we need to memorize something like “the longest palindromic substring length so far” for each position, or something else; seems feasible.

If we use Sliding Window approach; we might need two pointers: a start and an end. Each time we expand the end pointer, check if the substring formed by start and end pointer is palindromic. When it reaches the end of the string, move start pointer forward a position and do the same thing. Feasible but is is clearly a Brute Force method: it basically tries all possible substrings and checks if each of them is palindromic. We do not want this, let’s take a deeper think of the Dynamic Programming approach then.

Read More

Leetcode 4. Median of Two Sorted Arrays

Problem Description:

https://leetcode.com/problems/median-of-two-sorted-arrays/

Analysis:

(Aside: Please note that this article mainly focuses on the thought process. An idea introduced in the beginning may be completely overturned in later paragraphs, so please be sure the read until the end. Also, this is intended to illustrate the process of deriving an initial solution -> figure out something wrong -> make a fix -> repeat until found a working solution.)

This is actually a very difficult problem. Let’s first gather some initial thoughts from the problem description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Read More

Leetcode 3. Longest Substring Without Repeating Characters

Problem Description:

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Analysis:

For questions asking about longest, largest, etc., we may try to think about Dynamic Programming and Sliding Window. In this case, we can try both on a piece of paper and will find out that sliding window should be the approach. If you are not familiar with sliding window algorithm, you can imagine a window formed by a starting point and ending point on an axis. They both can move freely but the starting point has to be on the left-hand side of (smaller than) the ending point. The sliding window algorithm is basically to move end point to a situation where it can no longer expand, then move starting point gradually towards to ending point. Depending on what you need, you may either want to try to move ending point further each time moving starting point or move starting point towards ending point to a situation the “window” can no longer shrink, then move ending point further again.

Read More

Leetcode 2. Add Two Numbers

Problem Description:

https://leetcode.com/problems/add-two-numbers/

Analysis:

The solution is obvious that just to go through the two linked lists at the same time, add the number and make the sum a new node into the result. However, this can be a very buggy program if not careful.

This time, we will try to find corner cases using test-driven development. So let’s create tests first.

When creating tests, we must come up all possible situations that may break the code. In industry production, we must also be careful of invalid or meaningless or harmful inputs (e.g. SQL injection), but we don’t have to worry about them here.

Before creating tests, let’s take another look at the input requirement: each input is a linked list of integers. During the interview, it is better to ask the interviewer if we can assume the input is valid, which in this case, yes, so we can assume that each linked list node is an integer from 0 to 9. When creating tests cases, we can hand calculate the expected outputs as well unless the algorithm is extremely complex.

Some tests and expected outputs can be:

Read More

Leetcode 1. Two Sum

Problem Description:

https://leetcode.com/problems/two-sum/

Analysis:

The brute force solution is so obvious and trivial; the main focus is to find out an elegant way.

Let’s start by analyzing the brute force approach: two nested loops; the outer loop iterates from index 0 to the end, and the inner loop iterates from the next index of outer loop to the end. We check if they can sum to the target then. An O(n^2) solution. At each inner loop step, we are actually looking for a number that can be summed up to the target with outer loop number. This is where we may try something to improve.

So, we need a way to find out whether there is a number in the array. This easily leads us to think about using a HashTable. If we can map the array into a hash table, using the array value as key, and the array index as value, then we can easily tell if a value exists in the array by checking if the hash table contains the key. The original inner loop is O(N), and the hash table approach reduces it to O(1) because we do not need an inner loop anymore. Implementing a hash table needs us to loop over the array; this is inevitable, thus the entire program is now O(N).

Read More