Dynamic Array Problem (Hacker rank)

Question

I am trying to solve the Dynamic Array problem on HackerRank:

• Create a list, seqList, of N empty sequences, where each sequence is indexed from 0 to N-1. The elements within each of the N sequences also use 0-indexing.
• Create an integer, lastAnswer, and initialize it to 0.
• The 2 types of queries that can be performed on your list of sequences (seqList) are described below:
  1. Query: 1 x y
     1. Find the sequence, seq, at index ((x ^ lastAnswer) % N) in seqList.
     2. Append integer y to sequence seq.
  2. Query: 2 x y
     1. Find the sequence, seq, at index ((x ^ lastAnswer) % N) in seqList.
     2. Find the value of element y % size in seq (where size is the size of seq) and assign it to lastAnswer.
     3. Print the new value of lastAnswer on a new line.

However, I am getting a "time out error" for very large inputs.

Below is my code in Swift so far:

func dynamicArray(n: Int, queries: [[Int]]) -> [Int] {
 var sequences: [Int: [Int]] = [:]
 var lastAnswer = 0
 var answerlist = [Int]()
 for query in queries {
 let queryType = query[0]
 let x = query[1]
 let y = query[2]
 switch queryType {
 case 1:
 let seq = (x ^ lastAnswer) % n
 if var sequence = sequences[seq] {
 sequence.append(y)
 sequences[seq] = sequence
 } else {
 sequences[seq] = [y]
 }
 case 2:
 let seq = (x ^ lastAnswer) % n
 let index = y % (sequences[seq])!.count
 lastAnswer = sequences[seq]![index]
 answerlist.append(lastAnswer)
 default: break
 }
 }
 return answerlist
}

Can it be further optimised?

• Saranjith: For which input this code is being failed?
• greybeard: (PFB made me think you Canadian.)
• greybeard: Please block-quote the gist of the problem statement near the top of your question. Please describe how the code solves the problem - in the code, preferably.

Answer 1

You chose to represent the "list of sequences" as a dictionary

var sequences: [Int: [Int]] = [:]

and here you test if a sequence for the given index already exists, and then either append a new element or create the initial sequence for that index:

if var sequence = sequences[seq] {
 sequence.append(y)
 sequences[seq] = sequence
} else {
 sequences[seq] = [y]
}

That can be greatly simplified by using a subscript with a default value:

sequences[seq, default: []].append(y)

But actually, instead of representing the "list of sequences" as a dictionary I would represent it as an array (of arrays) instead:

var sequences: [[Int]] = Array(repeating: [], count: n)

The number of sequences is a-priori known, so that there is no advantage of using a dictionary. Appending a new element to a sequences (query type 1) then becomes

sequences[seq].append(y)

and for query type 2 we get

lastAnswer = sequences[seq][index]
answerlist.append(lastAnswer)

without the need of forced-unwrapping for the dictionary subscripting.

This should also be more efficient, because (array) index lookups are faster than dictionary lookups.

Some more remarks:

• The type of a variable should not be part of the variable name, e.g. answers instead of answerList.

• Multiple (related) assignments can be combined to a tuple assignment, e.g.

  let (queryType, x, y) = (query[0], query[1], query[2])
  

• We know that the query type can only be 1 or 2, but a fatalError() in the default case helps to find programming errors.

Putting it together, the function could look like this:

func dynamicArray(n: Int, queries: [[Int]]) -> [Int] {
 var sequences: [[Int]] = Array(repeating: [], count: n)
 var lastAnswer = 0
 var answers = [Int]()
 for query in queries {
 let (queryType, x, y) = (query[0], query[1], query[2])
 switch queryType {
 case 1:
 let seq = (x ^ lastAnswer) % n
 sequences[seq].append(y)
 case 2:
 let seq = (x ^ lastAnswer) % n
 let index = y % sequences[seq].count
 lastAnswer = sequences[seq][index]
 answers.append(lastAnswer)
 default:
 fatalError("Bad query type")
 }
 }
 return answers
}

---

In addition, it seems that most of the time is spent while reading the input data into the queries array, done by the (HackerRank supplied template) code

guard let queriesRowTemp = readLine()?.replacingOccurrences(of: "\\s+$", with: "", options: .regularExpression) else { fatalError("Bad input") }
let queriesRow: [Int] = queriesRowTemp.split(separator: " ").map {
 if let queriesItem = Int(0ドル) {
 return queriesItem
 } else { fatalError("Bad input") }
}

Instead of removing trailing whitespace with a regular expression search we can split the input row and ignore empty components:

guard let queriesRowTemp = readLine() else { fatalError("Bad input") }
let queriesRow: [Int] = queriesRowTemp.split(separator: " ",
 omittingEmptySubsequences: true).map {
 if let queriesItem = Int(0ドル) {
 return queriesItem
 } else { fatalError("Bad input") }
}

In my test that cut the time to read 100000 queries down from 3.7 to 1.7 seconds.

• Siddharth Kumar: I tried your code. However, the 6 out of 10 test cases are still failing. Your code seems to increase the readability but over all time complexity remained the same. So, the issue i faced is still persisting. Note: I also used 2-D array in my first attempt, but it couldn't help; then after i made sequences as dictionary as it as O(1) complexity in most of the cases. Please refer [link] (raywenderlich.com/1172-collection-data-structures-in-swift)
• Martin R: @SiddharthKumar: See updated answer.
• Siddharth Kumar: Thanks Martin. The issue was with the hacker rank template code itself. Great work for pointing it out.