Variable Sized Arrays in C++ | HackerRank Solution

Hello, Coderz, today we are going to solve Variable Sized HackerRank Solution in C++.

Task

Consider an n-element array, a, where each index i in the array contains a reference to an array of k_i integers (where the value of varies from array to array). See the Explanation section below for a diagram.

Given a, you must answer q queries. Each query is in the format i j, where i denotes an index in array a and j denotes an index in the array located at a[i]. For each query, find and print the value of element j in the array at location a[i] on a new line.

Input Format

The first line contains two space-separated integers denoting the respective values of n (the number of variable-length arrays) and q (the number of queries).

Each line i of the n subsequent lines contains a space-separated sequence in the format k a[i]₀ a[i]₁ … a[i]_k-1 describing the k-element array located at a[i].

Each of the q subsequent lines contains two space-separated integers describing the respective values of i (an index in array a) and j (an index in the array referenced by a[i]) for a query.

Constraints

• 1 <= n <= 10⁵
• 1 <= q <= 10⁵
• 1 <= k <= 3 . 10⁵
• n <= Σk <= 3 . 10⁵
• 0 <= i < n
• 0 <= j < k
• All indices in this challenge are zero-based.
• All the given numbers are non negative and are not greater than 10⁶.

Output Format

For each pair of i and j values (i.e., for each query), print a single integer that denotes the element located at index j of the array referenced by a[i]. There should be a total of q lines of output.

Sample Input

2 2
3 1 5 4
5 1 2 8 9 3
0 1
1 3

Sample Output

5
9

Explanation

The diagram below depicts our assembled Sample Input:

We perform the following q=2 queries:

1.  Find the array located at index i = 0 , which corresponds to a[i] = [1,5,4]. We must print the value at index j=1 of this array which, as you can see, is 5.
2. Find the array located at index i=1 , which corresponds to a[i] = [1,2,8,9,3]. We must print the value at index j=3 of this array which, as you can see, is 9.

Solution – Variable Sized Arrays Hackerrank Solution in C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // get length of array 'a' and number of queries
    int n, q;
    cin >> n >> q;

    // create vector of vectors
    vector<vector<int>> a(n);

    // fill each 2D vector i with k_i values
    for (int i = 0; i < n; i++) {
        // get the length k of the vector at a[i]
        int k;
        cin >> k;

        // fill the vector with k values
        a[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> a[i][j];
        }
    }

    // run queries on a
    for (int q_num = 0; q_num < q; q_num++) {
        // get i, j as the 'query' to get a value from a
        int i, j;
        cin >> i >> j;
        cout << a[i][j] << endl;
    }

    return 0;
}

Disclaimer: The above problem (Variable Sized Arrays) is generated by Hacker Rank but the Solution is provided by CodingBroz.

Broz Who Code

CodingBroz