Printing subarrays ⚡

Question

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)?

Answer 1

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.