You are given an integer array

*nums*and you have to return a new*counts*array. The*counts*array has the property where`counts[i]`

is the number of smaller elements to the right of `nums[i]`

.
Example:

Givennums= [5, 2, 6, 1] To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Return the array

`[2, 1, 1, 0]`

.**Understand the problem:**

https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst

Every node will maintain a val sum recording the total of number on it's left bottom side, dupcounts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:

```
1(0, 1)
\
6(3, 1)
/
2(0, 2)
\
3(0, 1)
```

When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right. for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4

if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5

Code (Java):

Code (Java):

public class Solution { public List<Integer> countSmaller(int[] nums) { Integer[] result = new Integer[nums.length]; BSTNode root = null; for (int i = nums.length - 1; i >= 0; i--) { root = insert(root, nums[i], i, result, 0); } return Arrays.asList(result); } private BSTNode insert(BSTNode root, int num, int i, Integer[] result, int preSum) { if (root == null) { root = new BSTNode(num, 0); result[i] = preSum; return root; } else if (root.val == num) { root.dup++; result[i] = preSum + root.numOfLeftNodes; return root; } else if (root.val > num) { root.numOfLeftNodes++; root.left = insert(root.left, num, i, result, preSum); } else { root.right = insert(root.right, num, i, result, preSum + root.numOfLeftNodes + root.dup); } return root; } class BSTNode { int val; int dup = 1; int numOfLeftNodes; BSTNode left, right; BSTNode(int val, int numOfLeftNodes) { this.val = val; this.numOfLeftNodes = numOfLeftNodes; } } }

This comment has been removed by the author.

ReplyDeleteHere is my solution in Swift.

ReplyDeleteTime complexity:

n * Log(n)

For each element (N elements) in the array we should find the index in sorted array with binary search it takes in the worst case Log (n) time.

func counterSamller(numbers: [Int]) -> [Int] {

var result = [Int]()

var sorted = [Int](count: numbers.count, repeatedValue: Int.max)

for i in (0.. Int {

var left = 0

var right = sorted.count - 1

while left <= right {

var mid = (left + right) / 2

if sorted[mid] == val {

while mid - 1 >= 0 && sorted[mid - 1] == val {

mid--

}

return mid

} else if sorted[mid] < val {

left = mid + 1

} else {

right = mid - 1

}

}

return left

}