# Count of Smaller Number I && II

Count of Smaller Number I

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.

Example

For array `[1,2,7,8,5]`, and queries `[1,8,5]`, return `[0,4,2]`

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

1. Just loop
2. Sort and binary search
3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

```public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
//Version 1. sort + binary search
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number before itself>
ArrayList<Integer> result = new ArrayList<>();
if (A == null || queries == null) {
return result;
}
if (A.length == 0) {
for (int i = 0; i < queries.length; i++) {
}
return result;
}
Arrays.sort(A);
for (int i = 0; i < queries.length; i++) {
int target = queries[i];
//find the last element A[i]<target, i+1 is the number
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] < target) {
} else if (A[start] < target) {
} else {
}
}
return result;
}```

Count of Smaller Number II

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element`Ai` in the array, count the number of element before this element `Ai` is smaller than it and return count number array.

Example

For array `[1,2,7,8,5]`, return `[0,1,2,3,2]`

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

```public class SegmentTreeNode {
int start, end;
int count;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.count = 0;
}
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
ArrayList<Integer> result = new ArrayList<>();
if (A == null || A.length == 0) {
return result;
}
SegmentTreeNode node = buildSegmentTree(0, 10000);
for (int i = 0; i < A.length; i++) {
if (A[i] == 0) {
} else {
}
update(node, A[i]);
}
return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start < end) {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(start, mid);
node.right = buildSegmentTree(mid + 1, end);
node.count = node.left.count + node.right.count;
}
return node;
}

public int query(SegmentTreeNode node, int start, int end) {
if (node.start == start && node.end == end) {
return node.count;
}
int leftCount = 0, rightCount = 0;
int mid = node.start + (node.end - node.start) / 2;
if (start <= mid) {
if (end <= mid) {
leftCount = query(node.left, start, end);
} else {
leftCount = query(node.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightCount = query(node.right, start, end);
} else {
rightCount = query(node.right, mid + 1, end);
}
}
return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
if (node.start == index && node.end == index) {
node.count = node.count + 1;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (node.start <= index && index <= mid) {
update(node.left, index);
} else if (mid < index && index <= node.end) {
update(node.right, index);
}
node.count = node.left.count + node.right.count; //or node.count = node.count+1;
}
}```
Share

# Interval Sum I && II

Interval Sum I

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers `[start, end]`. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array `[1,2,7,8,5]`, and queries `[(0,4),(1,2),(2,4)]`, return `[23,9,20]`

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for each query

Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)

```public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
//Version 1. prefix sum,
//Version 2. Segment tree: check Interval Sum II
ArrayList<Long> result = new ArrayList<>();
if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
return result;
}
Long[] prefixSum = new Long[A.length];
Long sum = 0L;
for (int i = 0; i < A.length; i++) {
sum += A[i];
prefixSum[i] = sum;
}
for (Interval interval : queries) {
if (interval.start == 0) {
} else {
}

}
return result;
}```

Interval Sum II

Given an integer array in the construct method, implement two methods `query(start, end)` and`modify(index, value)`:

• For query(start, end), return the sum from index start to index end in the given array.
• For modify(index, value), modify the number in the given index to value

Example

Given array A = `[1,2,7,8,5]`.

• `query(0, 2)`, return `10`.
• `modify(0, 4)`, change A[0] from 1 to 4.
• `query(0, 1)`, return `6`.
• `modify(2, 1)`, change A[2] from 7 to 1.
• `query(2, 4)`, return `14`.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for `query` and `modify`.

Solution: Segment Tree.

```public class Solution {
SegmentTreeNode root;

public class SegmentTreeNode {
int start, end;
int sum;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
public Solution(int[] A) {
if (A == null || A.length == 0) {
return;
}
this.root = buildSegmentTree(A, 0, A.length - 1);
}

private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
node.sum = A[start];
} else {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(A, start, mid);
node.right = buildSegmentTree(A, mid + 1, end);
node.sum = node.left.sum + node.right.sum;
}
return node;
}

public long query(int start, int end) {
if (start < this.root.start || end > this.root.end) {
return -1;
}
return query(this.root, start, end);
}

private long query(SegmentTreeNode root, int start, int end) {
if (root.start == start && root.end == end) {
return root.sum;
}
int mid = root.start + (root.end - root.start) / 2;
long leftSum = 0L, rightSum = 0L;
if (start <= mid) {
if (end <= mid) {
leftSum = query(root.left, start, end);
} else {
leftSum = query(root.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightSum = query(root.right, start, end);
} else {
rightSum = query(root.right, mid + 1, end);
}
}
return leftSum + rightSum;
}

public void modify(int index, int value) {
modify(this.root, index, value);
}

public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == index && root.end == index) {
root.sum = value;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.sum = root.left.sum + root.right.sum;
}
}
}```

