Machine Learning, AI and Programming

Tag: Binary Search Tree

Leetcode : Reverse Pairs

Problem Statement Solution: The brute force approach is to consider all pairs (i, j) such that i < j and check whether they satisfy the condition that nums[i] > 2*nums[j]. The time complexity for this approach is definitely O(N2) where N is the number of elements in the array 'nums'. We can improve this time complexity by reducing the number of comparisons required for each element. For e.g. if we […]

Continue Reading →

LeetCode : Count of Range Sum

Problem Statement Solution : This one looks like a very simple problem at first glance but I found it to be quite tricky during implementation. The straightforward solution is to pre-compute the prefix sums S(i), i.e. the sum of all integers from 0 to i-th index for all possible i, and then compute all possible range sums S(i, j), which is the sum of all integers from index i to […]

Continue Reading →

LeetCode : Recover Binary Search Tree

Problem Statement Solution : One approach that uses O(n) extra space, is to store for each node N, the pointer to the nodes with minimum and maximum values in the sub-tree rooted at N. Let's denote the minimum node rooted at N by N.min and the maximum  node by N.max. Then for a sub-tree rooted at N, the sub-tree has a "defect", if : N.val < N.left.max.val and/or N.val > N.right.min.val […]

Continue Reading →