Month: July 2014

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

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. Analysis To find the trapped water at position i, we need to find the maximum value of the left elements of i and right elements of … Read more

Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. Analysis We are required to use constant space. So we need to use the array. We can put the element, which value is i, in position i – 1. After … Read more

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. Analysis In fact, in … Read more