- Practice
- Data Structures
- Arrays
- Dynamic Array
- Discussions

# Dynamic Array

# Dynamic Array

EdwardSkrod + 16 comments BOOOOM! That was challenging and fun. I wish the language of the challenge were easier to understand. For example, the lastAn should have been named "lastAnswer" so as to be easier to understand. I thought lastAn was some kind of mathematical term. I would recommend the person responsible for making these challenges read "Clean Code" by Uncle Bob Martin!

bcrestel + 4 comments I completely agree, the wording of the question is terrible. I thought 'lastans' would be assigned the value of 'size'.... Your comment put me back on the right track. Thanks.

triethuynh + 0 comments Agree the wording is not goode enough. I was not quite understand his explaination why he came up to the output initially. Got it and solved the problemm finally. Thanks.

[deleted] + 4 comments Agreed, very confusing wording of the question. For me, the use of curly braces in the example made me think, wait, should seqList be a set? But he said it was a list? Does the word sequence suggest it should be ordered? I guess this question reflects real life, when the client cannot express accurately what they want!

neeraj85vns + 1 comment completely agree.. question is not explained well enough to write code..

aadivartak + 0 comments yeah I too agree to the fact.It became cryptic for me

christine_e_hill + 2 comments Also, they say "size", which is non-specific, when they mean "length". Size could be size in memory.

jonjanelle1 + 0 comments Agreed that the wording was a bit odd.

The usage of "size" instead of length is consistent the Java list interface, but not so much in general.

tyler_christian2 + 1 comment Just adding a comment because I understood this incorrectly.

*Size*is the y %*length of*seqList[index].So it is the length of the sub-array in the seqList array with an index ( seq ) calcuated from the original XOR ( ( x ^ lastAnswer ) % N ).

Size = y % len( seqList[seq] )

Patje + 2 comments Thank you! Thank you! After banging my head on the wall for an hour trying to understand their modulus statement, this cleared it up. Such a poorly written set of instructions.

rebelgiri + 0 comments Took an hour on understand. very confusing problem

I think you guys interpreted problem wrongly for query type 2

- Determine sequence number using ( ( x ^ lastAnswer ) % N ).
- ( y % size ) tell the index in an sequence. we need assign value at that index in the sequence(Step 1) to lastAnswer.

Hope its clear now :)

abhiemin + 2 comments import java.io.

