0315. Count of Smaller Numbers After Self
https://leetcode.com/problems/count-of-smaller-numbers-after-self
Description
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 1:
**Input:** nums = [5,2,6,1]
**Output:** [2,1,1,0]
**Explanation:**
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.Example 2:
**Input:** nums = [-1]
**Output:** [0]Example 3:
**Input:** nums = [-1,-1]
**Output:** [0,0]Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
ac1: Merge sort
Amazing solution from https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/445769/merge-sort-CLEAR-simple-EXPLANATION-with-EXAMPLES-O(n-lg-n). So easy to understand that not like a hard problem.
// Wrapper class for each and every value of the input array,
// to store the original index position of each value, before we merge sort the array
private class ArrayValWithOrigIdx {
int val;
int originalIdx;
public ArrayValWithOrigIdx(int val, int originalIdx) {
this.val = val;
this.originalIdx = originalIdx;
}
}
public List<Integer> countSmaller(int[] nums) {
if (nums == null || nums.length == 0) return new LinkedList<Integer>();
int n = nums.length;
int[] result = new int[n];
ArrayValWithOrigIdx[] newNums = new ArrayValWithOrigIdx[n];
for (int i = 0; i < n; ++i) newNums[i] = new ArrayValWithOrigIdx(nums[i], i);
mergeSortAndCount(newNums, 0, n - 1, result);
// notice we don't care about the sorted array after merge sort finishes.
// we only wanted the result counts, generated by running merge sort
List<Integer> resultList = new LinkedList<Integer>();
for (int i : result) resultList.add(i);
return resultList;
}
private void mergeSortAndCount(ArrayValWithOrigIdx[] nums, int start, int end, int[] result) {
if (start >= end) return;
int mid = (start + end) / 2;
mergeSortAndCount(nums, start, mid, result);
mergeSortAndCount(nums, mid + 1, end, result);
// left subarray start...mid
// right subarray mid+1...end
int leftPos = start;
int rightPos = mid + 1;
LinkedList<ArrayValWithOrigIdx> merged = new LinkedList<ArrayValWithOrigIdx>();
int numElemsRightArrayLessThanLeftArray = 0;
while (leftPos < mid + 1 && rightPos <= end) {
if (nums[leftPos].val > nums[rightPos].val) {
// this code block is exactly what the problem is asking us for:
// a number from the right side of the original input array, is smaller
// than a number from the left side
//
// within this code block,
// nums[rightPos] is smaller than the start of the left sub-array.
// Since left sub-array is already sorted,
// nums[rightPos] must also be smaller than the entire remaining left sub-array
++numElemsRightArrayLessThanLeftArray;
// continue with normal merge sort, merge
merged.add(nums[rightPos]);
++rightPos;
} else {
// a number from left side of array, is smaller than a number from
// right side of array
result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;
// Continue with normal merge sort
merged.add(nums[leftPos]);
++leftPos;
}
}
// part of normal merge sort, if either left or right sub-array is not empty,
// move all remaining elements into merged result
while (leftPos < mid + 1) {
result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;
merged.add(nums[leftPos]);
++leftPos;
}
while (rightPos <= end) {
merged.add(nums[rightPos]);
++rightPos;
}
// part of normal merge sort
// copy back merged result into array
int pos = start;
for (ArrayValWithOrigIdx m : merged) {
nums[pos] = m;
++pos;
}
}ac2: BST
This is not optimal, the worse case is still O(n^2), which is same as brute force.
class Solution {
public List<Integer> countSmaller(int[] nums) {
LinkedList<Integer> res = new LinkedList<Integer>();
// edge cases
if (nums == null || nums.length == 0) return res;
// iterate right to left, build tree, get result
Node root = null;
for (int i = nums.length - 1; i >= 0; i--) {
root = getLessInsert(root, nums[i], 0, res);
}
Collections.reverse(res);
return res;
}
private Node getLessInsert(Node root, int val, int prevSum, List<Integer> res) {
if (root == null) {
root = new Node(val);
res.add(prevSum);
} else if (val == root.val) {
root.count++;
res.add(root.leftSum + prevSum);
} else if (val < root.val) {
root.leftSum++;
root.left = getLessInsert(root.left, val, prevSum, res);
} else { // val > root.val
root.right = getLessInsert(root.right, val, prevSum + root.count + root.leftSum, res);
}
return root;
}
class Node {
int val, leftSum, count;
Node left, right;
public Node(int val) {
this.val = val;
leftSum = 0;
count = 1;
}
}
}
/*
BS
BST
BIT
merge sort
*/ac3: BIT
Binary Indexed Tree, O(nlogn) time gurantee.
class Solution {
public List<Integer> countSmaller(int[] nums) {
LinkedList<Integer> res = new LinkedList<Integer>();
// edge cases
if (nums == null || nums.length == 0) return res;
int[] nums2 = nums.clone();
Arrays.sort(nums2);
Map<Integer, Integer> rankMap = new HashMap<Integer, Integer>();
for (int i = 0; i < nums2.length; i++) {
if (!rankMap.containsKey(nums2[i])) {
rankMap.put(nums2[i], i+1);
}
}
// BIT
int[] tree = new int[nums.length + 1];
for (int i = nums.length - 1; i >= 0; i--) {
int rank = rankMap.get(nums[i]);
res.add(sum(rank-1, tree));
update(rank, tree);
}
Collections.reverse(res);
return res;
}
private int sum(int n, int[] tree) {
int res = 0;
while (n > 0) {
res += tree[n];
n -= n & (-n);
}
return res;
}
private void update(int n, int[] tree) {
while (n < tree.length) {
tree[n]++;
n += n & (-n);
}
}
}
/*
From right to left, for a num, I need to know how many smaller numbers we had met. So we use BIT to keep track of it.
Smaller number means: num with lower rank. How to update BIT? For each num, we update BIT by doing rank+1.
*/Last updated