HackerRank – Dynamic Array Solution in JavaScript – O(n) Time

Dynamic Array is a coding challenge with easy difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(n) space complexity.

Problem Statement

Personal Note : The original problem statement is quite confusing as it is not clear on what we should return, so I made some slight changes to the steps to make it clearer.

  • Declare a 2-dimensional array, arr, of n empty arrays. All arrays are zero indexed.
  • Declare an integer, lastAnswer, and initialize it to 0.
  • Declare an answers array.
  • Parse through each query. The format of each query will be [type, x, y]. There are 2 types of queries, given as an array of strings for you to parse, treat them according to their type:
    1. Query: 1 x y
      1. Let idx = ( (x ^ lastAnswer) % n ).
      2. Append the integer y to arr[idx].
    2. Query: 2 x y
      1. Let idx = ( (x ^ lastAnswer) % n ).
      2. Assign the value arr[idx][y % size(arr[idx])] to lastAnswer.
      3. Store the new value of lastAnswer to answers array.
  • Return answers array.

Note: ^ is the bitwise XOR operation. % is the modulo operator.
Finally, size(arr[idx]) is the number of elements in arr[idx].

Read full details and access the challenge on Dynamic Array | HackerRank

Solution

function dynamicArray(n, queries) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push([]);
    }
    let lastAnswer = 0;
    let answers = [];
    for (let i = 0; i < queries.length; i++) {
        let type = queries[i][0];
        let x = queries[i][1];
        let y = queries[i][2];
        let idx = (x ^ lastAnswer) % n;
        if (type === 1) {
            arr[idx].push(y);
        } else if (type === 2) {
            lastAnswer = arr[idx][y % arr[idx].length];
            answers.push(lastAnswer);
        }
    }
    return answers;
}

Time Complexity : O(n)

Space Complexity : O(n)

Hopefully the revised problem statement that I made is clear and understandable. If it is, you just have to follow the steps as instructed. My solution is also pretty self-explanatory as it mirrors the steps.

First, we declare the mentioned variables (arr with n elements, lastAnswer, answers).

Then, we iterate through each query and treat them according to their type.

Finally, we return the answers variable.

We’re iterating through the queries once so we have O(n) time and since we used arrays, we have O(n) space complexity.

Conclusion

That’s how you can solve the Dynamic Array Challenge in HackerRank.

Overall, this is a simple challenge if you can understand the instructions, you just have to follow it. But, the instructions are quite unclear so it took me quite some time to digest it, so I rewrite it a bit to help make it clearer for you. Hope it helps!

If you have an approach different from mine, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions using JavaScript in this blog!

See you next post!

Leave a Comment