# Monthly Archives: August 2016

## Wiggle Subsequence

leetcode 376.

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, `[1,7,4,9,2,5]` is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, `[1,4,7,2,5]` and `[1,7,4,5,5]` are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

```Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2
```

Can you do it in O(n) time?

Solution. An amazing solution is from here. The idea is that when there is a asc, then asc = desc + 1. When there is a desc, then desc = asc + 1.

```public int wiggleMaxLength(int[] nums) {
if (nums.length == 0) {
return 0;
}
int asc = 1, desc = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {    // update increasing by decreasing
asc = desc + 1;
}
else if (nums[i] < nums[i - 1]) {   // update decreasing by increasing
desc = asc + 1;
}
}
return Math.max(asc, desc);
}```

Check my code on github.

## Multiply String

leetcode 43.

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

Solution. An awesome solution is from this post.

1. length of new string is len1 + len2.
2. iterates each element in num1 and num2 from lower to higher position.
3. num1[i] * num2[j] will be placed at [i + j], [i + j + 1] position. ```public String multiply(String num1, String num2) {
int[] digit = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
for (int j = num2.length() - 1; j >= 0; j--) {
int posHigh = i + j, posLow = i + j + 1;
int curr = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + digit[posLow];
digit[posLow]  = curr % 10;
digit[posHigh] += curr / 10;
}
}
StringBuffer sb = new StringBuffer();
for (int i : digit) {
if (!(sb.length() == 0 && i == 0)) {
sb.append(i);
}
}
return sb.length() == 0 ? "0" : sb.toString();
}```

Check my code on github.

## Insert Delete GetRandom O(1) – Duplicates allowed

leetcode 381.

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. `insert(val)`: Inserts an item val to the collection.
2. `remove(val)`: Removes an item val from the collection if present.
3. `getRandom`: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Solution. Same as previous problem. To solve the duplicate one, all we need to change is that we choose to use HashSet as the value for loc. When we do remove and update, we 1. remove HashSet 2. remove ArrayList 3. Update HashSet 4.Update ArrayList. ```public class RandomizedCollection {

Map<Integer, Set<Integer>> loc;
List<Integer> list;
Random random = new Random();

/** Initialize your data structure here. */
public RandomizedCollection() {
loc = new HashMap<>();
list = new ArrayList<>();
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
Set<Integer> set = loc.getOrDefault(val, new HashSet<>());
loc.put(val, set);
return true;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!loc.containsKey(val)) {
return false;
}
Set<Integer> set = loc.get(val);
int pos = set.iterator().next();
set.remove(pos);    // remove loc
if (set.isEmpty()) {
loc.remove(val);
}
int lastEle = list.remove(list.size() - 1); // remove list
if (pos != list.size()) {   // update list and loc
list.set(pos, lastEle);     // update loc
Set<Integer> lastEleSet = loc.get(lastEle);
lastEleSet.remove(list.size()); // update list
}
return true;
}

/** Get a random element from the collection. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}

}```

Check my code on github.

## Insert Delete GetRandom O(1)

leetcode 380.

Design a data structure that supports all following operations in average O(1) time.

1. `insert(val)`: Inserts an item val to the set if not already present.
2. `remove(val)`: Removes an item val from the set if present.
3. `getRandom`: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Solution. To solve this problem, we need to use an ArrayList to maintain all the elements, and a HashMap to maintain the position of each element.

When getting the random, just get a random in ArrayList.
When removing, we delete in HashMap. If element is not in the last, we need to move the last element to the position of deleting element, and update the HashMap.  ```public class RandomizedSet {

Map<Integer, Integer> loc;
List<Integer> list;
Random random = new Random();

/** Initialize your data structure here. */
public RandomizedSet() {
loc = new HashMap<>();
list = new ArrayList<>();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (loc.containsKey(val)) {
return false;
}
loc.put(val, list.size());
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!loc.containsKey(val)) {
return false;
}
int pos = loc.remove(val);
int lastEle = list.remove(list.size() - 1);
if (pos != list.size()) {
list.set(pos, lastEle);
loc.put(lastEle, pos);
}
return true;
}

/** Get a random element from the set. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}

}```

Check my code on github.

## 3 Sum

leetcode 15.

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

```For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]```

Solution. When the array doesn’t has duplicate, it is a classical 3Sum problem, the code is like below

```public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
left++;
right--;
}
else if (sum < 0) {
right--;
}
else {
left++;
}
}
}
return list;
}```

If it has duplicate, we need to skip the duplicate by several rules:
1. When iterating i, if nums[i] has same value as the previous one, nums[i] == nums[i – 1]. We need to skip
2. After we found a new pair at nums[i]nums[left] and nums[right], we need to move left forward until a different value; move right backward until a different value.

```public List<List<Integer>> threeSumWithDuplicate(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
else if (sum < 0) {
right--;
}
else {
left++;
}
}
}
return list;
}```

Check my code on github.

## Longest Substring Without Repeating Characters

