# Monthly Archives: June 2016

## Valid Perfect Square

leetcode 367. Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as `sqrt`.

Example 1:

```Input: 16
Returns: True
```

Example 2:

```Input: 14
Returns: False```

Solution. An awesome solution is from here: n is perfect square if n = 1 + 3 + 5 + …. Below is the code:

```public static boolean isPerfectSquare(int num) {
int delta = 1;
while (num > 0) {
num -= delta;
delta += 2;
}
return num == 0;
}```

## A decent gcd code

This is a very decent code to calculate gcd. I found this when I was doing the water and jug problem.

```public static int gcd(int x, int y) {
while (y != 0) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}```

## 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]) and sum[right] – sum[left] <= k. See below description: So, when we have sumRight and k, we try to find the sumLeft, which is equal to or greater than sumRight – k. In order to achieve this, we can use TreeSet.

Below is the code for this problem. A important part of this code is that we should add 0 into TreeSet, or it won’t pass case like ({1, 0}, 2) or ({2}, 2)

```public static int maxSubArrayLessThanK(int []arr, int k) {
int ans = Integer.MIN_VALUE, sumRight = 0;
TreeSet<Integer> ts = new TreeSet<>();
ts.add(0);  // this is important. without this, won't pass {1, 0}
for (int i : arr) {
sumRight += i;
Integer sumLeft = ts.ceiling(sumRight - k);
if (sumLeft != null) {
ans = Math.max(ans, sumRight - sumLeft);
}
}
return ans;
}```

Finally, let’s jump to the leetcode problem: Max Sum of Rectangle No Larger Than K. Since we went through this problem and previous max subarray problem, this rectangle no larger than K problem can be solved naturally:

```public static int maxSubArrayRectangleLessThanK(int [][]matrix, int k) {
int ans = Integer.MIN_VALUE, row = matrix.length, col = matrix.length;
for (int left = 0; left < col; left++) {
int[] helper = new int[row];
for (int right = left; right < col; right++) {
for (int i = 0; i < helper.length; i++) {
helper[i] += matrix[i][right];
}
int sumRight = 0;
TreeSet<Integer> ts = new TreeSet<>();
ts.add(0);  // this is important. without this, won't pass {1, 0}
for (int i : helper) {
sumRight += i;
Integer sumLeft = ts.ceiling(sumRight - k);
if (sumLeft != null) {
ans = Math.max(ans, sumRight - sumLeft);
}
}   // for
}   // for
}
return ans;
}```

Check my code on github: MaxSubarrayLessThanKMaxSubarrayRectangleLessThanK

## Max subarray, and Max sub rectangle

Max subarray is from here: https://en.wikipedia.org/wiki/Maximum_subarray_problem

Finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

This is a classical problem which can be solved by Kadane algorithm. Below is the java solution:

```public static int maxSubArray(int []arr) {
int max = arr, currMax = arr;
for (int i = 1; i < arr.length; i++) {
currMax = Math.max(currMax + arr[i], arr[i]);  // compare the history continuous sum and current value
max = Math.max(max, currMax);  // update the max
}
return max;
}```

However, this problem can be developed to 2d problem: Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29. (http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/)

A great solution can be found in Tushar’s tutorial. In the solution, the outer loop iterates the column(left, right). Then it calculates the 1-dimension helper array which is sum of all elements from column left to column right. Then run the Kadane’s algorithm on this helper array.

Below is my java code:

```public static int maxSubArrayRectangle(int [][]arr) {
int row = arr.length, col = arr.length, max = arr;
int[] helperArr = null;
for (int left = 0; left < col; left++) {
helperArr = new int[col];
for (int right = left; right < col; right++) {
// update helper
for (int i = 0; i < row; i++) {
helperArr[i] += arr[i][right];
}
// Kodane algorithm to find the top and bottom for max continuous sequence
int helperMax = helperArr, currHelperMax = helperArr;
for (int i = 0; i < row; i++) {
currHelperMax = Math.max(currHelperMax + helperArr[i], helperArr[i]);
helperMax = Math.max(helperMax, currHelperMax);
}
max = Math.max(currHelperMax, max);
}
}
return max;
}```

Check my code on github: Max subarrayMax sub rectangle

## Counting bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For `num = 5` you should return `[0,1,1,2,1,2]`.