# Maximum Product Subarray

#### Maximum Product Subarray

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

Example

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

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

```public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxProduct = Integer.MIN_VALUE;
int preMax = 1;
int preMin = 1;
for (int i = 0; i < nums.length; i++) {
int max, min;
if (nums[i] >= 0) {
max = Math.max(preMax * nums[i], nums[i]);
min = Math.min(preMin * nums[i], nums[i]);
} else {
max = Math.max(preMin * nums[i], nums[i]);
min = Math.min(preMax * nums[i], nums[i]);
}
maxProduct = Math.max(maxProduct, max);
preMax = max;
preMin = min;
}
return maxProduct;
}```

# Segment Tree

Segment Tree(线段树)

1. 二叉树
2. 线段树的每个节点表示的是一段区间和最大值（或最小值）
3. 节点的左子树 = 父亲区间分裂后的左区间

1. 查询的区间 和 线段树节点表示的区间 相等 -》直接返回节点的最大值
2. 查询的区间 被 线段树节点表示的区间 包含 -》递归向下搜索左右子树
3. 查询的区间 和 线段树节点表示的区间 不相交 -》停止搜索子树
4. 查询的区间 和 线段树节点表示的区间 相交不相等 -》分裂查找左右子树 eg.max[1,3] = max([1,1], [2,3])

1. 自上而下递归分裂
2. 自下而上回溯更新

#### Segment Tree Query

For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute `max` to denote the maximum number in the interval of the array (index from start to end).

Design a `query` method with three parameters `root`, `start` and `end`, find the maximum number in the interval [start, end] by the given root of segment tree.

Example

For array `[1, 4, 2, 3]`, the corresponding Segment Tree is:

```<code>                  [0, 3, max=4]
/             \
[0,1,max=4]        [2,3,max=3]
/         \        /         \
[0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
</code>```

query(root, 1, 1), return `4`

query(root, 1, 2), return `4`

query(root, 2, 3), return `3`

query(root, 0, 2), return `4`

Note

It is much easier to understand this problem if you finished Segment Tree Build first.

```public int query(SegmentTreeNode root, int start, int end) {
if (root == null) {
return -1;
}
if (root.start == start && root.end == end) {
return root.max;
}
int mid = root.start + (root.end - root.start) / 2;
int leftMax = Integer.MIN_VALUE;
int rightMax = Integer.MIN_VALUE;
if (start <= mid) {
if (end <= mid) {
leftMax = query(root.left, start, end);
} else {
leftMax = query(root.left, start, mid);
}
}
if (end > mid) {
if (start >= mid) {
rightMax = query(root.right, start, end);
} else {
rightMax = query(root.right, mid + 1, end);
}
}
return Math.max(leftMax, rightMax);
}```

Segment Tree Query II

For an array, we can build a `SegmentTree` for it, each node stores an extra attribute`count` to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)

Design a `query` method with three parameters `root`, `start` and `end`, find the number of elements in the in array’s interval [start, end] by the given root of value SegmentTree.

Example

For array `[0, 2, 3]`, the corresponding value Segment Tree is:

```<code>                     [0, 3, count=3]
/             \
[0,1,count=1]             [2,3,count=2]
/         \               /            \
[0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
</code>```

`query(1, 1)`, return `0`

`query(1, 2)`, return `1`

`query(2, 3)`, return `2`

`query(0, 2)`, return `2`

Note

It is much easier to understand this problem if you finished Segment Tree Build and Segment Tree Query first.

