4dots @4dotsleetcode - Tumblr Blog

154. Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

This is the follow-up of the previous problem. The condition is that the array contains duplicates. This condition will break some of our assumptions made in the previous solution.

The change is that when you have duplicates on the side you cannot divide the array into half to find the minimal. E.g. 3133, in this case the medium 3 equals to both first and entry entry. There is no way you can guess whether 1 is on the left side or right side.

The solution is recursively following steps:

If the array has less than 3 entries, find the minimal one using Min.

If the medium is bigger than the last entry, we are for sure that the minimal value is on the right side of the array.

If the medium is smaller than the first entry we can assure that the minimal value is on the left side of the array.

For equal cases we need to check both sides and find the minimal value.

You can find my code here.

https://gist.github.com/zyzyis/1ae909e64f3597307246

#Binary search

153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

The problem is a straightforward binary search problem.

When the array has less than 3 entries, find the minimal one using Min.

When the array has more than two entries, we start to recursively divide the array from the medium. If the medium is smaller than the first entry we know that the minimal is going to be on the left part of the array, otherwise the minimal is going to be on the right part (because the array is sorted).

You can read my code here.

https://gist.github.com/zyzyis/929a5f57f86d7d911967

#Binary search

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

So, Leetcode is back with 3 new problems, and lots of improvements on the user interface.

This problem is almost the same as the problem Maximum Subarray, instead of using Addition, it uses Multiplication. The interesting for Multiplication is that two variables A, B, A x B could be a negative number if either A or B is negative. This makes our previous solution fail because in the previous solution we are always choosing the maximum sum during scan of the array.

For example, given an array

[-4, 3, -2]

the previous approach will start with maximum product -4, and then 3 as the maximum product because -12 is smaller than 3. This leads to a failure for the next product to 24.

The solution is to keep both maximum product and minimal product, and update the maximum with the global maximum product during scanning the array. In each step A[k], we always update

Max = Math.Max(A[k], Max * A[k], Min * A[k])

Min = Math.Min(A[k], Max * A[k], Min * A[k])

In the example above we have

Max: -4, Min: -4

Max: 3, Min: -12

Max: 24, Min: -6

Here max 24 is the largest product overall.

You can find my code here.

https://gist.github.com/zyzyis/402119c424c6b7264417

#greedy

151. Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

This is for me by far the hardest problem on Leetcode.

I got the final solution from many difference pieces on the Internet. Basically the concept is to change the problem into Finding the Kth element in two sorted arrays. So when the total length is an odd number we find the (total / 2)th number, and when the total length is an even we find the (total / 2)th, and the (total / 2) + 1.

The question is then how to find the Kth number in O(log(m+n)) time?

I simplify the answers from a great post on Internet as below:

We start with K/2th element from both A and B. If A[k / 2] is smaller than B[k / 2], we can for sure know that the first K / 2 elements of A are not going to have the Kth element. The reason is that to get A[k /2] be the candidate there is at least K / 2 elements smaller than A[k / 2] in B. And it is impossible because A[k / 2] is smaller than B[k / 2].

To use this important finding, we can safely drop the first K / 2 elements of A. And this problem becomes finding the K / 2th element from the subarray of A (without the first K / 2) and B.

We do this recursively until meeting the end conditions.

The end conditions are:

When K equals 1, we pick the smallest element in both arrays.

When one of the arrays is empty we return immediately with the Kth element in the other array.

If both K/2 elements are the same we return the Kth element from either of the array (since they are the same and it means that we find the Kth element).

You can read my code here.

https://gist.github.com/zyzyis/cc869cd2f21a44642609

#hard #binarysearch #median

150. Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

The easiest way is to append B at the end of A and do a sorting afterwards. The complexity would be O((m+n)log(m + n)) and we are not using the property of both two sorted input arrays.

The other approach is by starting fill the last item in A from both the tail of each array. We have two pointers pointing to both tails and every time we pick the bigger value one and decrement the pointer to the left. Since A has extra n spaces we will never overwrite the content of A itself (The worst case is all items from B are bigger than the max value of A and just fit in the extra spaces). The time complexity would be O(m + n) and space complexity is O(1).

You can read my code here.

https://gist.github.com/zyzyis/0f13dee3867d313a5af9

#merge

149. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

It is almost the same as Maximum Depth of Binary Tree.

You can read my code here.

https://gist.github.com/zyzyis/0fc27ef1910bf984d108

#recursion

148. Palindrome Partitioning I

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return

[ ["aa","b"], ["a","a","b"] ]

First use Dynamic Programming to find out a matrix <i, j> where substring s[i, j] is a palindrome. Then use backtracking to generate all the substrings.

You can read my code here.

https://gist.github.com/zyzyis/1c958ee659e69055d6a1

#dp #backtracking

147. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

This is a bit operation trick, thinking an integer as a bit vector. For any bit value x, x ^ x = 0. It means that all the integers appears twice will turns back to zero when doing a XOR operation. And the final result is the single one.

You can read my code here.

#bit operation

146. Search For A Range

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].

Since it is a sorted array and it is required to have time complexity of O(logn) binary search would be a nobrainer to go. My approach is as following:

Do a binary search on the target, if not found return {-1, -1}, otherwise keep the position.

Do another binary search on target - 0.9, for sure it is going to find the left bound of the position.

Do the same binary search on target + 0.9, and it is going to find the right bound.

