Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You asked for <code>O(n log n)</code>, here I give you technically an <code>O(n)</code> solution.</p> <p>As hinted by @SayonjiNakate, the solution using segment tree (I used Fenwick tree in my implementation) runs in <code>O(n log M)</code> time, where <code>M</code> is the maximum possible value in the array. Assuming <code>M</code> is constant (hey it's bounded by the size of int!), the algorithm runs in <code>O(n)</code>. Sorry if you feel that I'm cheating in reporting the complexity, but hey, technically that's true! =D</p> <p>Firstly, note that the problem "number of smaller elements on the left" is equivalent to the problem "number of greater elements on the right" by reversing and negating the array. So, in my explanation below I only describe the "number of smaller elements on the left", which I call "lesser_left_count".</p> <p><strong>Algorithm</strong> for lesser_left_count:</p> <p>The idea is to be able to find the total of numbers smaller than a specific number.</p> <ol> <li><p>Define an array <code>tree</code> with size upto <code>MAX_VALUE</code>, which will store the value <code>1</code> for seen numbers and <code>0</code> otherwise.</p></li> <li><p>Then as we traverse the array, when we see a number <code>num</code>, just assign the value <code>1</code> to <code>tree[num]</code> (<em>update operation</em>). Then lesser_left_count for a number <code>num</code> is the sum from <code>1</code> to <code>num-1</code> (<em>sum operation</em>) so far, since all smaller numbers to the left of current position would have been set to <code>1</code>.</p></li> </ol> <p>Simple right? If we use <a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=binaryIndexedTrees" rel="nofollow">Fenwick tree</a>, the update and sum operation can be done each in <code>O(log M)</code> time, where <code>M</code> is the maximum possible value in the array. Since we are iterating over the array, total time is <code>O(n log M)</code>, or simply <code>O(n)</code> if we regard <code>M</code> as a constant (in my code I set it to <code>2^20-1 = 1048575</code>, so it's <code>O(20n)</code>, which is <code>O(n)</code>)</p> <p>The only disadvantage of the naive solution is that it uses a lot of memory as <code>M</code> gets bigger (I set <code>M=2^20-1</code> in my code, which take around 4MB of memory). This can be improved by mapping distinct integers in the array into smaller integers (in a way that preserve the order). The mapping can be done in simply <code>O(n log n)</code> by sorting the array (ok, that makes the complexity <code>O(n log n)</code>, but as we know that <code>n &lt; M</code>, you can regard that as <code>O(n)</code>). So the number <code>M</code> can be reinterpreted as <em>"number of distinct elements in the array"</em>.</p> <p>So the memory wouldn't be any problem anymore, because if after this improvement you indeed need huge memory, that means there are <em>that many</em> distinct numbers in your array, and the time complexity of <code>O(n)</code> will already be too high to be calculated in normal machine anyway.</p> <p>For the sake of simplicity, I didn't include that improvement in my code.</p> <p>Oh, and since Fenwick tree only works for positive numbers, I converted the numbers in the array to be minimum 1. Note that this doesn't change the result.</p> <p>Python code:</p> <pre><code>MAX_VALUE = 2**20-1 f_arr = [0]*MAX_VALUE def reset(): global f_arr, MAX_VALUE f_arr[:] = [0]*MAX_VALUE def update(idx,val): global f_arr while idx&lt;MAX_VALUE: f_arr[idx]+=val idx += (idx &amp; -idx) def cnt_sum(idx): global f_arr result = 0 while idx &gt; 0: result += f_arr[idx] idx -= (idx &amp; -idx) return result def count_left_less(arr): reset() result = [0]*len(arr) for idx,num in enumerate(arr): cnt_prev = cnt_sum(num-1) if cnt_sum(num) == cnt_prev: # If we haven't seen num before update(num,1) result[idx] = cnt_prev return result def count_left_right(arr): arr = [x for x in arr] min_num = min(arr) if min_num&lt;=0: # Got nonpositive numbers! arr = [min_num+1+x for x in arr] # Convert to minimum 1 left = count_left_less(arr) arr.reverse() # Reverse for greater_right_count max_num = max(arr) arr = [max_num+1-x for x in arr] # Negate the entries, keep minimum 1 right = count_left_less(arr) right.reverse() # Reverse the result, to align with original array return (left, right) def main(): arr = [1,1,3,2,4,5,6] (left, right) = count_left_right(arr) print 'Array: ' + str(arr) print 'Lesser left count: ' + str(left) print 'Greater right cnt: ' + str(right) if __name__=='__main__': main() </code></pre> <p>will produce:</p> <pre> Original array: [1, 1, 3, 2, 4, 5, 6] Lesser left count: [0, 0, 1, 1, 3, 4, 5] Greater right cnt: [5, 5, 3, 3, 2, 1, 0] </pre> <p>or if you want Java code:</p> <pre><code>import java.util.Arrays; class Main{ static int MAX_VALUE = 1048575; static int[] fArr = new int[MAX_VALUE]; public static void main(String[] args){ int[] arr = new int[]{1,1,3,2,4,5,6}; System.out.println("Original array: "+toString(arr)); int[][] leftRight = lesserLeftRight(arr); System.out.println("Lesser left count: "+toString(leftRight[0])); System.out.println("Greater right cnt: "+toString(leftRight[1])); } public static String toString(int[] arr){ String result = "["; for(int num: arr){ if(result.length()!=1){ result+=", "; } result+=num; } result+="]"; return result; } public static void reset(){ Arrays.fill(fArr,0); } public static void update(int idx, int val){ while(idx &lt; MAX_VALUE){ fArr[idx]+=val; idx += (idx &amp; -idx); } } public static int cntSum(int idx){ int result = 0; while(idx &gt; 0){ result += fArr[idx]; idx -= (idx &amp; -idx); } return result; } public static int[] lesserLeftCount(int[] arr){ reset(); int[] result = new int[arr.length]; for(int i=0; i&lt;arr.length; i++){ result[i] = cntSum(arr[i]-1); if(cntSum(arr[i])==result[i]) update(arr[i],1); } return result; } public static int[][] lesserLeftRight(int[] arr){ int[] left = new int[arr.length]; int min = Integer.MAX_VALUE; for(int i=0; i&lt;arr.length; i++){ left[i] = arr[i]; if(min&gt;arr[i]) min=arr[i]; } for(int i=0; i&lt;arr.length; i++) left[i]+=min+1; left = lesserLeftCount(left); int[] right = new int[arr.length]; int max = Integer.MIN_VALUE; for(int i=0; i&lt;arr.length; i++){ right[i] = arr[arr.length-1-i]; if(max&lt;right[i]) max=right[i]; } for(int i=0; i&lt;arr.length; i++) right[i] = max+1-right[i]; right = lesserLeftCount(right); int[] rightFinal = new int[right.length]; for(int i=0; i&lt;right.length; i++) rightFinal[i] = right[right.length-1-i]; return new int[][]{left, rightFinal}; } } </code></pre> <p>which will produce same result.</p>
    singulars
    1. This table or related slice is empty.
    1. POCompute smaller and bigger values for an array position
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USjusthalf
    1. USjusthalf
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POCompute smaller and bigger values for an array position
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COthank you very much, it solved my problem indeed.
      singulars
      1. PO
      1. USMoises B.
    2. COThis is a great solution, though you can't argue that `M` is a constant if you also assume that `n < M` -- or rather, if you do then `n` is constant too and your algorithm becomes `O(1)`. So I'd either argue that `M` is constant and we're planning for huge `n`, or express the complexity in `n` and `M`. Either way, nicely done.
      singulars
      1. PO
      1. USErik P.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload