For the Hard Algorithm round of a Software Dev interview, I was recently asked this question. I was able to do this using Brute Force/Recursion, not sure about the intended approach, any help regarding this?

Given an array of permutation of n numbers, calculate the noumber of tuples (i,j,k,l,m) such that i<j<k<l<m and a[i]<a[k]<a[j]<a[m]<a[l].

My approach -> Try out each of all the tuples of (i,j,k,l,m) from given array using recursion and taking into account only those which satisfy the condition, Something like N Choose 5 , As This has exponential time complexity , I wanted to make it cubic or maybe quadratic

CodePudding user response：

I would use something like Quadtrees heavily. A quadtree allows you to put a bunch of points in 2d, and then do searches over regions efficiently. Either to find the points, or to just count them. (Store the count of points in each node, and then counting gets faster because you can stop when you have a square entirely in the desired region.)

One useful quadtree is to view the permutation as a series of n points (i, a[i]). We can use this to look for all cases where i is in one range and a[i] is in another. Call that tree perm.

A second useful quadtree is to map all inversions i < j and a[j] < a[i] to the point (i, a[j]). Call that tree invert.

And now your search looks like this:

search invert to find all inversions (j, k):
    x = count i < j with a[i] < a[k] (search perm)
    y = count inversions (l, m) with k < l and a[j] < a[m] (search invert)
    add x*y to total

I believe that populating perm will take time O(n log(n)), populating invert will take O(n^2 log(n)), and each search to get a count should be something like O((log(n))^2). (Not sure about that one.) Since there are O(n^2) inversions, the total performance should be something like O((n log(n))^2).