So in total it takes 3 binary searches to find the target and the time complexity is O(logn) and space complexity is O(1).

You can read my code here.

https://gist.github.com/zyzyis/95f1360f7be60b81fca1

#binary search

145. Merge K Sorted List

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

There are two ways, one is to use Merge Sorting, which results in O(knlogn) complexity. The other is to use a minimal Heap, which results in O(kn) complexity when building it (it is tighter than O(knlogn) by amortize analysis ). My solution uses minimal Heap approach thanks to the PriorityHeap data structure in Java.

You can read my code here.

https://gist.github.com/zyzyis/f661210f39c8c8574906

#heap #amortize

144. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Binary Search Tree has a property that in-order traversal generates a non-decreasing array. So the easiest solution is to do an in-order traversal and find which are the two values being swapped. Doing this we need an array of O(n).

I overcome this by using recursion. When we are in the traversal process we can maintain a variable which has the value of the previous node and when the current node is smaller than the previous one we mark it down. In the end we should have at least one pair of incorrect nodes. Swap it and return.

You can read my code here

https://gist.github.com/zyzyis/6c8a2a44707cf61cad74

PS: Recursion is not an O(1) space complexity approach. It should be O(logn) and O(n) for worst case. I found from internet that using threaded binary tree which can lead to O(1) space complexity, will updated later.

#recursion #threaded binary tree

143. Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Following up the previous problem, the biggest difference with duplication is that once we find the middle point is smaller or bigger than the left boundary we still don't know whether the left or right is sorted.

E.g.

input is [1 1 1 3 1 1 1 1 1 1 1] and the middle point is 1 in bold. Since the left boundary has the same value 1 we cannot find which part is sorted and which is not. But we know for sure the left boundary is not the target, we can just skip it and move left to its right. The worst case we need to skip half of the array for each iteration which results in time complexity O(n) (so the simplest code actually is only a for loop).

You can read my code here.

https://gist.github.com/zyzyis/b08de208fff58e59644e

#binary search

142. Search In Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

The pivot which separates the array into two different sorted arrays. My solution is as following:

Do a binary search, find the value of the middle point.

If the value of middle point is bigger than the left boundary, we know that all the left points are in sorted array. We can check whether the target is in the range of the sorted array, if so, we change the right boundary to the middle point. And the rest would be a normal binary search. If the target is not in the range of left points, we change the left boundary to the middle point and repeat the process from step 1.

If the value of middle point is smaller than the left boundary, we know that all the right points are in sorted array. Do the same as step 2 and repeat the process.

Since every iteration we cut the array into half search space the time complexity is O(logn).

You can read my code here.

https://gist.github.com/zyzyis/308d70fee6bcf714f560

#binary search

141. Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

great / \ gr eat / \ / \ g r e at / \ a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

rgeat / \ rg eat / \ / \ r g e at / \ a t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

rgtae / \ rg tae / \ / \ r g ta e / \ t a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

I find this a very interesting problem because it looks like a recursion but actually very hard to implement one if you try so. My solution uses a Dynamic Programming solution with time complexity of O(N^4), where N is the length of the string.

I maintain a 3-dimension array D[i, j, k] which is true when s1[i, i + k] and s2[j, j + k] are scramble strings. We can have

D[i, j, k] = D[i, j, z] and D[i + z, j + z, k - z] or

D[i, j + k - z, z] and D[i + z, j, k - z], where 1 < z < k

The two equations basically represents the swap of two possibilities, e.g

s1: abc

s2: cba

when we calculate D[0, 0, 3] with z = 2, we check D[0, 0, 2] (s1: ab, s2: cb) and D[2, 2, 1] (s1: c, s2: a), or D[0, 1, 2] (s1: ab, s2: ba) and D[2, 0, 1] (s1: c, s2: c).

The final result is D[0, 0, N].

You can read my code here.

https://gist.github.com/zyzyis/e1859e3e64b11b880421

#dynamic programming

140. Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16.

Return the formatted lines as:

[ "This is an", "example of text", "justification. " ]

Note: Each word is guaranteed not to exceed L in length.

It is not a hard problem but needs lots of patience to get it right. I feel it is very hard to write bug free solution in a short time if it is in an interview.

The algorithm is quite straightforward, first we calculate how many words per line by checking whether it can exceed L. Later for each line we calculate the spaces following each token. There are two cases,

The last line, which means among words there is exactly one space. And all the remaining spaces are appended at last.

Not the last line. The spaces among words are based on how even we can spread.

You can read my code here.

https://gist.github.com/zyzyis/762decef632c75ef0376

#string

139. Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Following the Word Break I problem, we use a one-dimension Dynamic Programming solution to find whether a substring [0, k] can be constructed using the string dictionary. Once we find it is true we record the position of the break point. After all the break points are recorded we use a simple backtracking to generate all the string tokens.

You can read my code here.

https://gist.github.com/zyzyis/cb8bfa895be697945ff0

#dp #backtracking

138. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

This must be a follow-up question after the previous Largest Rectangle in Histogram. Given a matrix MxN, we can calculate M histograms by piling up each lines. We call the Largest Rectangle function to get the maximum areas of each histogram and find its global maximum.

The time complexity is O(MN).

You can read my code here.

https://gist.github.com/zyzyis/015eb8aac11e10281cf1

#matrix #creative

Trending Blogs

Recently Viewed Blogs

4dots