Tag Archives: array

Max subarray, and Max sub rectangle less than K

This is a variation of this post. Besides finding the max continuous subarray, it requires that the max value should be less or equal to K. The solution is to store all the sum[right] for arr[0, …, right]. Then try to find the sum[left] for arr[0, …, left], which we can get max(sum[right] – sum[left])… Read More »

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in… Read More »

WordDistanceI, II, III

3 problems are from leetcode. WordDistanceI Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”]. Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”,… Read More »

Create maximum number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize… Read More »

Number of combination of triangle

Given an array with all positive numbers. Find how many number of group are there which is able to make a triangle. For example, Given {3, 4, 5}, return 1 Given {3, 4, 5, 6}, return 4. Possible triangles are: {4, 5, 6}, {3, 5, 6}, {3, 4, 6}, {3, 4, 5} The solution is… Read More »

Find min distance of two list

Given two sorted list, find the min distance of any 2 elements in 2 lists. For example, {1, 10, 20} and {5, 15, 21} min=21-20=1 {1, 10} and {15, 21} min=15-10=5 Solution 1 is to use merge sort. Compare abs(arr1[i]-arr[2] ) and min. Solution 2 is that it doesn’t compare in each merge. It only… Read More »

Sum of Set

Given a integer array, and a number n. Return true if n can be consisted by a subset of array. For example, arr[]={3, 2, 3, 5}, n=11, return true; arr[]={3, 2, 3, 5}, n=12, return false This problem can be solved by HashSet. Loop element i in arr[]. For each loop, get the value of… Read More »

Worm walking on a line

Given a array consisted of only 0 or 1, and a number N. We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed. For example, 100100111000, n=2, the best flip is 100111111000, return 6 10001101101, n=2, the best flip… Read More »

Open Closed range in a sorted array

1. Find leftOpen For a sorted array 1, 2, 3, 4, 4, 4, 5, 5, 6. And given 4. Find the left-most position, where 4>=arr[pos]. The answer of position is 3 2. Find leftClose For a sorted array 1, 2, 3, 4, 4, 4, 5, 5, 6. And given 4. Find the left-most position, where 4>arr[pos]. The answer of… Read More »

Max Gap between consecutive numbers

Source: http://www.careercup.com/question?id=14764703 Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)? For example, we have a unsorted array 9 19 13 12 33 41 22 the sorted version is 9 12 13 19 22 33 41 the output of the algorithm should be… Read More »