*; import java.util.*;public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); int N= sc.nextInt(); int q=sc.nextInt(); int lastAnswer=0; int x=1; int a[] [] = new int[q][3]; List> seqList = new ArrayList>(); for(int i=0;i

`} x=(a[i][1]^lastAnswer%N); if(a[i][0]==1) { seqList.add(new ArrayList<Integer>()); seqList.get(x).add(a[i][2]); } else { int s = seqList.get(x).size() - 1; lastAnswer =seqList.get(x).get(s); if(lastAnswer!=0) System.out.println(lastAnswer); } } } } what is wrong with this code as it is giving only one positive test case?????`

fezett + 0 comments Why don't you print lastAnswer when it's 0?

francescq + 0 comments I have the same behaviour in javascript. My success test is the 10th one.

The problem is seq calculation returns a value much bigger than N, the actual length of seqList.

The solution is to add the paranthesis on xor calculation ( a ^ b) % c

saurabhyacky + 1 comment There are 2 queries , when to use which query?Like in the example they are executing 3 type 1 query and then type 2. When to switch from 1 to 2?

rantudas2480 + 0 comments I had the same doubt. The query formats are: Query: 1 x y(for query 1) & Query: 2 x y(for query 2).

amscopub_forum + 0 comments No in real life, you ask the client clarifying questions. If you build using unclear requirements, you will fail.

cook_tylerj + 0 comments I found that the example at the bottom contradicted what the explanation of the different queries did. They actually detail 2 different operations.

xingru_deng + 0 comments true. I find it unnecessarily hard to understand. The example is organized in a bad and confusing way.

rahulshetty96 + 7 comments import java.io.

*; import java.util.*;public class Solution {

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int q = sc.nextInt(); int inc=0,inb=0; int last = 0,x; int a[][] = new int[q][3]; int b[] = new int[100000]; int c[] = new int[100000]; for(int i = 0; i<q ; i++) { for(int j=0;j<3;j++) a[i][j] = sc.nextInt(); x = ((a[i][1]^last)%n); //sequence s1 or s0 if(a[i][0] == 1) // query 1 or 0 { if(x == 0) b[inb++] = a[i][2]; else c[inc++] = a[i][2]; } else{ if(x == 0) last = b[a[i][2]%(inb)]; else last = c[a[i][2]%(inc)]; System.out.println(last); } } }`

}

WOULD ANYONE MIND HELPING ME TO FIND WHATS WRONG WITH THIS PROGRAM?

Murli0802 + 1 comment n is number of sequences so ther might possible more then 2 sequences. In that case you need more array like b[],c[].Max possible size of these arrays are q so there you can also save some memory.

rahulshetty96 + 1 comment Thanks a lot friend!I got my mistake.

swaroophople + 1 comment I have the same problem can you explain??

Murli0802 + 1 comment n = number of sequence lastAns=0 q = number of query sequences S0={} S1={} S2={} . . . Sn={}

for queries type (1) 1 x y index of sequence id = (x^lastAns)%n append y in Si-th sequence

(2) 2 x y index of sequence id = (x^lastAns)%n lastAns = valueAt(y%(size of Si-th sequence)) and pint lastAns

after every query value of lastAns will be updated according to query type.

anmolnarang4210 + 2 comments what is y and x

Murli0802 + 2 comments y and x are integer inputs (given in question)

ankit_1310029 + 3 comments what is the size of every sequence??

according to me it must be n, but i'm guessing that size of each sequence should be exactly the amount of elements that are present at that moment.

cemelo + 0 comments Yeah. That sentence has terrible phrasing.

ankit_1310029 + 0 comments [deleted]

muntaqeem + 5 comments watch each input line after the first one.

1 0 5

this means, query type 1, x is 0 and y is 5

2suprit + 0 comments Thank you so much, understood this now

undefitied + 0 comments Thanks! It was unclear.

Gaurav_B + 0 comments Thank You So much. Really it was unclear.

Aliya_I + 0 comments oh, without your explanation I've could not figure it out. Thank you!

wasitshafi700 + 0 comments tnks bro.... i was missing that....

vincent_g + 0 comments [deleted]darkcode + 1 comment Use ArrayList,it will be easier

tiger_1 + 2 comments how to create N number of arraylist dynamically ??

steffen_vulpius + 1 comment ArrayList[] sequenceArray=new ArrayList[length]; for (int j = 0; j <length; j++) { sequenceArray[j]=new ArrayList<Integer>(); }

where length is the first int read from the input.

codertoaster + 0 comments Or you can just create and ArrayList of ArrayLists.

ArrayList> arr=new ArrayList<>();

each element i in the list arr will be another ArrayList.

aparnamsh29 + 2 comments To avoid errors such as "Unsafe operations",Use the following:-

ArrayList<ArrayList<Integer>> b=new ArrayList<ArrayList<Integer>>(n); for(int i=0;i<n;i++) b.add(new ArrayList<Integer>());

And to later on perform the operations, use expressions like:

int t=(a[i][1]^last)%n; b.get(t).add(a[i][2]);

serpentsmiles + 1 comment Many, many users have repeatedly asked that others not post their code in the discussions. If you wish help with your code, simply say so, and if another user responds yes, then send them a private message. Please.

WittyNotes + 1 comment Is this really true? I've never seen others comment on this, and it's seems to be a function of the discussion board to post your (working) result and compare to others' solutions.

AGRN96 + 0 comments I find it much better to just submit your code, then copy the link and posting it on here. It seems to be a way to deter people from just copying the code and not learning anything. The submission link method requires them to forgo any points if they have not completed the problem.

rwan7727 + 8 comments In c++:

`int n,q; cin >> n >> q; vector <vector <int> > s(n,vector <int> ()); int lastAnswer=0; for (int i=0;i<q;i++) { int t,x,y; cin >> t >> x >> y; if (t==1) { s[(x^lastAnswer)%n].push_back(y); } else { lastAnswer=s[(x^lastAnswer)%n][y%s[(x^lastAnswer)%n].size()]; cout << lastAnswer << endl; } }`

bhavgothadiya + 1 comment Here why vector > s(n,vector ());

bhavgothadiya + 0 comments what is used here vector>

bhavgothadiya + 0 comments what is T,X,y Here

amorthyo + 0 comments Why did you do lastAnswer=s[(x^lastAnswer)%n][y%s[(x^lastAnswer)%n].size()]; in the column sec for s?

josepaez_2 + 0 comments great approach!

aryabharat + 1 comment we can make it a bit more simple by replacing vector decl. by

vector <int> s[n];

abhaykuma + 0 comments what will that do ? will it declare 2d vector of n rows ?

thethanh92 + 0 comments [deleted]rohanshenoy96 + 1 comment I wrote this and i am getting Run time error. ALmost same code. Can anyone tell me why this isn't working.

#!/bin/python3 import math import os import random import re import sys # Complete the dynamicArray function below. def dynamicArray(n, queries): lastNumber = 0 seqList=[]; for i in range(n): seqList.append([]) res = []; for k, x, y in queries: index = (x^lastNumber)%n if k==1: seqList[index].append(y) print(seqList) else: size = len(seqList[index]) print(seqList) print(size) lastNumber = seqList[index][y%size] print(lastNumber) res.append(lastNumber) return res if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nq = input().rstrip().split() n = int(nq[0]) q = int(nq[1]) queries = [] for _ in range(q): queries.append(list(map(int, input().rstrip().split()))) result = dynamicArray(n, queries) fptr.write('\n'.join(map(str, result))) fptr.write('\n') fptr.close()

laurent_philipp1 + 0 comments Hi ! Just remove your "print" instructions because they perturb the output...

Edit: Why minus votes? Could someone explain?

hainam2511 + 0 comments vector<vector<long>> l; for(int i = 0; i < n; i++) l.push_back( *(new vector<long>()) );

You can also do this to initiate the 2D vector

raghuchahar007 + 0 comments [deleted]nikhilsai_v + 0 comments it works only for two sequences if there are more than 2 sequences then error

SuperGogeta + 1 comment Funny thing is it's a simple piece of code, just 11 lines in python, shame the question is so poorly framed.

knightofbaghdad + 0 comments [deleted]

Superleroy + 2 comments After reading the description several times, trying to map the output to the input, then reading the comments, reading the description again, taking a ten minute break, reading the description again and only after that realizing what the types of query actually means, I have to agree that it was fun too solve. Seriously is there any way to obscure the intention any more? The description is way to hard for the work that has to be done.

cal_pang123 + 1 comment Agreed - I read the question start to finish twice and still don't completely understand what the question is asking.

Alphonso + 1 comment When you first read the question you look over at the difficulty level and wonder if "Easy" is relative to a genius. The person who wrote this question definitely needs to rewrite it so it's more clear.

thedurphy + 0 comments No, the sign of a genius is to be able to explain a subject matter to a child. This guy couldn't explain to me how to work a faucet if he wanted to.

thinhpng + 0 comments Boy, I had no clue what he was asking about. I did not understand what the problem is.

techniker + 0 comments So true. The question was really abstruse. Kind of infuriated me.

manisha_9801 + 0 comments can u pls explain me this question

pritz007 + 0 comments Agreed! Problem discription is way too confusing.

meghanareddy500 + 0 comments can u please explain the question?

juanjoalbo + 0 comments Hard to read, it made me want to avoid that challenge.

lucyluo88 + 0 comments I completely agree, the wording of the question is terrible.

Luane + 0 comments The style of writing used was very much the kind we find in technical books or some textbooks. It is closer to "mathematical language".

limpingandroid + 0 comments 3 years later, and it's still worded in a confusing way. Also, the mathematics appear to use non-standard symbols.

The example gives (1 XOR 7) % 2 = 3. So 1 XOR 7 is 6, but 6 mod 2 gives 0. So apparently they mean integer division when using the % sign??? Who does that??

Edit: Oops, never mind. Re-read it once again, and they do go with 6 mod 2 = 0. But the zero is then used as an index into array1 (3,5), and LastAnswer is set to that. That's where the 3 comes from. Okay, I think I understand it well enough to start programming finally.

Luane + 0 comments I am still wondering if the difficulty I found to understand the challenge was because I need to study more or was because the question was made in a confusing way?

Kanahaiya + 0 comments hi,

I have uploaded a video tutorial on the same.

I hope this comment will help you to understand the problem.

https://www.hackerrank.com/challenges/dynamic-array/forum/comments/591510

sekhar_samala + 1 comment Question is so confusing. Cloud you please re-frame question?

jensbodal + 3 comments You just need to break it down into each part.

There is a dynamic array of sequences.

There are two types of queries:

one adds an element to a sequence at a calculated index

two finds the sequence at a calculated index and prints the value at the calculated subindex.

Sammieo + 2 comments Thank you for the simplification. Can I ask what, precisely, you mean by a 'calculated index' though?

jensbodal + 12 comments The calculated index is definied in the two bullet points:

`x`

`y`

: Insert`y`

at the end of the`((x XOR lastans) mod N)`

th sequence`x y`

: Print the value of the`(y mod size)`

th element of the`((x XOR lastans) mod N)`

th sequence. Here,**size**denotes the size of the related sequence. Then, assign this integer to**lastans**.

So given 2 squences (

`N=2`

),`lastans=0`

and`1 0 5 | {type = 1, x = 0, y = 5}`

you would apply operation**#1**to`0`

and`5`

: You would insert 5 at the end of the squence at the calculated index of`((0^0)%2)`

Think of it like a hashmap with buckets: the sequences are buckets, and you are inserting a new collision at the end of the bucket's linked list.

enricotalbot + 0 comments Thanks jensbodal, the hardest part of it was deciphering the extremly poorly worded question/explanation.

shoaibahmed9922 + 0 comments thank You very much " jensbodal "...

namanrocks94 + 1 comment `for(int i=0; i<Q;i++) { long int k=A[i][0]; if(k==1) { long int x=A[i][1]; t=((x^lastAns)%N); list[t][a[t]]=A[i][2]; a[t]++;} else{ long int x=A[i][1]; t=((x^lastAns)%N); long int y=A[i][2]; long int size= y % a[t]; lastAns=list[t][size]; cout<<lastAns<<endl; } } is the logic right here ?`

jlokhande46 + 0 comments no its wrong u have to place the element right after its first one

Priten + 0 comments Thank you for the clarification!

zainul118 + 0 comments Cheers mate..thanks for this explanation... I was going mad understanding the problem statement

786lokesh + 0 comments [deleted]anukritinigam02 + 0 comments thank you so much so for the description

caglaror + 0 comments Without your explainations i couldn't solve. Thank you @jensbodal.

UmkaFrom + 0 comments GOD BLESS YOU, seriously, I read the description and the example so many times and could not figure out where the author gets values for x and y... Such a simple problem if you word it right

teja2213 + 0 comments the inputs are 1 x y. Unfortunately, I am reading it as 1xy(1 multiplied with y).

ddebnath_32 + 0 comments But in question word "append" is used for query 1.

h276692580 + 1 comment Have a confuse about task.

Q1: 1 x y

Find the sequence seqList, seq , at index ((x xor lasAns) % N)in seqList.

what is x, what is y? x, y not confirm, how we can get the index?

triethuynh + 0 comments See post from "jensbodal" (6 months ago) - he explained x, y, etc.

wasitshafi700 + 0 comments tnks @jensbodal

pokedev8 + 0 comments Apologies for any offence caused to the author/writer of the quiz, it's just, I would be really grateful if someone could help me decipher what the question is asking for?

I've read the questions about 5 times, and am struggling to understand what it is that is needed to be done?

(I'll keep re-reading in the meantime, but if someone could help in the meantime that would be grand :( )

lmahanand + 0 comments Hackerrank,

Please have readable question libraries. You questions very poorly written. It needs more effort in undertanding the questions than solving the questions.

Please improve the question descriptions.

kprateek88 + 1 comment This is a simple "do as you are told" thing, with a direct straightforward implementation and no algorithmic cleverness needed. I wonder why it is marked "difficult".

dawguy + 3 comments Dynamicly increasing the size of the array in for query (1) might be why its marked as difficult.

[edit] Although if you in Java if you use an ArrayList then it does seem like a very straight forward problem. If you understood the question and could walk through the example on paper you can implement a solution.

jakezorx + 1 comment Yeah, they should perhaps limit this problem to something like C++ or C, without all the goold ol' memory errors its perhaps a bit too easy.

willybarro + 0 comments C++ has the vector container that works pretty much like Java's ArrayList, so it'd be as easy as it was for you in Java. And I agree with you that it should be limited to C or some language that don't have builtin dynamic array types. The biggest difficulty in this challenge is interpreting the text :-/.

thricefall + 0 comments Why do we have to dynamically increase the size of the array for query 1? Something MOD n will always return a value less than n.

vaschetan + 0 comments [deleted]

Freak_1231 + 1 comment sadly the question was poorly explained... >..<

vtu5977 + 0 comments u r correct

gbmartelli + 5 comments I will try to clarify the question for people which are having a hard time to understand it, like I was: seqList is basically an Anrray of Arrays, each Array in seqList will be dynamic, while seqList itself will be static with the input 'N' determining the number of Arrays that will compose it. The 'Q' input will determine the number of Queries. Each Query will demand an input of 3 integers: 't', 'x' and 'y'. The 't' is for "type". The type 1 Query will append the 'y' variable to some array in seqList, the formula will specify which one. The type 2 Query will take some value, that was alredy assigned to some Array of the seqList, and copy that to lastAnswer. The first formula specifies the array of seqList and the second formula specifies which value of that Array must be taken. I hope the schematic below make it clearer.

setList List 0 [1 : 2 : 3] List 1 [4 : 5] List 2 [] List 3 [6 : 7 : 8 : 9] . . List N-1 [0: 1]

`It might be a little bit harder for C programmers because it will be needed to reallocate memory dinamically for each type 1 query. I think it's easier if you keep in mind that the seqList is just a pointer to a pointer to a integer. And it's necessary to crate array to store the number of elements in each array of seqList. I hope this post might be useful for someone. Please let me know if it's not clear enough or if it's not clear at all. This is my solution in c if anyone is interested.`

//Guilherme Benner Martelli #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { int N; int Q; int t, x, y; int seq; int lastAnswer = 0; int **seqList; int * seqCount; int index; scanf("%i", &N); seqList = malloc(N*sizeof(int *)); seqCount = malloc(N*sizeof(int)); for(int i = 0; i < N; i++) seqCount[i] = 1; scanf("%i", &Q); for(int i = 0; i < Q; i++){ scanf("%i %i %i", &t, &x, &y); if(t==1){ seq = ((x^lastAnswer)%N); seqList[seq] = realloc(seqList[seq],seqCount[seq]*sizeof(int)); seqList[seq][seqCount[seq]-1] = y; seqCount[seq]++; }else { seq = ((x^lastAnswer)%N); index = y%(seqCount[seq]-1); lastAnswer = seqList[seq][index]; printf("%i\n", lastAnswer); } } for(int i = 0; i < N; i++) free(seqList[i]); free(seqList); free(seqCount); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

krithikams0402 + 2 comments can u explain still more clearly please, specially seqlist(array of arrays concept)

gbmartelli + 0 comments By array of arrays I mean that each element of the seqList array is another array. It's similar to a 2D array but in the 2D array every line has the same number of columns, on the other hand each line of the array of arrays has a different number of columns.

gbmartelli + 0 comments The compiler understands an array as an address to the first byte of a memory block. I think it's easier to understand if you think about seqList as an address to the first byte of a memory block that happens to store addresses to other memory blocks.

nihir_gul + 1 comment The code below is on the same lines as your code, but please tell me the mistake. I am getting a lot of segmentation faults.

# include

# include

# include

# include

int bitxor(int a,int b) { return (a^b); }

int main() { int ** sl; int la=0,n,i,q; int *size;

`scanf("%d %d\n",&n,&q); sl=(int **)malloc(n*sizeof(int *)); size=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++) { sl[i]=(int *)malloc(n*sizeof(int)); size[i]=0; }`

// printf("%d %d\n",n,q);

`while(q--) { int a,x,y; scanf("%d %d %d\n",&a,&x,&y); // printf("%d %d %d\n",a,x,y); if(a==1) { int j; j=(bitxor(x,la)%n); sl[j][size[j]] = y; ++(size[j]); } else if(a==2) { int j; j=(bitxor(x,la)%n); int k=size[j]; int l = y%k; la = sl[j][l]; printf("%d\n",la); } } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;`

}

gbmartelli + 1 comment SegFault means you are trying to access a memory address you are not allowed to. It's propably because you are not reallocating the memory of the arrays each time you add a new element in type 1 querry. Use realloc function.

amar97 + 0 comments can u explain what are the arguments inside realloc and how they works

vikasgoel608 + 0 comments Nice Explanation.

Thanks

DHKavinda + 1 comment when running in windowsOS, program suddenly stops if we input "1" for "x". Doesn't work.

vikasgoel608 + 0 comments I tried on Ubuntu...Thanks

ashsri412 + 0 comments [deleted]

satadhi + 0 comments the language used for this question is really weird specially for people who think in terms of python.

RodneyShag + 9 comments ### Java solution - passes 100% of test cases

Use an ArrayList<ArrayList<Integer>> in Java

From my HackerRank solutions.

import java.util.Scanner; import java.util.ArrayList; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int Q = scan.nextInt(); int lastAns = 0; /* Create 2-D ArrayList */ ArrayList<ArrayList<Integer>> lists = new ArrayList<>(); for (int i = 0; i < N; i++) { lists.add(new ArrayList<Integer>()); } /* Perform Q Queries */ for (int i = 0; i < Q; i++) { int q = scan.nextInt(); int x = scan.nextInt(); int y = scan.nextInt(); ArrayList<Integer> seq = lists.get((x ^ lastAns) % N); if (q == 1) { seq.add(y); } else if (q == 2) { lastAns = seq.get(y % seq.size()); System.out.println(lastAns); } } scan.close(); } }

Let me know if you have any questions.

pragunkapoor193 + 1 comment can u please explain the solution

RodneyShag + 0 comments Hi. The problem asks us to save a bunch of lists and perform queries on them. How would we represent 1 list? Well, an ArrayList<Integer> is a good choice instead of an int[] since we don't know the final size our list needs to be.

Now that we know how to represent 1 list, how should we represent a bunch of lists? Well, we can use an ArrayList<ArrayList<Integer>>, which is basically a list of lists. Creating this data structure is the main challenging part of this problem.

The rest of the code just performs the 2 types of queries on our data structure.

aakash216961 + 0 comments Brilliant solution bro! Cheers.

Soul_XHacker + 0 comments Thanks! Your code provided me a vital hint. For last 30 mintes I was doing lastElemOfArray()%size() instead of appendedElement%size()

dnyaw + 0 comments Best Explaination and cleanest code ever. thanks

Neer1416 + 0 comments Awesome

Starboy65 + 0 comments fantastic bro i am thinking just the same like u and come up with a similar solution after getting your logic ...:)