Solution. A great solution is from here. It uses the formula: f(x) = f(x / 2) + x % 2

0        1        2        3        4        5        6        7        8

0        1       10      11       110     101    110   111      1000

0        1        1        2        2        2        2        3        1

We know 7 move right 1 bit, then it can reach 3. So we can calculate 7 by 3. The only difference is that we need to know the new bit is 0 or 1.

Check my code on github.

## Intersection of Two Linked Lists

leetcode 160.

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

```A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3```

Solution. I got the cool but trick solution from here. O(n) time, O(1) space.

Define a and b Node to travel through 2 lists. The point is to let both a and b travel complete 2 lists.

a travels: a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1

b travels: b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1

If order to let a, b travel, below code is presented:

```def getIntersectionNode(self, headA, headB):
while a != b:
a = a.next if a != None else headB
b = b.next if b != None else headA
return a```

Check my code on github: link

## Count Numbers with Unique Digits

leetcode 357.

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding `[11,22,33,44,55,66,77,88,99]`)

Solution. This problem is a combination problem.

When n == 0, return 1. I got this answer from the test case.

When n == 1, _ can put 10 digit in the only position. [0, … , 10]. Answer is 10.

When n == 2, _ _ first digit has 9 choices [1, …, 9], second one has 9 choices excluding the already chosen one. So totally 9 * 9 = 81. answer should be 10 + 81 = 91

When n == 3, _ _ _ total choice is 9 * 9 * 8 = 684. answer is 10 + 81 + 648 = 739

When n == 4, _ _ _ _ total choice is 9 * 9 * 8 * 7.

When n == 10, _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

When n == 11,  _ _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 = 0

Others are always 0.

Below is my code:

```public static int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
int ans = 10, base = 9;
for (int i = 2; i <= n && i <= 10; i++) {
base = base * (9 - i + 2);
ans += base;
}
return ans;
}```

Here is my code on github: link

## Data Stream as Disjoint Intervals

From https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

```[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]```

This is a good one. The solution from here. Use TreeMap and put start as key, (start, end) as value in TreeMap. Basically, ; there will be 3 conditions when adding a new value: add 4 to (5, 6), (8, 9); add 6 to (5, 5); add 4 to (5, 5):   Besides, there are 2 exceptions: add 6 to (5, 7); add 6 to (6, 6):  Check my code on github: link

## Lambda study summary

Below code is a basic way to self-define a lambda. Basically, it requires:
1. a interface with only one function
2. a method which has the interface as parameter, and in the method, it will call the function in that interface implementation.

```public static void simpleWay() {
Math add = new Math() {
@Override
public int operate(int a, int b) {
return a + b;
}
};
Math sub = new Math() {
public int operate(int a, int b) {
return a - b;
}
};
System.out.println(MathOperation(1, 2, sub));
}

public static void lambdaWay() {
Math add = (int a, int b) -> a + b;
Math sub = (int a, int b) -> a - b;
System.out.println(MathOperation(1, 2, sub));
}

/**
* MathOperation and Math are the core for defining lambda expression.
* An operation interface and a function which uses interface.do() to return something.
*/

public static int MathOperation (int a, int b, Math math) {
return math.operate(a, b);
}

interface Math {
public int operate(int a, int b);
}```

After that, below are some useful lambda expression in Java 8.

```public static void forEachCase() {
List<Integer> list = new ArrayList<>();
list.forEach(i -> System.out.println(i));
}

public static void removeIf() {
List<Integer> list = new ArrayList<>();
list.removeIf(i -> i == 2); // if only has one element, doesn't has to be (Integer i) -> i == 2 ....  Could be i -> i == 2
System.out.println(list);
}

public static void replaceAll() {
List<Integer> list = new ArrayList<>();
list.replaceAll(i -> -i);
System.out.println(list);
}

public static void sortCase1() {
List<Integer> list = new ArrayList<>();
Collections.sort(list, (i1, i2) -> i1 - i2);
System.out.println(list);
}

public static void sortCase2() {
List<Integer> list = new ArrayList<>();
list.sort((i1, i2) -> i1 - i2);
System.out.println(list);
}

public static void threadCase() {
Runnable r1 = () -> {
try {
for (int i = 0; i < 10; i++) {
System.out.println(i);