Leetcode 315 Solution

This article provides solution to leetcode question 315 (count-of-smaller-numbers-after-self)

https://leetcode.com/problems/count-of-smaller-numbers-after-self

Solution

struct Node { int m_val; int smaller; int count = 1; Node* left; Node* right;
Node(int val) { m_val = val; smaller = 0; count = 1; left = NULL; right = NULL; } };
class BST { Node* m_root;
Node* insert(Node* node, int val) { if (node == NULL) return new Node(val); else if (val == node->m_val) { node->count++; return node; } else if (val < node->m_val) { node->smaller++; node->left = insert(node->left, val); return node; } else if (val > node->m_val) { node->right = insert(node->right, val); return node; }
return NULL; }
int findsmaller(Node* node, int val) { if (node == NULL) return 0; else if (node->m_val == val) return node->smaller; else if (node->m_val > val) return findsmaller(node->left, val); else if (node->m_val < val) return node->smaller + node->count + findsmaller(node->right, val);
return 0; }
public: BST() { m_root = NULL; }
void insert(int val) { m_root = insert(m_root, val); }
int findsmaller(int val) { return findsmaller(m_root, val); } };
class Solution { public: vector<int> countSmaller(vector<int>& nums) { BST bst; vector<int> res(nums.size());
for (int i = nums.size() - 1; i >= 0; i--) { res[i] = bst.findsmaller(nums[i]); bst.insert(nums[i]); }
return res; } };