LeetCode – Remove Duplicates from Sorted Array
1. Problem
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.
For example, given input array A = [1,1,2], your function should return length = 2, and A is now [1,2].
2. Idea
In the presence of the limit not to allocate extra space for another array, we have two alternatives to remove duplicates: one is to actually remove duplicates by moving the following numbers forward, and the other one is to maintain an index of the last “effective” number and copy each different number to that index. With an easy observation, it turns out that the first solution yields O(n2) time complexity, while the second one does O(n) . Therefore, I took and implemented the second one and passed LeetCode OJ.
3. Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

package me.darrensunny.leetcode;
/**
* LeetCode – Remove Duplicates from Sorted Array
* Created by Darren on 1447.
*/
public class RemoveDuplicatesFromSortedArray {
public int removeDuplicates(int[] A) {
int n = A.length;
if (n < 2)
return n;
int current = 0; // Index of the last “effective” number
for (int i = 1; i < n; i++) {
// When a different number is encountered,
// copy its value to the one at the next effective index
if (A[i] != A[i–1])
A[++current] = A[i];
}
return current+1;
}
}

4. Wrapup
No extra space is used for the above implementation. One pass of all the numbers suffices.
LeetCode – Remove Element
1. Problem
Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
2. Idea
This is a variant of LeetCode – Remove Duplicates from Sorted Array, except that in this case, the number that is the same with given value is removed. Anyway, the same idea applies.
3. Implementation
public int removeElement(int[] A, int elem) {
int count = A.length;
int result = 0;
for (int i=0; i<count; i++) {
if (A[i] != elem) {
A[result++] = A[i];
}
}
return result;
}
LeetCode – Divide Two Integers
1. Problem
Divide two integers without using multiplication, division and mod operator.
2. Idea
Consider a simple case where both the dividend and divisor are positive. Without using multiplication, division and mod operator, we could subtract the divisor from the dividend until the remainder is smaller than the divisor. Then the number of subtraction (denoted by q ) is the quotient between the dividend and the divisor. However, this solution is rather slow, with a time complexity of O(q) . As it turns out, an implementation of it would exceed the time limit when the dividend is large (say 231 ) and the divisor is small (say 2).
However, based on this intuitive idea, we can propose an improved solution to reduce the time complexity and thus to pass the test. The insight is that instead of subtracting the divisor each time, we could have subtracted multiples of the divisor. And though direct multiplication is forbidden, left shift operation can be used as an alternative. In other words, we first find the maximum 2power multiples (2x, 4x, 8x, etc.) of the divisor that does not exceed the dividend, subtract it from the dividend, and try a smaller 2power multiples of the divisor repeatedly until we arrive at the divisor itself. And of course, all possible cases involved in the computation, such as possibility to overflow and positive/negative numbers, need to be handled carefully.
3. Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

package me.darrensunny.leetcode;
import com.sun.org.apache.xpath.internal.operations.Div;
/**
* LeetCode – Divide Two Integers
* Created by Darren on 1447.
*/
public class DivideTwoIntegers {
// 440ms for 987 test cases
public int divide(int dividend, int divisor) {
if (divisor == 0)
return Integer.MAX_VALUE;
int quotient = 0;
// In order to make the Math.abs method work as expected, we need to consider the case
// when either number is Integer.MIN_VALUE (Math.abs(Integer.MIN_VALUE)=Integer.MIN_VALUE)
if (dividend == Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) {
return 1;
} else if (divisor == Integer.MIN_VALUE) {
return 0;
} else if (dividend == Integer.MIN_VALUE) {
quotient++;
dividend += Math.abs(divisor);
}
int posDividend = Math.abs(dividend), posDivisor = Math.abs(divisor);
// The maximum number of right shifts that can be applied to posDividend while
// Making it larger than posDivisor
int shift = 0;
while ((posDividend>>(shift+1)) >= posDivisor)
shift++;
// Subtract multiples of posDivisor from posDividend and sum up the number
// of multiples in quotient.
while (shift >= 0) {
if (posDividend >= (posDivisor << shift)) {
quotient += 1 << shift;
posDividend –= posDivisor << shift;
}
shift—;
}
// Determine whether quotient should be positive or negative
return ((dividend^divisor) >>> 31 == 0) ? quotient : –quotient;
}
}

4. Wrapup
It can be seen that the time required depends on the number of the digits in the binary representation of the quotient. That is, the time complexity isO(logq) .