Life In Code

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant … Read more

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Analysis This is a DP problem. We will use a two dimensional array distance[][] … Read more

Implement int sqrt(int x). Compute and return the square root of x. Analysis We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type. There is another way, which is Newton’s Method. You can check the code here. Code … Read more

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. Analysis This problem is not so difficult. We can use two pointers, a fast pointer and a slow pointer, to achieve this. However, there are some corner cases in this problem which needs to be careful. Take 1 -> … Read more

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): “123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. Analysis We can generate all permutations until we get the kth one. But … Read more

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. Analysis We can sort the intervals first. They are sorted by their “start” value. If the “start” value is the same, “end” value is used to compare them. In Java, it’s very easy to sort them by writing a comparator. Code

… Read more

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. Analysis It would be easy to determine whether two strings are anagrams when we sort them. The complexity of sorting a string, which length is n, is $O(nlogn)$. Comparing two strings will cost $O(n)$. We … Read more

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? Analysis If we want to do this in-place, we need to find the regular pattern of rotating a point. We need to modify four points. For example, we have the matrix like the … Read more

Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. Jump Game II Given an … Read more

Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Analysis It’s easy to implement Permutation recursively. In every level we use … Read more