Leetcode 493 - reverse pairs -

Leetcode 493 - Reverse pairs

Hard:

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2
Example2:

Input: [2,4,3,5,1]
Output: 3



keywords:

Give an array nums, integer, 
define important reverse pair if i < j and number[i] > 2 * nums[j]; in other words, left side element is two times more than right side element

ask: return number of important reverse pairs in the given array

[1, 3, 2, 3, 1]

1, <- 
3 <- 1, 2 * 1 < 3, pair [1, 4]
3 , pair[3, 1]

return 2 
-> reverse the array 
[1, 3, 2, 3, 1] 
brute force, 1 -> 2 -> 3, 3 _> total 2
3 -> 6 -> ...nothing
2 -> 4 -> nothing
O(n^2)

O(n) 

space to save the result 
1, exisiting numbers visited, any number < 1 / 2,  <= 0
-> sorted order-> logn 
nlogn 

reverse the array
iterate the array
  visit = numbers[i]
  
data structure -> sorted data structure 
  3, look for <= 1
  
  visited element sorted [1] - binary search 


[1, 3, 2, 3, 1] -> [[1, 3, 2, 3, 1]]

public static int FindNumberOfImportantPair(int[] numbers)
{
   if(numbers == null)
     return 0; 
     
   var length = number.Length; 
   
   Array.Reverse(numbers); // smaller -> 
   
   var binarySearchTree = new SortedSet();
   
   int count = 0; 
   for(int i = 0; i < length; i++)  // O(n)
   {
      var current = numbers[i]; // 5, <= 2, [0] + [1] + [2]
      
      count += query(binarySearchTree, current);       // logn
      
      addToBST(current, binarySearchTree); // 1 -> number[1]++;
   }
   
   return count; 
}


work on visited elements 
  countNumber[0]++;
  countNumber[1]++;  sumNumber[1] =countNumber[0] + countNumber[1]; // O(1)

BST: https://leetcode.com/problems/reverse-pairs/discuss/ 
LT Reverse Pairs: 493


https://codereview.stackexchange.com/questions/158242/hackerrank-kindergarten-adventures

polynomial algebra 
           [0]

     [1]           [2]
  [0-1]    [2-3]  []  []

[] [] [] []   [] [] [] []
0 1   2   3    4  5 6   7
[0, 3] true->

complete binary search express 

8 elments -> extra space to speed up search 
1 + 2 + 4 + 8 = 15 double space ->