sryar92 + 1 comment @rshaghoulian Using java8, do we have a option to make a 2-D array in which outer structure is array and inner structure(each element of array) is ArrayList? As here we have fixed value for n (outer dimension) but changing length for each element of array[n] i.e. ArrayList inside Array.

RodneyShag + 0 comments I don't think that's possible, and the compiler will prevent you from creating such a data structure. This is because, when the compiler goes to allocate memory fo this 2-d data structure, it won't know how much memory to allocate, since it doesn't know the size of each item in array[] (since they're variable size ArrayLists).

You can still try it out to see how the compiler responds.

toaderstandrei + 0 comments I got close to the same solution of yours after some hours of work. However, the problem was formulated a bit confusing. It was more to understand what one wants. Problem is not so hard once you get it.

palashrawat7 + 1 comment Why have you perfomed (x^lastAns). Please explain it.

We have to perform the XOR operation.

RodneyShag + 1 comment In Java, ^ is XOR

palashrawat7 + 0 comments So ^ doesn't mean the power function. I know we use pow(n,x) but I thought ^ represents power. Thanks for your reply. I really appreciate that.

yli131 + 1 comment create an array of arraylist and initialize them

`ArrayList<Integer>[] group = new ArrayList[N]; for (int i = 0; i < N; i++) { group[i] = new ArrayList<Integer>(); } then the rest is quite easy`

maximshen + 4 comments I have a question about whether we should use Array of ArrayList, or just 2D array.

I have my own code below

public class Solution {

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int lastans =0; int N = sc.nextInt(); int Q = sc.nextInt(); int tag, x, y, index; ArrayList<Integer>[] list = new ArrayList[N]; while(Q-->0){ tag = sc.nextInt(); x = sc.nextInt(); y = sc.nextInt(); index = (x^lastans)%N; switch (tag) { case 1: if (list[index] == null) { ArrayList<Integer> myList = new ArrayList<>(); myList.add(y); list[index] = myList; } else list[index].add(y); break; case 2: System.out.println(lastans = list[index].get(y % list[index].size())); break; } } }`

}

And code from @__spartax:

public class Solution {

`static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer tok = null; public static void main(String[] args) { int last = 0, x, y; int n = getInt(), q = getInt(), cmd, c, len; int[][] A = new int[n][]; int[] tmp; for(int k = 0; k < q; ++k) { cmd = getInt(); x = getInt(); y = getInt(); c = (x^last) % n; switch(cmd) { case 1: if(A[c] == null) len = 1; else len = A[c].length + 1; tmp = new int[len]; if(A[c] != null) System.arraycopy(A[c], 0, tmp, 0, A[c].length); tmp[tmp.length-1] = y; A[c] = tmp; break; case 2: System.out.println(last = A[c][y % A[c].length]); } } } static String gets() throws IOException{ if(tok == null || !tok.hasMoreTokens()) tok = new StringTokenizer(br.readLine()); return tok.nextToken(); } static int getInt() { try { return Integer.parseInt(gets()); } catch(IOException | NumberFormatException e) { return -1; } }`

}

When I used array of ArrayList, I spent twice more time as using 2D array. Yes, I use ArrayList, but ArrayList.get(index) only needs constant time like array. And @__spartax used System.arraycopy, which requires O(n), which is exactly how ArrayList works when it has to expand its size. But he expanded the size everytime. Yes, I have a higher space complexity because of ArrayList, but I don't get it why my algo spends twice time as his. Thanks in advance.

__spartax + 0 comments [deleted]__spartax + 1 comment First of all your algo uses

`Scanner`

. Using`BufferedReader`

will improve performance of your algorithm. Secondly`ArrayList`

is just a wrapper for`Object[]`

and`System.arraycopy`

is a native method.maximshen + 0 comments Thank you. For other ppl's reference, found one article about Scanner vs BufferedReader

https://iamcodelover.wordpress.com/2012/08/27/reading-from-console-java-scanner-vs-bufferedreader/

manoranjan03 + 0 comments Hey, Can you explain why is this required!!

if (list[index] == null) { ArrayList myList = new ArrayList<>(); myList.add(y); list[index] = myList; }

Thanks

matherthal + 0 comments This solution helped me to figure it out that creating a new List>() was too expensive for some cases. When I changed it to new List[N]. It makes sense.

Sort 987 Discussions, By:

Please Login in order to post a comment