leetcode 3

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given `"abcabcbb"`, the answer is `"abc"`, which the length is 3.

Given `"bbbbb"`, the answer is `"b"`, with the length of 1.

Given `"pwwkew"`, the answer is `"wke"`, with the length of 3. Note that the answer must be a substring, `"pwke"` is a subsequence and not a substring.

Solution. An awesome solution is from here. It has two pointers, left and right. s[left, right] has no duplicate.

Iterate right, if s[right] is not in HashSet, then put it in, and update ans = max(ans, right – left).

If s[right] is already in HashSet, we need to loop from left and remove s[left], until there is no s[right] in HashSet.

If the string is [a b c d e f g h i e j k l], then the process is like: ```public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0, ans = 0;
while (right < s.length()) {
if (set.contains(s.charAt(right))) {    // has duplicate, move left until there is no duplicate between [left, right]
set.remove(s.charAt(left++));
}
else {
set.add(s.charAt(right++)); // has no duplicate between [left, right], move right
ans = Math.max(ans, right - left);
}
}
return ans;
}```

Check my code on github.

## Min Stack

leetcode 155.

There are many ways to solve the min stack problem. However, there is one solution which only requiring O(1) extra space.

The idea is that when pushinng, store the offset of the current min value. When pop or getTop, use the offset and min to get the top or next min.

If the [3, 4, 2, 1] enters stack sequentially, the stack looks like this: ```public class MinStack {

long min;
Stack<Long> stack;

public MinStack() {
stack = new Stack<>();
}

public void push(int x) {
if (stack.size() == 0) {
min = x;
stack.push(0l);
}
else {
stack.push(x - min);
min = Math.min(min, x);
}
}

public void pop() {
long pop = stack.pop();
if (pop < 0) {
min = min - pop;
}
}

public int top() {
long top = stack.peek();
if (top < 0) {
return (int)min;
}
return (int)(top + min);
}

public int getMin() {
return (int)min;
}

}```

Check my code on github.

## Search in Rotated Sorted Array I & II

leetcode 33, 81

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.

What if duplicates are allowed?

Solution. I referred this nice solution. Compared to without duplicate, the version for with duplicate has a part of code to judge if nums[left] == nums[mid] == nums[rigt]. If so, then left++, right–.

One more thing we need to pay attention is that when we check the first type of shape, we need to check use >= for nums[mid] >= nums[left] instead of nums[mid] > nums[left].

```public static boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return true;
}
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
}
else if (nums[mid] >= nums[left]) { // left side is longer
if (target >= nums[left] && target < nums[mid]) {   // to left
right = mid - 1;
}
else {
left = mid + 1;
}
}
else {  // right side is longer
if (nums[mid] < target && target <= nums[right]) {  // to right
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return false;
}```

Check my code on github i, ii.

## Partition List

leetcode 86.

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given `1->4->3->2->5->2` and x = 3,
return `1->2->2->4->3->5`.

Solution. This problem is a partition problem without knowing the pivot. If it is array, it is this problem.  I firstly use similar way to partition array, the code is a bit over head.

Then I checked this post, it provides a easy implementation. Basically, maintain two lists, less and great, put the element which is less than x to less list, put element which is greater than or equal to x to great list. Isn’t smart?

```public static ListNode partition(ListNode head, int x) {
ListNode less = new ListNode(-1), great = new ListNode(-1), currLess = less, currGreat = great;
currLess = currLess.next;
}
else {
currGreat = currGreat.next;
}
}
currLess.next = great.next;
currGreat.next = null;
return currLess.next;
}```

Check my code on github.

## Scramble String

leetcode 87.

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.

Solution. This is a interesting problem. The idea is to compare isScramble(S1[0, …, i], S2[0, …, i]) and isScsramble(S1[i + 1, …, len – 1]), S2[i + 1, …, len – 1]), or isScramebl(S1[0, …, i], S2[len – i, len – i + 1, …, len]) and isScramble(S1[i + 1, i + 2, …, len – 1), S2[0, 1, …, len – i]).

For this case

S1 = X0 X1 X2 X3 X4 X5 X6
S2 = Y0 Y1 Y2 Y3 Y4 Y5 Y6

We check isScramble(X0X1X2, Y0Y1Y2) and isScramble(X3X4X5X6, Y3Y4Y5Y6) Or check isScamble(X0X1X2, Y4Y5Y6) and isScramble(X3X4X5X6, Y0Y1Y2Y3) ```public static boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
int[] letters = new int;
for (int i = 0; i < s1.length(); i++) { // this check to avoid enter useless loop.
letters[s1.charAt(i) - 'a']++;
letters[s2.charAt(i) - 'a']--;
}
for (int count : letters) {
if (count != 0) {
return false;
}
}
for (int i = 1; i < s1.length(); i++) {
if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
return true;
}
if (isScramble(s1.substring(0, i), s2.substring(s1.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s1.length() - i))) {
return true;
}
}
return false;
}```

Check my code on github.