Achieve a task using a single loop instead of 2 c++`

Question

This is a task specific code for which I want to know if there's a better way of doing it. Thus, people who love logic and coding, please help me out.

This is the question :

Let A be an array of n positive integers. All the elements are distinct. If A[i] > A[j] and i < j then the pair (i, j) is called a special pair of A. Given n find the number of special pairs of A.

Its pretty simple and straight. Here's the following solution I implemented. The logic part.

         for(int j=0;j<nos.size();j++)
            {
                    for(int k=j+1;k<nos.size();k++)//always maintain condition that i<j and simply compare the numbers.
                    {
                            if(nos[j] > nos[k])
                            {
                                    spc++;//compute special pair.
                            }
                    }
            }

Every nos[i] contains the array for which special pair is to be computed. Is there a way to do this with using a single loop? Or any other logic that can be time saving and is faster. Thanks in advance I seek to learn more from this.

And can you please tell me how I can determine which code is faster without having to execute the code. Your inputs are really welcome.

The main question is to compute the no.of special pairs. Thus, just the increment of spc.

Answer 1

I think @syam is correct that this can be done in O(N log N) time (and O(N) extra space).

You'd do this with a balanced binary tree where each node has not only a value, but also a count of the number of descendants in its left sub-tree.

To count the special pairs, you'd walk the array from the end to the beginning, and insert each item in the tree. As you insert the item in the tree, you find the number of items in its left sub-tree -- those are the items that are less than it, but were to its right in the array (i.e., each one represents a special pair). Since we only descend through ~log(N) nodes to insert an item, the time to compute the number of items to the left is also O(log N). We also have to update the counts of items to the left approximately log(N)/2 times (again, logarithmic complexity).

That gives O(N log N) time.

Edit for more details: The balancing of the tree is fairly conventional (e.g., AVL- or RB-tree) with the addition of adjusting the count of items to the left as it does rotations to restore balance.

As you insert each item, you descend through the tree to the point where it's going to be inserted. At the root node, you simply record the count of items in the left sub-tree. Then let's say you new item is greater than that, so you descend to the right. As you do this, you're doing two things: recording your current position, so you know the location of this node relative to the nodes already inserted, and updating the counts in the tree so you'll have an accurate count for later insertions.

So, let's work through a small sample. For the sake of argument, let's assume our input is [6, 12, 5, 9, 7]. So, our first insertion is 7, which becomes the root of our tree, with no descendants, and (obviously) 0 to its left.

Then we insert 9 to its right. Since it's to the right, we don't need to adjust any counts during the descent -- we just increment our count of items to the left. That's it, so we know for 9 we have one special pair ([9,7], though we haven't kept track of that).

Then we insert 5. This is to the left of 7, so as we descend from 7, we increment its count of items to the left to 1. We insert 5, with no items to the left, so it gets a count of 0, and no special pairs.

Then we insert 12. When we hit the root node (7) it has a count of 1 item to the left. We're descending to the right, so we increment again for the root node itself. Then we descend to the right again from 9, so we add one more ( +0 from its left sub-tree), so 12 has three special pairs.

Then we insert 6. We descend left from 7, so we don't add anything from it. We descend right from 5, so we add 1 (again, +0 from its left sub-tree). So it has one special pair.

Even when you need to generate all the special pairs (not just count them) you can expect the tree to improve speed in the average case (i.e., pretty much anything except sorted in descending order). To generate all the special pairs, we insert each item in the tree as before, then traverse through the tree to the left of that item. Where the naive algorithm traversed (and compare to) all the elements to the right in the array to find those that would be special pairs, this only has to traverse the tree to find those that actually are special pairs.

This does have one side effect though: it generates the pairs in a different order. Instead of each pair being generated in the order it occurred in the array, the pairs will be generated in descending order by the second element. For example, given an input like [4,1,2,3], the naive algorithm would produce [[4,1], [4,2], [4,3]], but this will produce `[[4,3], [4,2], [4,1]].

Answer 2

I don't think you can improve your algorithm. In my opinion it shows O(n²) complexity. You can proove that by counting the number of inner loops your program has to perform for an array of length n. The first loop will have n-1 iterations, the second loop n-2, the third n-3 and so on. Summing that up using the formula for the sum of the first n integers (only backwards this time and not from 1 to n but from 2 to n-1):

(n-1)+(n-2)+(n-3)+...3+2 = n*(n-1)/2 - 1. You dont have to loop over the last remaining element, since there is no other element left to compare. Actually this is the only improvement I see for your algorithm ;-):

for(int j=0;j<nos.size();j++)

to

for(int j=0;j<nos.size()-1;j++)

Summing up for large n the expression n*(n-1)/2 - 1 behaves like n² and that's where I believe the O(n²) comes from. Please correct me if I'm wrong.

Answer 3

You mean can you do better than quadratic runtime? No. To see this, consider the decreasing se­quence A = (N, N - 1, ..., 2, 1). For this sequence, all the pairs (i, j) with i < j are special, and there are O(N^2) such pairs. Since you must output every special pair, you need quadratic time to do so.