Algorithms Part 2 : A Beginner's Attempt (at improvement and translation)

As mentioned in my last post, I wanted to revisit the same problem after learning some ruby. Not only did I want to "translate" from one language to another, I wanted to attempt at optimization. Here is my javascript solution. The full question is both in the repl and previous blog.

The TL;DR is starting from an array of all false values, act upon it from an array of queries. First value of a query determines SET(1) or GET(2). SET means you turn the value in the starting array true, GET means you determine the position (indexing starts at 1) of the next true from the given starting position. SET has no output. If there are no ouputs for the GET, output is -1.

testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
expectedOutput = output = [-1, 2, -1, 2]

I tried to recreate my javascript solution as similarly as possible using ruby methods as such.

testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]

queries.each {|q| 
  if q[0]==1
    testArray[q[1]-1]=true
  elsif q[0]==2
    found = false
    i=q[1]-1
      until found || i>testArray.length do
        if testArray[i]
          outputArray<<i+1
          found = true
        end
        i=i+1
      end
    if found == false
      outputArray<<-1
    end
  end
}
print outputArray

As mentioned before, this could run very long if the GET were to have to search a very long "testArray" only to return -1. What if setting also stored the value to an array of everything that has been set? I also had the idea to store the max value separately in case the "memoryArray" get large. First step is to chop down the "if GET" and store the SETs.

testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]
memoryArr=[]
memoryArrMax= 0

queries.each {|q| 
  if q[0]==1
    testArray[q[1]-1]=true
    memoryArr<<q[1]
    if q[1]>memoryArrMax
      memoryArrMax=q[1]
    end
  elsif q[0]==2
    if q[1] > memoryArrMax
      outputArray<<-1
    else
      puts 'i should be here 2 times'
    end
  end
}
print memoryArr
puts 
print outputArray

console:

i should be here 2 times
i should be here 2 times
[2]
[-1, -1]

So we see the output array is properly getting -1 twice, like before, but without even searching the the testArray. (I stored the max as a separate variable because the memoryArray could get pretty big, so in the worst case the .max built in method would take longer to recalculate every time there is a GET, I'm guessing, as opposed to a single comparison with each SET).

Next we add what to do if we have a GET where we know the return should not be -1. We need to find the first VALUE in memoryArray (which corresponds to indexes of true values in testArray) that is greater than or equal to the index provided with our GET request. This requires the array to be sorted. To cut down on sorting, we can opt to only sort on a GET request, instead of after every SET. Additionally, this can further be reduced by not sorting with consecutive GETs. I will add a boolean to track if our last query was a GET. This brings our final solution to:

testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]
memoryArr=[]
memoryArrMax= 0
lastWasGet=false

queries.each {|q| 
  if q[0]==1
    testArray[q[1]-1]=true
    lastWasGet=false
    memoryArr<<q[1]
    if q[1]>memoryArrMax
      memoryArrMax=q[1]
    end
  elsif q[0]==2
    if q[1] > memoryArrMax
      outputArray<<-1
    else
      if !lastWasGet
        memoryArr=memoryArr.sort
        lastWasGet=true
      end
      for index in memoryArr do
        if index>=q[1]
          outputArray<<index
        end
        break if index>=q[1]
      end
    end
  end
}

Repl here

I understand that there may be some limitations of the .sort method that may make this solution also sub-optimal. I still don't think it could be worse than the worst case of the previous brute-force-y solution. If you made it this far, let me know what your think, and how you would approach this!