wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Array Problem (count a[i]<=a[j], i>=j)
        
(Message started by: witee on Jul 18^th, 2010, 5:00am)

Title: Array Problem (count a[i]<=a[j], i>=j)
Post by witee on Jul 18^th, 2010, 5:00am

Given an array for each index (j) find the number of numbers less then and equal to a[j] from j to n..
complexity < 0(n*n)

Title: Re: Array Problem
Post by towr on Jul 18^th, 2010, 6:29am

[hide]Use a binary search tree, and for each node keep track of the number of nodes in its subtree.[/hide]

Title: Re: Array Problem
Post by witee on Jul 18^th, 2010, 11:43am

check for this input 2 3 1 this method will give 0 for 2nd array element while the ans. is 1 .correct me if i m wrong!!!!

Title: Re: Array Problem
Post by towr on Jul 18^th, 2010, 12:11pm

Perhaps I should add you ought to start at the back of the array. It's the natural place to start, since you want information about elements following a given one, and you'll only have such information if you looked there first.
So first you have an empty BST, which contains 0 elements less or equal to 1. Then you insert the 1, at which point it contain one element less than or equal to 3. Then you insert the 3, and it contains one element less than or equal to 2.
So you get 1,1,0 (in order of input, in reverse order of finding them).

Title: Re: Array Problem
Post by witee on Jul 18^th, 2010, 12:23pm

The worst case complexity is 0(n*n) when elements r sorted in decreasing order..correct me if i m wrong!

Title: Re: Array Problem
Post by towr on Jul 18^th, 2010, 1:19pm

Insertion into a bst is an O(log n) operation is you implement the BST properly (with automatic balancing). So it's O(n log n) in total.

Title: Re: Array Problem
Post by birbal on Jul 24^th, 2010, 9:06am

on 07/18/10 at 12:23:49, witee wrote:

The worst case complexity is 0(n*n) when elements r sorted in decreasing order..correct me if i m wrong!

Well not always. After each insert, you can check and balance the tree.
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree