1
\$\begingroup\$

I was trying to to print all subarrays of an array in quadratic time. Here is my code:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    int N;
    std::cin >> N; //size of array

    for (int i = 0; i < N; i++) {
        int x;
        std::cin >> x;
        v.push_back(x);
    }

    int j = v.size() - 1;
    std::vector<int> l;

    do {
        l.push_back(v[j]);

        if (j == 0) {
            int k = l.size() - 1;

            do {
                std::cout << l[k] << " ";

                if (k == 0) {
                    l.pop_back();

                    if (l.empty()) {
                        break;
                    }

                    std::cout << '\n';
                    k = l.size() - 1;
                } else {
                    k--;
                }
            } while (k >= 0);

            v.pop_back();

            if (v.empty()) {
                std::cout << '\n';
                break;
            }

            std::cout << '\n';
            j = v.size() - 1;
        } else {
            j--;
        }
    } while (j >= 0);
}

What is the time complexity of this code? Is it more efficient than O(n^3)?

\$\endgroup\$
9
  • \$\begingroup\$ For what you need v if you already have a? \$\endgroup\$
    – convert
    Jun 9 at 20:14
  • \$\begingroup\$ This method of printing subarrays is little faster than the general method to print subarrays using three nested loops. \$\endgroup\$ Jun 10 at 8:32
  • \$\begingroup\$ I was asking about why you need 2 vectors v and a? They are both exactly the same, or have I mised some? \$\endgroup\$
    – convert
    Jun 10 at 10:14
  • \$\begingroup\$ I had edited my code according to your comment. Can you tell what is the time complexity of my code? \$\endgroup\$ Jun 10 at 11:34
  • \$\begingroup\$ Any restrictions on subarrays? Like contiguity? \$\endgroup\$ Jun 10 at 12:51

3 Answers 3

2
\$\begingroup\$

Your code is obfuscated

The code you have written looks very obfuscated. For example, the outer do-loop does two things: it copies elements from v to l (in reverse order), and when it finished doing that, the next iteration will start the inner loop that prints a subarray (reversing it again), and then it resets j so the outer loop will start from scratch with a v that has one less element. The loop indices also go backwards. All variable names are only a single letter long. This makes the code very hard to read, not just for others but also for yourself in the future.

Use variable names that clearly indicate what the variable is used for. They don't have to be overly long; concise names are preferred over verbose ones. Only use one-letter names for very common things, like i for a loop index, x/y/z for coordinates, or n for a count of things.

Rewrite the loops so it becomes much more clear what is going on. Make use of the fact that you can copy whole std::vectors in one go, and create helper functions where appropriate. So for example:

static void print(const std::vector<int>& array) {
    for (auto& item: array) {
        std::cout << item << ' ';
    }

    std::cout << '\n';
}
...
std::vector<int> array;
...
while (!array.empty()) {
    auto subarray = array;

    while (!subarray.empty()) {
        print(subarray);
        subarray.erase(subarray.begin()); // pop_front()
    }

    array.pop_back();
}

Efficiency

Is it more efficient than O(n^3)?

Not unless it has a bug. If you print out all the possible contiguous subarrays of a given array of length \$N\$, you are printing in the order of \$O(N^3)\$ elements. The question is then: is it less efficient than \$O(N^3)\$? This means looking carefully at hidden costs from manipulating the std::vectors, as not all operations on them are \$O(1)\$. There is in fact a \$O(N \log N)\$ cost to filling the vector l the first time, as it needs to reallocate memory multiple times and copy elements. You can avoid that by calling l.reserve(N) before entering the outer do-loop, but overall this does not influence the total complexity.

Note that while your code might have the best possible time complexity, that does not mean it is the most efficient way to do this. In particular, a lot of time is spent copying v into l. You don't need to do that; you can write your code such that you only need the original array a, and just print its elements in the right order.

\$\endgroup\$
1
  • \$\begingroup\$ DO NOT edit your code after posting. Read the rules! \$\endgroup\$
    – Aganju
    Jun 11 at 5:25
0
\$\begingroup\$

There is also an recursive solution:

#include <iostream>
#include <vector>

using namespace std;

void printSubArray(const vector<int>& input, int currIndex){
    string result("");
    int length=input.size();
    for (int i = currIndex; i <length ; i++){
        result+=to_string(input[i]) + " ";
        cout<<result<< '\n';
    }
    if(currIndex<length-1){
        printSubArray(input, currIndex+1);
    }
}

int main()
{
   vector<int> v;
    int N;
    cin >> N; 

    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    printSubArray(v, 0);

    return 0;
}

This can be also turned to a solution with 2 loops, so the complexity should be O(n^2). Also since every array of size n has (n^2+n)/2 subarrays this is the number of arrays to be printed and the complexity is O(n^2).

\$\endgroup\$
7
  • \$\begingroup\$ The number of loops does not necessarily correspond with the complexity. Regardless, It can't be \$O(n^2)\$ since you need to print \$O(n^3)\$ elements to cover all possible contiguous subarrays. \$\endgroup\$
    – G. Sliepen
    Jun 11 at 21:32
  • \$\begingroup\$ @G. Sliepen No 2 loops, if you want can rewrite this recursive solution to a solution with 2 loops. \$\endgroup\$
    – convert
    Jun 11 at 21:38
  • \$\begingroup\$ @G. Sliepen No this is exactly the working recursive solution, avaible on the internet, just have writen it in C++. \$\endgroup\$
    – convert
    Jun 11 at 21:42
  • \$\begingroup\$ Ah, but the string result can contain multiple numbers. Printing a string takes time that is proportional to its length, so you have to take that into account for the time complexity as well. \$\endgroup\$
    – G. Sliepen
    Jun 11 at 22:22
  • \$\begingroup\$ All possible subarrays can be printed using one loop. \$\endgroup\$ Jun 12 at 1:40
-1
\$\begingroup\$

All possible subarrays can be printed using one loop:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> array;
    int N;
    std::cin >> N; //size of array

for (int i = 0; i < N; i++) {
    int x;
    std::cin >> x;
    array.push_back(x);
}

int i = array.size() - 1;
std::vector<int> subarray=array;

    do {
        std::cout << subarray[array.size()-i-1] << " ";

        if (i == 0) {
            subarray.pop_back();

            if (subarray.empty()) {
              array.pop_back();
              subarray=array;
            }

            std::cout << '\n';
            i = subarray.size() - 1;
        } else {
            i--;
        }
    } while (i >= 0);
}
\$\endgroup\$
1
  • \$\begingroup\$ This is not a review of the code in the original question. And again, time complexity is not the same as the number of loops. By trying to cram as much as possible into one loop, you have created hard to read code. \$\endgroup\$
    – G. Sliepen
    Jun 13 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.