We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Thanks for the awesome problem HR! I foolishly thought this was going to be as easy as the first couple and quickly got stuck (trying to use a brute force insertion sort method, with O(n^2) complexity. Though frustrating at the time, good idea to include test case file #7 to throw off unbalanced implementations. To give some hints to others following my path: 1. To solve this problem, take each element e in the array and add up all previous numbers in the array greater than this number. 2. The aggregate of all these sums is your output. To achieve this result, you'll need to research some computing concepts. In order, I recommend: - Binary Search Trees (http://en.wikipedia.org/wiki/Binary_search_tree) - AVL trees, aka, balanced binary search trees (http://www.geeksforgeeks.org/avl-tree-set-1-insertion/) - Order statistic trees, specifically the rank method (http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree) Good Luck! PS Mods, if this is too many hints, let me know and I can take it down.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Insertion Sort Advanced Analysis
You are viewing a single comment's thread. Return to all comments →
Thanks for the awesome problem HR! I foolishly thought this was going to be as easy as the first couple and quickly got stuck (trying to use a brute force insertion sort method, with O(n^2) complexity. Though frustrating at the time, good idea to include test case file #7 to throw off unbalanced implementations. To give some hints to others following my path: 1. To solve this problem, take each element e in the array and add up all previous numbers in the array greater than this number. 2. The aggregate of all these sums is your output. To achieve this result, you'll need to research some computing concepts. In order, I recommend: - Binary Search Trees (http://en.wikipedia.org/wiki/Binary_search_tree) - AVL trees, aka, balanced binary search trees (http://www.geeksforgeeks.org/avl-tree-set-1-insertion/) - Order statistic trees, specifically the rank method (http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree) Good Luck! PS Mods, if this is too many hints, let me know and I can take it down.