2
\$\begingroup\$

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?

| improve this question | | | | |
\$\endgroup\$
  • \$\begingroup\$ For which input this code is being failed? \$\endgroup\$ – Saranjith Jan 22 at 7:22
  • \$\begingroup\$ (PFB made me think you Canadian.) \$\endgroup\$ – greybeard Jan 22 at 7:31
  • \$\begingroup\$ 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. \$\endgroup\$ – greybeard Jan 22 at 7:34
1
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Siddharth Kumar Jan 22 at 9:22
  • \$\begingroup\$ @SiddharthKumar: See updated answer. \$\endgroup\$ – Martin R Jan 22 at 10:07
  • \$\begingroup\$ Thanks Martin. The issue was with the hacker rank template code itself. Great work for pointing it out. \$\endgroup\$ – Siddharth Kumar Jan 22 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.