```public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) {
return 0;
}
if (root.start == start && root.end == end) {
return root.count;
}
int mid = root.start + (root.end - root.start) / 2;
int leftCount = 0, rightCount = 0;
if (start <= mid) {
if (end <= mid) {
leftCount = query(root.left, Math.max(start, root.start), end);
} else {
leftCount = query(root.left, Math.max(start, root.start), mid);
}
}
if (end >= mid) {
if (start >= mid + 1) {
rightCount = query(root.right, start, Math.min(end, root.end));
} else {
rightCount = query(root.right, mid + 1, Math.min(end, root.end));
}
}
return leftCount + rightCount;
}```

#### Segment Tree Modify

For a `Maximum Segment Tree`, which each node has an extra value `max` to store the maximum value in this node’s interval.

Implement a `modify` function with three parameter `root`, `index` and `value` to change the node’s value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.

Example

For segment tree:

```<code>                      [1, 4, max=3]
/                \
[1, 2, max=2]                [3, 4, max=3]
/              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]
</code>```

if call `modify(root, 2, 4)`, we can get:

```<code>                      [1, 4, max=4]
/                \
[1, 2, max=4]                [3, 4, max=3]
/              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]
</code>```

or call `modify(root, 4, 0)`, we can get:

```<code>                      [1, 4, max=2]
/                \
[1, 2, max=2]                [3, 4, max=0]
/              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]
</code>```
Note

We suggest you finish problem Segment Tree Build and Segment Tree Query first.

Challenge

Do it in `O(h)` time, h is the height of the segment tree.

# Trailing Zeros

Trailing Zeros

Write an algorithm which computes the number of trailing zeros in n factorial.

Example

11! = 39916800, so the out should be 2

Challenge

O(log N) time

Solution: 只要找里面有多少个5, 乘出来就会有多少个0，因为2永远是够的

# of 5：n/5+n/25+n/(5^3)…..

```public long trailingZeros(long n) {
long base = 5;//important to use long type
long count = 0;
while (n >= base) {
count += n / base;
base *= 5;
}
return count;
}```

# Maximum Subarray I & II & III

Maximum Subarray I

Given an array of integers, find a contiguous subarray which has the largest sum.

Example

For example, given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number

Challenge

Can you do it in time complexity O(n)?

Solution: O(n) time O(1) space. one pass. Prefix Sum

```public int maxSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int maxSum = Integer.MIN_VALUE;
int sum = 0;
int minSum = 0;
for (Integer num : nums) {
sum += num;
maxSum = Math.max(maxSum, sum - minSum);
minSum = Math.min(minSum, sum);
}
return maxSum;
}```

# Minimum Subarray

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Example

For [1, -1, -2, 1], return -3

Note

The subarray should contain at least one integer.

Solution: O(n) time O(1) space. one pass. Prefix Sum

```public int minSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int minSum = Integer.MAX_VALUE;
int sum = 0;
int maxSum = 0;
for (Integer num : nums) {
sum += num;
minSum = Math.min(minSum, sum - maxSum);
maxSum = Math.max(maxSum, sum);
}
return minSum;
}```

# Majority Number I & II & III

Majority Number I （找一个出现次数>1/2的数）

Given an array of integers, the majority number is the number that occurs `more than half` of the size of the array. Find it.

Example

Given `[1, 1, 1, 1, 2, 2, 2]`, return `1`

Challenge

O(n) time and O(1) extra space

Solution: 用的抵消的思想，如果两个数不一样大，就相互抵消，一样大就保留， 用count计数

```public int majorityNumber(ArrayList<Integer> nums) {
int candidate = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (count == 0) {
candidate = nums.get(i);
count++;
} else {
if (candidate == nums.get(i)) {
count++;
} else {
count--;
}
}
}
return candidate;
}```

Majority Number II （找一个出现次数>1/3的数）

Given an array of integers, the majority number is the number that occurs `more than 1/3` of the size of the array.

Find it.

Example

Given `[1, 2, 1, 2, 1, 3, 3]`, return `1`.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

Solution: 策略和I一样，只是现在有两个candidate,

```public int majorityNumber(ArrayList<Integer> nums) {
int candidate1 = -1;
int candidate2 = -1;
int count1 = 0;
int count2 = 0;
for (Integer num : nums) {
if (candidate1 == num) {
count1 ++;
} else if (candidate2 == num) {
count2 ++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
if (count1 == 0) {
return candidate2;
}
if (count2 == 0) {
return candidate1;
}
count1 = 0;
count2 = 0;
for (Integer num : nums) {
if (num == candidate1) {
count1++;
}
if (num == candidate2) {
count2++;
}
}
return count1 > count2 ? candidate1 : candidate2;
}```

Majority Number III （找一个出现次数>1/k的数）

Given an array of integers and a number k, the majority number is the number that occurs `more than 1/k` of the size of the array.

Find it.

Example

Given `[3,1,2,3,2,3,3,4,4,4]` and `k=3`, return `3`.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(k) extra space

Solution: Similar approach as I & II

```public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> majorityCounts = new HashMap<>();
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
majorityCounts.put(num, majorityCounts.get(num) + 1);
} else {
if (majorityCounts.size() < k - 1) {
majorityCounts.put(num, 1);
} else {
List<Integer> toBeRemoved = new ArrayList<>();
for (Integer key : majorityCounts.keySet()) {
if (majorityCounts.get(key) > 1) {
majorityCounts.put(key, majorityCounts.get(key) - 1);
} else {
}
}
//important here: can not remove the element while iterating the set
//which will cause ConcurrentModificationException
for (Integer key : toBeRemoved) {
majorityCounts.remove(key);
}
}
}
}
Set<Integer> results = majorityCounts.keySet();
int maxCount = 0;
int candidate = 0;
for (Integer key : majorityCounts.keySet()) {
majorityCounts.put(key, 0);
}
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
int count = majorityCounts.get(num) + 1;
majorityCounts.put(num, count);
if (count > maxCount) {
maxCount = count;
candidate = num;
}
}
}
return candidate;
}```

# Max Tree

#### Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

• The root is the maximum number in the array
• The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given `[2, 5, 6, 0, 3, 1]`, the max tree constructed by this array is:

```<code>    6
/ \
5   3
/   / \
2   0   1
</code>```
Challenge

O(n) time and memory.

Solution: 用stack来维护在每个数出现前比它大得数。

When new node comes in, if it is larger than the peek, stack.pop() and at the same time append it as the new node’s left child. until the stack peek is larger than the new node or the stack is empty, at this time, the peek.right = new node. then we push new node into the stack. if the stack is empty when the new node is pushed, the new node is the temporary root.

```public TreeNode maxTree(int[] A) {
if (A == null || A.length == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode root = null;
for (int i = 0; i < A.length; i++) {
TreeNode curr = new TreeNode(A[i]);
while (!stack.isEmpty() && A[i] >= stack.peek().val) {
TreeNode tmp = stack.pop();
tmp.right = curr.left;
curr.left = tmp;
}
if (!stack.isEmpty()) {
stack.peek().right = curr;
} else {
root = curr;
}
stack.push(curr);
}
return root;
}```

# Largest Rectangle in Histogram

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example

Given height = `[2,1,5,6,2,3]`,
return `10`.

Solution: max(the area of rectangle which height[i] is the shortest bar)

leftBound[i]: index of the first element less than height[i] starting from the left +1

rightBound[i]: index of the first element less than height[i] starting from the right -1

result = max(height[i]*(rightBound[i]-leftBound[i]))

O(n) time.

Solution 1. Straightforward Version

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] leftBound = new int[height.length];
int[] rightBound = new int[height.length];
Stack<Integer> minStack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
leftBound[i] = 0;
} else {
leftBound[i] = minStack.peek() + 1;
}
minStack.push(i);
}
minStack = new Stack<>();
for (int i = height.length - 1; i >= 0; i--) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
rightBound[i] = height.length - 1;
} else {
rightBound[i] = minStack.peek() - 1;
}
minStack.push(i);
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
int area = height[i] * (rightBound[i] - leftBound[i] + 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}```

Solution 2. Fancy Version, One pass

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> minStack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= height.length; i++) {
int curr = (i == height.length) ? -1 : height[i];
while (!minStack.isEmpty() && curr <= height[minStack.peek()]) {
int tmp = minStack.pop();
int left = minStack.isEmpty() ? 0 : minStack.peek() + 1;
int area = (i - left) * height[tmp];
maxArea = Math.max(area, maxArea);
}
minStack.push(i);
}
return maxArea;
}```